java排序--平衡二叉树

r囧r小猫 2022-09-20 05:48 161阅读 0赞

概念:

平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。构造与调整方法 平衡二叉树的常用[算法][Link 1]有红黑树、AVL、[Treap][]、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的[数列][Link 2]，可以参考Fibonacci数列 1是根节点 F(n-1)是左子树的节点数量 F(n-2)是右子数的节点数量。

1作用

我们知道，对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度（O(log2n)）同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过 [随机化][Link 3] 建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的 [时间复杂度][Link 4] 。

[平衡二叉搜索树][Link 5] （Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。常用算法有红黑树、AVL、Treap、伸展树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O（log2n），大大降低了操作的时间复杂度。

## 2算法 ##

### 红黑树 ###

**红黑树**是一种自平衡二叉查找树，是在 [计算机科学][Link 6] 中用到的一种 [数据结构][Link 7] ，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，他称之为"对称二叉B树"，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。

### AVL ###

**AVL**是最先发明的自平衡二叉查找树算法。在AVL中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

### Treap ###

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

### 伸展树 ###

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

### SBT ###

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

[Link 1]: http://baike.baidu.com/view/7420.htm
[Treap]: http://baike.baidu.com/view/956602.htm
[Link 2]: http://baike.baidu.com/view/39749.htm
[Link 3]: http://baike.baidu.com/view/1587523.htm
[Link 4]: http://baike.baidu.com/view/104946.htm
[Link 5]: http://baike.baidu.com/view/2315698.htm
[Link 6]: http://baike.baidu.com/view/92404.htm
[Link 7]: http://baike.baidu.com/view/9900.htm
[Link 8]: http://baike.baidu.com/view/249120.htm
[Link 9]: http://baike.baidu.com/view/668854.htm
[Link 10]: http://baike.baidu.com/view/427107.htm
[Link 11]: http://baike.baidu.com/view/1695291.htm
[Link 12]: http://baike.baidu.com/view/61891.htm
[Link 13]: http://baike.baidu.com/view/7340.htm
[Link 14]: http://baike.baidu.com/view/93561.htm
[Link 15]: http://baike.baidu.com/view/553911.htm
[Link 16]: http://baike.baidu.com/view/1065277.htm
[ACM_ICPC]: http://baike.baidu.com/view/94274.htm
[B]: http://baike.baidu.com/view/298408.htm
[Link 17]: http://baike.baidu.com/view/389453.htm
[select]: http://baike.baidu.com/view/621719.htm
[rank]: http://baike.baidu.com/view/1604393.htm