来源:CSDN

1 二叉排序树(BST)

1.1 定义

二叉排序树(Binary Sort Tree),又称二叉查找树,或是一棵空树,或是具有下列特性的二叉树:

  1. 若左子树非空,则左子树上所有节点值都小于根节点的值。
  2. 若右子树非空,则右子树上所有节点值都大于根节点的值。
  3. 左、右子树也分别是一棵二叉排序树。

由此可见,二叉排序树的定义也是递归的。由定义可知,左子树节点值 < 根节点值 < 右子树节点值,因此二叉排序树是中序有序的。

1.2 二叉排序树的插入

二叉排序树作为一种动态树表,其特点是树的结构通常不是一次生成的,而是在查找过程中,当树中不存在关键字值等于给定值的结点时再进行插入的。

插入结点的过程如下:若原二叉排序树为空,则直接插入结点:否则,若关键字k小于根结点值,则插入到左子树,若关键字k大于根结点值,则插入到右子树。插入的结点一定是一个新添加的叶结点,且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子。

1.3 二叉排序树的删除

在二叉排序树中删除一个结点时,不能把以该结点为根的子树上的结点都删除,必须先把被删除结点从存储二叉排序树的链表上摘下,将因删除结点而断开的二叉链表重新链接起来,同时确保二叉排序树的性质不会丢失。

删除时共分3种情况:

  1. 若被删除结点z是叶结点,则直接删除,不会破坏二叉排序树的性质。
  2. 若结点只有一棵左子树或右子树,则让z的子树直接替代z,成为z父结点的子树。
  3. 若结点有左、右两棵子树,则令z的直接后继(或直接前驱)替代z,然后从二叉排序树中删去这个直接后继(或直接前驱),这样就转换成了第1或第2种情况。

1.4 二叉排序树的查找效率

二叉排序树的查找效率主要取决于树的高度。若构造二叉排序树的输入序列越接近有序,则二叉排序树的查找效率越差(因为构造出的二叉排序树的高度越高)。

极端情况下,二叉排序树是一个只有左孩子或右孩子的单支树,此时树的高度最高且等于总结点数,查找性能最差。


如上图所示,两棵树的平均查找长度为:

因此,为避免树的高度增长过快,降低二叉排序树的性能,便提出了平衡二叉树,平衡二叉树的平均查找长度为O(log2​n),其中n为节点数。

2 平衡二叉树(AVL)

平衡二叉树(Balanced Binary Tree),为避免树的高度增长过快,降低二叉排序树的性能,规定在插入和删除二叉树节点时,保证节点左、右子树高度差的绝对值不超过1(-1、0、1),将这样的二叉树成为平衡二叉树。又称AVL,AVL树得名于它的发明者G. M. Adelson-VelskyE. M. Landis,他们在1962年的论文《An algorithm for the organization of information》中发表了它。

平衡因子:节点左子树和右子树的高度差,即平衡因子 = 左子树高度 - 右子树高度,则由平衡二叉树定义可知,节点的平衡因子取值只能为-1、0、1。

2.1 平衡二叉树的插入

1 LL平衡旋转(右单旋转)

此种方式在某节点左孩子(L)的左子树(L)上插入新节点,故名为LL型。

如图所示,在节点4的左孩子2的左子树1,插入新节点0。节点4的平衡因子由1变为2(左子树高度增加),故要右旋(高度低的向下去)以平衡子树。

解决方法:

  • 节点4右下旋转成为2的右子树(2的右子树被替代,4的左子树变空)。
  • 节点2的原右子树成为4的左子树(2的原右子树补上4的空左子树)。

Q:若是在上图中1的右侧插入一个结点又该怎样操作呢?
A:插入在1右侧的节点,同时又在2的左侧(1<新节点值<2),由于是顺序树,则4经过旋转后新节点最终位置仍应在1右侧、2左侧,旋转后节点顺序不变(新节点仍在1右侧、2左侧),所以无论在左侧和右侧插入,操作步骤不变。

2 RR平衡旋转(左单旋转)

此种方式在某节点右孩子(R)的右子树(R)上插入新节点,故名为RR型。

如图所示,在节点3的右孩子5的右子树6,插入新节点7。节点3的平衡因子由-1变为-2(右子树高度增加),故要左旋(高度低的向下去)以平衡子树。

解决方法:

  • 节点3左下旋转成为5的左子树(5的左子树被替代,3的右子树变空)
  • 节点5的原左子树成为3的右子树(5的原左子树补上3的空右子树)

Q:若是在上图中6的左侧插入一个结点又该怎样操作呢?

A:插入在6左侧的节点,同时又在5的右侧(5<新节点值<6),由于是顺序树,则3经过旋转后新节点最终位置仍应在6左侧、5右侧,旋转后节点顺序不变(新节点仍在6左侧、5右侧),所以无论在左侧和右侧插入,操作步骤不变。

3 LR平衡旋转(先左旋、后右旋)

此种方式在某节点左孩子(L)的右子树(R)上插入新节点,故名为LR型。

如图所示,在节点6的左孩子2的右子树3,插入新节点4。节点6的平衡因子由1变为2(左子树高度增加),此时需要进行先左后右两次旋转操作。

解决方法:

  • 节点6的左孩子2的右子树根节点3先左上旋转,替代2成为6的左子树,2成为3的左子树。
  • 节点6后右下旋转,成为3的右子树(3的右子树被替代,6的左子树变空),再将节点3的原右子树成为6的左子树(3的原右子树补上6的空左子树)。


Q:若是在上图中3的左侧插入一个结点又该怎样操作呢?

A:插入在3左侧的节点,同时又在2的右侧(2<新节点值<3),由于是顺序树,则3经过旋转后新节点最终位置仍应在3左侧、2右侧,旋转后3的左子树非空,所以要将节点插入2的右侧,最后将6直接右下旋转即可。

4 RL平衡旋转(先右旋、后左旋)

此种方式在某节点右孩子(R)的左子树(L)上插入新节点,故名为RL型。

如图所示,在节点2的右孩子7的左子树6,插入新节点4。节点2的平衡因子由-1变为-2(右子树高度增加),此时需要进行先右后左两次旋转操作。

解决方法:

  • 节点2的右孩子7的左子树根节点6先右上旋转,替代7成为2的右子树,7成为6的右子树。
  • 节点2后左下旋转,成为6的左子树(6的左子树被替代,2的右子树变空),再将节点6的原左子树成为2的右子树(6的原左子树补上2的空右子树)。

Q:若是在上图中6的右侧插入一个结点又该怎样操作呢?

A:插入在6右侧的节点,同时又在7的左侧(6<新节点值<7),由于是顺序树,则6经过旋转后新节点最终位置仍应在6右侧、7左侧,旋转后6的右子树非空,所以要将节点插入7的左侧,最后将2直接左下旋转即可。


人贵有自知之明。