GuangchaoSun's Blog

3.3 Balanced Search Trees

发表于  |    |   分类于   |  

2-3查找树

结点构成：

  • 2-结点，含有一个键（及其对应的值）和两条链接，左链接指向的2-3树的键都小于该结点，右链接指向的2-3树中的键都大于该结点。
  • 3-结点，含有两个键（及其对应的值）和三条链接，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点。

search:

在一颗大小为N的2-3树中，查找和插入操作访问的结点必然不超过lgN个。
所以说2-3树在最坏的情况下仍然具有良好的性能。

红黑二叉查找树

红黑二叉查找树背后的基本思想是用标准的二叉查找树（完全用2-结点构成）和一些额外的信息来表示2-3树。
替换3-链接：

  • 红链接将两个2-结点连接起来构成一个3-结点
  • 黑链接则是2-3树的普通链接

一一对应：如果我们将一颗红黑树中的红链接画平，那么所有空连接到根结点的距离总是相同的。
一种等价的定义：

  • 红链接均为左链接；
  • 没有任何一个结点同时和两条红链接相连；
  • 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。

左旋转h的右链接

1
2
3
4
5
6
7
8
9
10
Node rotateLeft(Node h){
	Node x = h.right;
	h.right = x.left;
	x.left = h;
	x.color = h.color;
	h.color = RED;
	x.N = h.N;
	h.N = 1 + size(h.left) + size(h.right);
	return x;
}

插入新键时可以使用旋转操作帮助我们保证2-3树和红黑树之间的一一对应关系，旋转操作可以保证红黑树的两个重要性质：有序性和完美平衡性。
插入操作：

  • 如果右子结点是红色而左子结点是黑色的，进行左旋转；
  • 如果左子结点是红色的且它的左子结点也是红色的，进行右旋转；
  • 如果左右子结点均为红色，进行颜色转换。

红黑树的插入算法RedBlackBST.java

红黑树的性质

结论：所有基于红黑树的符号表实现都能保证操作的运行时间为对数级别（范围查找除外，它所需的额外时间和返回的键的数量成正比）
一颗大小为N的红黑树的高度不会超过2lgN
一颗大小为N的红黑树中，根结点到任意结点的平均路径长度为~1.00lgN。

Creative Problems

  1. Fundamental theorem of rotations. Show that any BST can be transformed into any other BST on the same set of keys by a sequence of left and right rotations.
    Solution sketch: rotate the smallest key in the first BST to the root along the leftward spine; then recur with the resulting right subtree until you have a tree of height N (with every left link null). Do the same with the second BST. Remark: it is unknown whether there exists a polynomial-time algorithm for determining the minimum number of rotations needed to transform one BST into the other (even though the rotation distance is at most 2N - 6 for BSTs with at least 11 nodes).

Web Exercise

  1. Memory of a BST. What is the memory usage of a BST and RedBlackBST and TreeMap?
    Solution. MemoryOfBSTs.java.
  2. Randomized BST. Program RandomizedBST.java implements a randomized BST, including deletion. Expected O(log N) performance per operations. Expectation depends only on the randomness in the algorithm; it does not depend on the input distribution. Must store subtree count field in each node; generates O(log N) random numbers per insert.
    Proposition. Tree has same distribution as if the keys were inserted in random order.