Red Black Tree 红黑树 AVL trees 2-3 trees 2-3-4 trees B-trees Red-black trees Balanced search tree 平衡搜索树

This data structure requires an extra one-bit color field in each node.
Red-black properties:
1. Every node is either red or black.
2. The root and leaves (NIL’s) are black.
3. If a node is red, then its parent is black.
4. All simple paths from any node x to a descendant leaf have the same number of black nodes = black-height(x).

http://pages.cs.wisc.edu/~skrentny/cs367-common/readings/Red-Black-Trees/index.html

Recall that, for binary search trees, although the average-case times for the lookup, insert, and delete methods are all O(log N), where N is the number of nodes in the tree, the worst-case time is O(N). We can guarantee O(log N) time for all three methods by using a balanced tree -- a tree that always has height O(log N)-- instead of a binary search tree.

A number of different balanced trees have been defined, including AVL trees, 2-4 trees, and B trees. You might learn about the first two in an algorithms class and the third in a database class. Here we will look at yet another kind of balanced tree called a red-black tree.

The important idea behind all of these trees is that the insert and delete operations may restructure the tree to keep it balanced. So lookup, insert, and delete will always be logarithmic in the number of nodes but insert and delete may be more complicated than for binary search trees.

A red-black tree is a binary search tree in which

• each node has a color (red or black) associated with it (in addition to its key and left and right children)
• the following 3 properties hold:
  1. (root property) The root of the red-black tree is black
  2. (red property) The children of a red node are black.
  3. (black property) For each node with at least one null child, the number of black nodes on the path from the root to the null child is the same.

An example of a red-black tree is shown below:

https://baike.baidu.com/item/红黑树

它的统计性能要好于平衡二叉树(有些书籍根

红黑树

据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树)，因此，红黑树在很多地方都有应用。在C++ STL中，很多部分(包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。其他平衡树还有：AVL，SBT，伸展树，TREAP 等等。

树的左旋

树的右旋