Abstract Self-Balancing Binary Search Tree

阳光穿透心脏的1/2处 2022-04-08 11:47 146阅读 0赞

# 二叉搜索树 #

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。  
具体介绍和实现：[https://blog.csdn.net/hebtu666/article/details/81741034][https_blog.csdn.net_hebtu666_article_details_81741034]

我们知道，对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度（O(log2n)）同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，

此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过[随机化][Link 1]建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的[时间复杂度][Link 2]。

# 概念引入 #

Abstract Self-Balancing Binary Search Tree：自平衡二叉搜索树

顾名思义：它在面对任意节点插入和删除时自动保持其高度

常用算法有红黑树、AVL、Treap、伸展树、SB树等。在平衡二叉搜索树中，我们可以看到，其高度一般都**良好地维持在O（log（n））**，大大降低了操作的时间复杂度。这些结构为可变有序[列表][Link 3]提供了有效的实现，并且可以用于其他[抽象数据结构，][Link 4]例如[关联数组][Link 5]，[优先级队列][Link 6]和[集合][Link 7]。

对于这些结构，他们都有自己的平衡性，比如：

### AVL树 ###

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

根据定义可知，这是根据深度最严苛的标准了，左右子树高度不能差的超过1.

具体介绍和实现：[https://blog.csdn.net/hebtu666/article/details/85047648][https_blog.csdn.net_hebtu666_article_details_85047648]

### 红黑树 ###

特性:  
（1）每个节点或者是黑色，或者是红色。  
（2）根节点是黑色。  
（3）每个叶子节点（NIL）是黑色。 \[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！\]  
（4）如果一个节点是红色的，则它的子节点必须是黑色的。  
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

根据定义，确保没有一条路径会比其他路径长出2倍。

### size balance tree ###

**Size Balanced Tree**（简称**SBT**）是一自平衡二叉查找树，是在计算机科学中用到的一种数据结构。它是由中国广东[中山纪念中学][Link 8]的陈启峰发明的。陈启峰于2006年底完成论文《Size Balanced Tree》，并在2007年的[全国青少年信息学奥林匹克竞赛][Link 9]冬令营中发表。由于SBT的拼写很容易找到中文谐音，它常被中国的信息学竞赛选手和[ACM/ICPC][ACM_ICPC]选手们戏称为“傻B树”、“Super BT”等。相比红黑树、AVL树等自平衡二叉查找树，SBT更易于实现。据陈启峰在论文中称，SBT是“目前为止速度最快的高级二叉搜索树”。SBT能在O(log n)的时间内完成所有[二叉搜索树][Link 10]（BST）的相关操作，而与普通二叉搜索树相比，SBT仅仅加入了简洁的核心操作**Maintain**。由于SBT赖以保持平衡的是size域而不是其他“无用”的域，它可以很方便地实现动态顺序统计中的[select][]和[rank][]操作。

对于SBT的每一个结点 t,有如下性质：  
性质(a) s\[ right\[t\] \]≥s\[ left \[ left\[ t \] \] \], s\[ right \[ left\[t\] \] \]  
性质(b) s\[ left\[t\] \]≥s\[right\[ right\[t\] \] \], s\[ left\[ right\[t\] \] \]  
即.**每棵子树的大小不小于其兄弟的子树大小。**

### 伸展树 ###

**伸展树**（Splay Tree）是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的[冗余信息][Link 11]。在**伸展树**上的一般操作都基于伸展操作。

### Treap ###

**Treap**是一棵二叉排序树，它的左子树和右子树分别是一个**Treap**，和一般的二叉排序树不同的是，**Treap**纪录一个额外的数据，就是优先级。**[Treap][]**在以关键码构成二叉排序树的同时，还满足[堆][Link 12]的性质(在这里我们假设节点的优先级大于该节点的孩子的优先级)。但是这里要注意的是**Treap**和[二叉堆][Link 13]有一点不同，就是二叉堆必须是[完全二叉树][Link 14]，而**Treap**并不一定是。

**对比可以发现，AVL树对平衡性的要求比较严苛，每插入一个节点就很大概率面临调整。**

**而红黑树对平衡性的要求没有那么严苛。可能是多次插入攒够了一下调整。。。**

把每一个树的细节都扣清楚是一件挺无聊的事。。虽然据说红黑树都成了面试必问内容，但是实在是不想深究那些细节，这些树的**基本操作也无非是那么两种：左旋，右旋**。这些树的所有操作和情况，都是这两种动作的组合罢了。

所以本文先介绍这两种基本操作，等以后有时间（可能到找工作时），再把红黑树等结构的细节补上。

# 最简单的旋转 #

最简单的例子：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70][]

这棵树，左子树深度为2，右子树深度为0，所以，根据AVL树或者红黑树的标准，它都不平衡。。

那怎么办？转过来：

![20181214211057789.png][]

![20181214210359653.png][]

是不是就平衡了？

这就是我们的顺时针旋转，又叫，右旋，因为是以2为轴，把1转下来了。

左旋同理。

# 带子树旋转 #

问题是，真正转起来可没有这么简单：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1][]

这才是一颗搜索树的样子啊

ABCD都代表是一颗子树。我们这三个点转了可不能不管这些子树啊对不对。

