二叉查找树

二叉查找树英语Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sorted binary tree)。二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合multiset关联数组等。

二叉查找树是指一棵空树或者具有下列性质的二叉树

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

注:维基百科和百度百科上性质【1】和【2】不同,描述中的一个性质会存在键值相等的情况,考虑到性质【4】,是不应该存在这个相等情况的。

注:以上定义摘自维基百科(微幅修改)。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低,等于树高,期望为O(log n),最坏为O(n)。

二叉查找树

两个高度相同的二叉查找树

上面的两个二叉查找树树高是一样的,但是查找是速度是相同的。

下面介绍二叉查找树的一些操作:

查找节点

因为二叉查找树的性质,查找树中一个节点是十分容易的,遵循以下原则即可:

  • 空树,查找失败;
  • 根节点匹配查找关键字,返回;
  • 当前节点值小于查找关键字,查找右孩子节点;
  • 当前节点值大于查找关键字,查找左孩子节点。

其实就是大了往左,小了往右。

插入节点

因为二叉查找树的节点插入并不要求平衡性,所以插入新节点总是放到叶子节点上就可以了,步骤如下:

  • 空树,新节点作为根节点;
  • 当前节点值等于新值,因为已经存在这个值,直接返回就可以了;
  • 当前节点大于新值,递归插入左子树;
  • 当前节点小于新值,递归插入右子树。
二叉查找树的插入

二叉查找树中插入新节点4

如上图,二叉查找树中新增一个键值为4的节点。

删除节点

删除节点需要理解什么是中序遍历,中序遍历就是先遍历左子树,然后访问根节点,最后遍历右子树。下面是删除某节点的方案:

  • 节点是叶子节点,删除之,其父节点指向空;
  • 删除节点是单支节点,父节点指向其子节点,子节点指向父节点,删除当前节点;
  • 节点存在左右子树,找到其中序遍历的前驱(或后继),替换当前节点的位置,修改这个前驱(或后继)的父节点指向空,删除该节点。
二叉查找树的删除

二叉查找树的删除

二叉查找树双分支节点删除

二叉查找树双分支节点删除

上面两个图展示了有两个分支的节点删除时的情况,实现时可以自由选择使用前驱替代还是后继替代(其中红色为删除节点,绿色为替换原来位置的前驱或后继节点)。

关于后继的查找,因为二叉查找树的性质,如果一个节点有右子树,右子树的最小节点就是后继节点,如果没有右子树,那么就往上找,他的第一个作为左孩子的父节点一定比他大,就是这个节点。

相关代码如下:

头文件:

相关操作,代码实现时和讲解并不完全相同,特别是在删除部分,很多递归的地方是可以用循环来实现的,这样节省了资源,删除部分并没有按照一个个条件实现,也是为了节省代码:

测试一下效果:

以上就是代码,可以跑一下加深理解。

二叉查找树》上有2条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注