树 二叉搜索树 平衡二叉搜索树 AVL树 红黑树

java

树

1. 树的导览

树由节点（Nodes）和 边（edges）构成。树有根节点（root），边（deges），父节点（parent），子节点（child），叶节点（leaf）。如果最多只允许两个子节点，即所谓的二叉树（binary tree）。不同的节点如果拥有相同的父节点，则彼此互为兄弟节点（siblings）。根节点至任何节点之间有唯一路径（path），路径所经过的边数，成为路径长度（length）。根节点至任一节点的路径长度，即所谓该节点的深度（depth）。根节点的深度永远是0。 某节点至其最深子节点（叶节点）的路径长度，成为该节点的高度（height）。整棵树的高度，便以根节点的高度来代表。节点A->B 之间如果存在（唯一）一条路径，那么A 称为B的祖代（ancestor），B称为A的子代（descendant）。任何节点的大小（size）是指其所有子代（包括自己）的节点总数。

1.1 二叉搜索树（binary search tree）

所谓二叉树（binary tree），其意义是：“任何节点最多只允许两个子节点”。称为左子节点和右子节点。二叉搜索树可提供对数时间的元素插入和访问。二叉搜索树的节点放置规则是：任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中每一个节点的键值。因此，从根节点一直往左走，直至无左路可走，即得最小元素；从根节点一直往右走，直至无右路可走，即得最大元素。

1.2 平衡二叉搜索树（balanced binary search tree）

也许因为输入值不够随机，也许因为经过某些插入或删除操作，二叉搜索树可能会失去平衡，造成搜寻效率低落的情况。

所谓树形平衡与否，并没有一个绝对的测量标准。“平衡”的大致意义是：没有任何一个节点过深（深度过大）。不同的平衡条件，造就出不同的效率表现，以及不同的实现复杂度。有数种特殊结构如AVL-tree， RB-tree、AA-tree ，均可实现出平衡二叉搜索树。

1.3 AVL tree （Adelson-Velskii-Landis tree）

AVL tree 是一个“加上了额外平衡条件”的二叉搜索树。其平衡条件的建立是为了确保整棵树的深度为O(logN)。直观上的最佳平衡条件是每个节点的左右子树有着相同的高度，但这未免太过苛刻，我们很难插入新元素而又保持这样的平衡条件。AVL tree 于是退而求其次，要求任何节点的左右子树高度相差最多1。这是一个较弱的条件，但仍能够保证“对数深度”平衡状态。

只要调整“插入点之根节点”路径上，平衡状态被破坏之个节点中最深的那一个，便可使整棵树重新获得平衡。假设该最深节点为X，由于节点最多拥有两个子节点，而所谓“平衡被破坏”意味着X的左右两棵子树的高度相差2，因此我们可以轻易将情况分为四种：

（1）插入点位于X的左子节点的左子树——左左；

（2）插入点位于X的左子节点的右子树——左右；

（3）插入点位于X的右子节点的左子树——右左 ；

（4）插入点位于X的右子节点的右子树——右右 。

情况1、4彼此对称，成为外侧插入，可采用单旋转操作调整解决。

情况2、3彼此对称，成为内侧插入，可采用双旋转调整解决。

一、红黑树的介绍

先来看下算法导论对R-B Tree的介绍： 红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

红黑树，作为一棵二叉查找树，满足二叉查找树的一般性质。下面，来了解下 二叉查找树的一般性质。

二叉查找树

二叉查找树，也称有序二叉树（ordered binary tree），或已排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 任意节点的左、右子树也分别为二叉查找树。 没有键值相等的节点（no duplicate nodes）。  因为一棵由n个结点随机构造的二叉查找树的高度为lgn，所以顺理成章，二叉查找树的一般操作的执行时间为O(lgn)。但二叉查找树若退化成了一棵具有n个结点的线性链后，则这些操作最坏情况运行时间为O(n)。

红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

但它是如何保证一棵n个结点的红黑树的高度始终保持在logn的呢？这就引出了红黑树的5个性质：

（1）每个结点要么是红的要么是黑的。

（2）根结点是黑的。

（3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。

（4）如果一个结点是红的，那么它的两个儿子都是黑的。

（5）对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度，从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论成立的原因。

（注：上述第3、5点性质中所说的NULL结点，包括wikipedia.算法导论上所认为的叶子结点即为树尾端的NIL指针，或者说NULL结点。然百度百科以及网上一些其它博文直接说的叶结点，则易引起误会，因此叶结点非子结点）

如下图所示，即是一颗红黑树(下图引自wikipedia：http://t.cn/hgvH1l)：

此图忽略了叶子和根部的父结点。同时，上文中我们所说的 "叶结点" 或"NULL结点"，如上图所示，它不包含数据而只充当树在此结束的指示，这些节点在绘图中经常被省略，望看到此文后的读者朋友注意。

二、树的旋转知识

当在对红黑树进行插入和删除等操作时，对树做了修改可能会破坏红黑树的性质。为了继续保持红黑树的性质，可以通过对结点进行重新着色，以及对树进行相关的旋转操作，即通过修改树中某些结点的颜色及指针结构，来达到对红黑树进行插入或删除结点等操作后继续保持它的性质或平衡的目的。

树的旋转分为左旋和右旋，下面借助图来介绍一下左旋和右旋这两种操作。

1.左旋

如上图所示，当在某个结点pivot上，做左旋操作时，我们假设它的右孩子y不是NIL[T]，pivot可以为任何不是NIL[T]的左子结点。左旋以pivot到Y之间的链为“支轴”进行，它使Y成为该子树的新根，而Y的左孩子b则成为pivot的右孩子。

2.右旋
右旋与左旋差不多，再此不做详细介绍。

树在经过左旋右旋之后，树的搜索性质保持不变，但树的红黑性质则被破坏了，所以，红黑树插入和删除数据后，需要利用旋转与颜色重涂来重新恢复树的红黑性质。

至于有些书如《STL源码剖析》有对双旋的描述，其实双旋只是单旋的两次应用，并无新的内容，因此这里就不再介绍了，而且左右旋也是相互对称的，只要理解其中一种旋转就可以了。

https://www.cnblogs.com/yyxt/p/4983967.html