二叉树PLUS(搜索树、平衡树)
搜索树
二叉搜索树(Binary Search Tree,BST)是一种常见的二叉树数据结构,它在二叉树的基础上多了一下几个特点:
条件一:对于任意节点,其左子树中的所有节点的值都小于该节点的值,而右子树中的所有节点的值都大于该节点的值。
条件二:如果满足条件一,那么对搜索树进行中序遍历,就会得到一个有序的序列。
1 | 搜索树 |
中序遍历:1 3 4 6 7 8 10 13 14
可以看到这颗二叉树任意节点都大于的左子树上的节点,小于右子树上的节点
构建搜索树
在构建搜索树时,按照条件一对元素进行插入就可以,但是在极端情况下搜索树会变成链表,这种情况就是使用有序序列构建搜索树时
1 | //序列 1 3 4 6 7 8 10 13 14 |
可以看到这棵树变成了链表,为了避免这种情况,后面诞生了平衡搜索树
基础操作
搜索树实际上维护了一个有序的序列,我们对照有序数组看看两者的插入和删除操作有什么不同。
有序数组
对数组中的元素进行插入和删除操作,第一步就是先找到这个元素,使用二分查找可以很快找到需要插入的元素位置O(log n)
,然后插入时需要把后面的对象依次向后移动,这里时间复杂度为O(n)
级别的,删除操作需要把该元素后面的对象依次向前移动,时间复杂度还是O(n)
。
1 | 1 3 4 6 7 8 10 13 14 |
搜索树
在比较平衡的搜索树中找到这个元素的效率和有序数组一样O(log n)
,但是在删除时不需要移动那么多元素,插入时更是不需要移动元素。所以搜索树是一种插入删除高效的数据结构
1 | 8 |
删除
上面的插入操作很好理解,现在看一下删除,删除一个节点后要如何处理该节点的子节点呢?
删除规则:用删除节点的左子树最大节点替换该节点,或者使用删除节点的右子树最小节点替换该节点
为什么要这样做呢?我们看一下下面这个序列:
1 | 1 3 4 6 [7] 8 [10] 13 14 |
现在要删除根节点8,按照上面的规则其实就会选出最接近删除节点的元素替换它。左子树就会选出7,右子树会选出10,按照这样的规则删除的好处是避免移动过多的节点。
AVL树
AVL树也叫平衡二叉树,是由两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明的,为了纪念他们,将平衡二叉树称为 AVL树。
AVL树满足的条件:
条件一:是一颗二叉搜索树。
条件二:每个节点的左子树和右子树的高度最多相差1,即任何节点的平衡因子(左子树高度减去右子树高度的绝对值)不超过1。
条件三:每个节点的左子树和右子树都是AVL树。
平衡因子(Balance Factor):节点的平衡因子其实就是左子树高度与右子树高度的差的绝对值
$$
BF = 左子树高度 - 右子树高度
$$
1 | 1 |
基本操作
AVL树也是一颗二叉搜索树,所以查找、插入、删除操作和二叉树基本一样,唯一需要注意的是再删除和插入后需要保证AVL树的平衡,就是保证节点的平衡因子为小于等于1
左旋
让该节点成为它右子节点的左子节点
冲突情况:如果左旋的节点与右子节点的左子节点发生冲突,就让原来位置的节点成为左旋节点的右子节点。
对于这颗不平衡的二叉搜索树(节点1的平衡因子是-2),可以通过左旋来实现平衡
1 | [1] |
现在来看一下复杂的情况,对于下面这颗树,如果还是左旋,节点1和节点2就会发生冲突
1 | [1] 3 |
对于左旋操作,冲突的节点变成旋转节点的右孩子
右旋
让该节点成为它左子节点的右子节点
冲突情况:如果左旋的节点与左子节点的右子节点发生冲突,就让原来位置的节点成为右旋节点的左子节点。
对于这颗不平衡的二叉搜索树(节点4的平衡因子是2),可以通过右旋来实现平衡
1 | [4] |
现在来看一下复杂的情况,对于下面这颗树,如果还是左旋,节点1和节点2就会发生冲突
1 | [4] 2 |
对于右旋操作,冲突的节点变成旋转节点的左孩子
插入节点破坏平衡后的四种旋转情况
LL(失衡节点的左子树,发生左失衡)
失衡节点:平衡因子 = 2
失衡节点左子节点:平衡因子 = 1
恢复平衡方法:失衡节点右旋
1 | [14] |
我们来看一下上面这颗树,节点3的加入,导致搜索树不平衡,这时候14节点的平衡因子 = 2
,6节点的平衡因子 = 1
,这种情况只需要对14节点右旋就可以恢复平衡。
RR(失衡节点的右子树,发生右失衡)
失衡节点:平衡因子 = -2
失衡节点右子节点:平衡因子 = -1
恢复平衡方法:失衡节点左旋
1 | [5] |
我们来看一下上面这颗树,节点17的加入,导致搜索树不平衡,这时候节点5的平衡因子 = -2
,9节点的平衡因子 = -1
,这种情况只需要对节点5左旋就可以恢复平衡。
LR(失衡节点的左子树,发生右失衡)
失衡节点:平衡因子 = 2
失衡节点左子节点:平衡因子 = -1
恢复平衡方法:失衡节点左子节点左旋,失衡节点右旋
1 | [9] [9] 8 |
我们来看一下上面这颗树,节点6的加入,导致搜索树不平衡,这时候节点9的平衡因子 = 2
,5节点的平衡因子 = -1
,这种情况先对节点5左旋,然后对节点9右旋,就可以恢复平衡。
RL(失衡节点的右子树,发生左失衡)
失衡节点:平衡因子 = -2
失衡节点右子节点:平衡因子 = 1
恢复平衡方法:失衡节点右子节点左旋,失衡节点左旋
1 | [5] [5] 6 |
我们来看一下上面这颗树,节点8的加入,导致搜索树不平衡,这时候节点5的平衡因子 = -2
,9节点的平衡因子 = 1
,这种情况先对节点9右旋,然后对节点5左旋,就可以恢复平衡。
插入时多个节点失衡
插入节点时如果多个节点都失衡,则调整距离插入节点最近的失衡节点,注意这里只需要调整一次
1 | [1] |
失衡节点:1节点平衡因子 = -2
,3节点平衡因子 = -2
恢复平衡方法:调整距离插入节点5最近的节点3,对节点3进行左旋
删除节点失衡,调整好导致多次失衡
删除节点和插入有一点不同,删除节点,需要依次对祖先节点进行检查,如果失衡就需要调整,这时候我们就需要调整多次节点。
1 | 11 |
在这棵AVL中删除节点5,此时节点7的平衡因子= -2
,我们可以通过左旋节点7来平衡树
1 | 11 |
此时会发现节点11的平衡因子= -2
,我们需要继续对节点11进行左旋
1 | 17 |
对节点11进行左旋,节点14发生冲突,把节点14变味节点11的右子节点,调整结束这就是一颗AVL树