二叉搜索树、平衡二叉树

阳光穿透心脏的1/2处 2023-10-18 22:26 56阅读 0赞

## 一、二叉搜索树 ##

这里我们不用太多书面化的语言来定义，笔者认为在讨论数据结构、算法相关的内容时用太多书面化、学术化的语言是一种让人很烦的事情。咬文嚼字，不便于读者理解。

简单来说二叉树搜索树，其实就是用来做二分查找的一种二叉树。

特点是：根节点的左子树值均小于根节点的值，根节点的右子树值均大于根节点的值。

比如123 4 567建树的结果就是

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70][]

### 插入操作 ###

(1)插入操作需要遍历二叉搜索树，  
  
(2)a 待插入元素的值小于当前结点的key值，则访问当前结点的 左子树  
  
b 待插入元素的值大于当前结点的key值，则访问当前结点的右子树  
  
c 待插入元素的值等于当前结点的key值，则返回false，表示该元素已存在

### 删除操作 ###

1、要删除的结点无孩子结点；

2、要删除的结点只有左孩子结点；

3、要删除的结点只有右孩子结点；

4、要删除的结点有左、右孩子结点；

以上的4种情况相应的删除方法如下：

a、直接删除该结点

b、删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点；

c、删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点；

d、在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除

### 退化问题 ###

还是以之前建立的树为例，我们继续有序的插入。可以明显看出，二叉树严重倾斜。如果一直插入，

整棵树的进行搜索的时间复杂度会从O(log2n)跌落到O(n)。渐渐从二分查找跌落为顺序查找。其实除了插入，删除操作也会造成这样的退化问题。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 1][]

## 二、平衡二叉树 ##

平衡二叉树的出现就是为了解决二叉搜索树在执行多次操作后可能会产生的退化问题。

它只是一种思想，有很多种实现，常见的实现有红黑树、AVL、Treap、伸展树等。

总的来说，平衡二叉树的特点就是：

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

经过严密的数学推导，已经验证，平衡二叉树的复杂度为：

![20190726160055155.png][]

是个指数函数，约等于O(log2n)。

### 旋转 ###

每当插入元素，造成二叉树不平衡以后，通过旋转的方式将树调整平衡。

注意！调整只调最小不平衡树！！！

插入的元素叫“破坏者”，最小不平衡树的根节点叫“被破坏者”。

有以下四种旋转情况：

“破坏者”在右子树的右子树，执行RR旋转，将“被破坏者”的右孩子提为根节点，该右孩子的左子树移植为“被破坏者”的右子树。

**（注：下面第一幅图，作图图有误，-1应该改为6.5）**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 2][]

“破坏者”在左子树的左子树，就执行LL旋转，将“被破坏者”压为“破坏者”父节点的右孩子，“破坏者”父节点往上走一层。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 3][]

破坏者在左子树的右子树，就执行LR旋转，步骤和LL旋转相似。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 4][]

破坏者在右子树的左子树执行RL旋转，调整被破坏者，被破坏者的R，以及被破坏者R的L（这里可能有点晕，其实仔细观察会发现其实就是契合右子树的左子树这个位置关系。），被破坏者的R提上，被破坏者的R的L不变。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 5][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190726142809500.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190726144018783.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg==,size_16,color_FFFFFF,t_70
[20190726160055155.png]: https://img-blog.csdnimg.cn/20190726160055155.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190726162351797.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20190726164003288.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20190726164612989.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20190726165819228.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg==,size_16,color_FFFFFF,t_70