好，我们想想这些子树怎么办。

![20181214211249447.png][]

首先，AB子树没有关系，放在原地即可。

![2018121421134383.png][]

D作为3的右子树，也可以不动，那剩下一个位置，会不会就是放C子树呢？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 2][]

我们想想能否这样做。

原来：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1][]

1）C作为2的右子树，内任何元素都比2大。

2）C作为3左子树的一部分，内任何元素都比3小。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 2][]

转之后：

1）C作为2的右子树的一部分，内任何元素都比2大。

2）C作为3左子树，内任何元素都比3小。

所以，C子树可以作为3的左子树，没有问题。

这样，我们的操作就介绍完了。

这种基本的变换达到了看似把树变的平衡的效果。

左右旋转类似

# 代码实现 #

对于Abstract BinarySearchTree类，上面网址已经给出了思路和c++代码实现，把java再贴出来也挺无趣的，所以希望大家能自己实现。

抽象自平衡二叉搜索树（AbstractSelfBalancingBinarySearchTree）的所有操作都是建立在二叉搜索树（BinarySearchTree ）操作的基础上来进行的。

各种自平衡二叉搜索树（AVL、红黑树等）的操作也是由Abstract自平衡二叉搜索树的基本操作：左旋、右旋构成。这个文章只写了左旋右旋基本操作，供以后各种selfBalancingBinarySearchTree使用。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1][]

public abstract class AbstractSelfBalancingBinarySearchTree extends AbstractBinarySearchTree {
        protected Node rotateRight(Node node) {
            Node temp = node.left;//节点2
            temp.parent = node.parent;
            //节点3的父(旋转后节点2的父)
            node.left = temp.right;
            //节点3接收节点2的右子树
            if (node.left != null) {
                node.left.parent = node;
            }
    
            temp.right = node;
            //节点3变为节点2的右孩子
            node.parent = temp;
    
            //原来节点3的父（若存在），孩子变为节点2
            if (temp.parent != null) {
                if (node == temp.parent.left) {
                    temp.parent.left = temp;
                } else {
                    temp.parent.right = temp;
                }
            } else {
                root = temp;
            }
            return temp;
        }
    
        protected Node rotateLeft(Node node) {
            Node temp = node.right;
            temp.parent = node.parent;
            node.right = temp.left;
            if (node.right != null) {
                node.right.parent = node;
            }
            temp.left = node;
            node.parent = temp;
            if (temp.parent != null) {
                if (node == temp.parent.left) {
                    temp.parent.left = temp;
                } else {
                    temp.parent.right = temp;
                }
            } else {
                root = temp;
            }
            
            return temp;
        }
    }

[https_blog.csdn.net_hebtu666_article_details_81741034]: https://blog.csdn.net/hebtu666/article/details/81741034
[Link 1]: https://baike.baidu.com/item/%E9%9A%8F%E6%9C%BA%E5%8C%96
[Link 2]: https://baike.baidu.com/item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6
[Link 3]: https://en.wikipedia.org/wiki/List_%28computing%29
[Link 4]: https://en.wikipedia.org/wiki/Abstract_data_structure
[Link 5]: https://en.wikipedia.org/wiki/Associative_arrays
[Link 6]: https://en.wikipedia.org/wiki/Priority_queue
[Link 7]: https://en.wikipedia.org/wiki/Set_%28computer_science%29
[https_blog.csdn.net_hebtu666_article_details_85047648]: https://blog.csdn.net/hebtu666/article/details/85047648
[Link 8]: https://baike.baidu.com/item/%E4%B8%AD%E5%B1%B1%E7%BA%AA%E5%BF%B5%E4%B8%AD%E5%AD%A6
[Link 9]: https://baike.baidu.com/item/%E5%85%A8%E5%9B%BD%E9%9D%92%E5%B0%91%E5%B9%B4%E4%BF%A1%E6%81%AF%E5%AD%A6%E5%A5%A5%E6%9E%97%E5%8C%B9%E5%85%8B%E7%AB%9E%E8%B5%9B
[ACM_ICPC]: https://baike.baidu.com/item/ACM%2FICPC
[Link 10]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91
[select]: https://baike.baidu.com/item/select
[rank]: https://baike.baidu.com/item/rank
[Link 11]: https://baike.baidu.com/item/%E5%86%97%E4%BD%99%E4%BF%A1%E6%81%AF
[Treap]: https://baike.baidu.com/item/Treap
[Link 12]: https://baike.baidu.com/item/%E5%A0%86
[Link 13]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E5%A0%86
[Link 14]: https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70]: /images/20220405/85521926c79f40288398cf6da9d1e135.png
[20181214211057789.png]: /images/20220405/0313360af2914b268fc6363c472596cb.png
[20181214210359653.png]: /images/20220405/5e126c8c020a4f22934d4d493ec201fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1]: /images/20220405/a5c635109d5e4c8cbd58f828b662f423.png
[20181214211249447.png]: /images/20220405/51c8f3b5f73d4abea901c72dfaf4ef10.png
[2018121421134383.png]: /images/20220405/298bfc07e04549f8ad568e7799ba5d23.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 2]: /images/20220405/7058daedbb1e43b1aa3cc252a2948ad3.png