前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >二叉查找树(Binary Search Tree)

二叉查找树(Binary Search Tree)

作者头像
None_Ling
发布2018-10-24 14:45:56
1.2K0
发布2018-10-24 14:45:56
举报
文章被收录于专栏:Android相关

定义

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  3. 任意节点的左、右子树也分别为二叉查找树;
  4. 没有键值相等的节点

深度为3的二叉查找树

优势

  1. 查找、插入的时间复杂度较低
  2. 时间复杂度为O(logN),最坏时间复杂度为O(N)
  3. 从基础的二叉查找树可以衍生平衡二叉树,从而使得查询/插入操作的时间复杂度平衡在O(logN) PS: 查询节点的时间与树高度相关,高度越高,时间越长

劣势

  1. 由于普通的二叉查找树没有做平衡(通过旋转来达到树左右子树高度相差不大)处理,导致可能会出现树的严重倾斜

平衡二叉树与倾斜的二叉树.png

二叉树查找

在二叉搜索树b中查找x的过程为: 若b是空树,则搜索失败,否则: 若x等于b的根节点的数据域之值,则查找成功;否则: 若x小于b的根节点的数据域之值,则搜索左子树;否则: 若x大于b的根节点的数据域之值,则搜索右子树。

查找过程.png

二叉树插入

向一个二叉搜索树b中插入一个节点s的算法,过程为: 若b是空树,则将s所指结点作为根节点插入,否则: 若s->data等于b的根节点的数据域之值,则返回,否则: 若s->data小于b的根节点的数据域之值,则把s所指节点插入到左子树中,否则: 把s所指节点插入到右子树中。(新插入节点总是叶子节点)

插入过程.png

二叉树删除

在二叉查找树删去一个结点,有3种情况:

  1. 若*p结点为叶子结点,即当前节点的左子树和右子树均为空树: 由于删去叶子结点不破坏整棵树的结构,则只需修改其父节点的指针即可。

删除无子树的节点

  1. p结点只有左子树或右子树: 此时只要令左子树或右子树直接成为父结点左子树(当p是左子树)或右子树(当*p是右子树)即可,作此修改也不破坏二叉查找树的特性。

删除只有一个子树

  1. p结点的左子树和右子树均不空: 在删去p之后,为保持其它元素之间的相对位置不变,可按中序遍历保持有序进行调整,可以有两种做法 a. 令p的左子树为f的左/右(依p是f的左子树还是右子树而定)子树,s为p左子树的最右下的结点,而p的右子树为s的右子树 b. 令p的直接前驱(in-order predecessor)或直接后继(in-order successor)替代p,然后再从二叉查找树中删去它的直接前驱(或直接后继)。

删除有两个子树的节点

前驱(Preducessor)

定义:节点val值小于该节点val值并且值最大的节点 若一个节点有左子树,那么该节点的前驱节点是其左子树中val值最大的节点(也就是左子树中所谓的rightMostNode) 若一个节点没有左子树,那么判断该节点和其父节点的关系 2.1 若该节点是其父节点的右节点,那么该节点的前驱结点即为其父节点。 2.2 若该节点是其父节点的左节点,那么需要沿着其父亲节点一直向树的顶端寻找,直到找到一个节点P,P节点是其父节点Q的右节点,那么Q就是该节点的前驱节点

TreeMap的Preducessor算法

如最上图所示: 3的前驱是1:当前节点有左子树,找到左子树最右的节点 10的前驱是8:当前节点没有左子树,并且是父节点的右子树 4的前驱是3:当前节点没有左子树,找到沿父节点出于左子树节点

后继(Successor)

定义:节点val值大于该节点val值并且值最小的节点 若一个节点有右子树,那么该节点的后继节点是其右子树中val值最小的节点(也就是右子树中所谓的leftMostNode) 若一个节点没有右子树,那么判断该节点和其父节点的关系 2.1 若该节点是其父节点的左子树,那么该节点的后继结点即为其父节点 2.2 若该节点是其父节点的右子树,那么需要沿着其父亲节点一直向树的顶端寻找,直到找到一个节点P,P节点是其父节点Q的子树 ,那么Q就是该节点的后继节点

TreeMap的Successor算法

如最上图所示: 8的后继是10:当前节点有右子树,并且右子树节点无左子树 10的后继是13:当前节点有右子树,则找到右节点的右子树最小的节点 4的后继是6:当前节点是父节点的左子树,则该节点的后继即为其父节点

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017.12.08 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 定义
  • 优势
  • 劣势
  • 二叉树查找
  • 二叉树插入
  • 二叉树删除
  • 前驱(Preducessor)
  • 后继(Successor)
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档