红黑树
Many programming languages provide built-in support for tree-based sets and maps — for instance, Java’s TreeSet/TreeMap classes and the C++ Standard Template Library’s set and map classes
Binary Search Tree
a special type of tree that keeps elements sorted (but doesn’t guarantee efficient insertion and retrieval) (元素有序，但并不保证高效插入和取值)
Red-black Trees
Red-black trees are an evolution of binary search trees that aim to keep the tree balanced (保持树平衡) without affecting the complexity of the primitive operations. This is done by coloring each node in the tree with either red or black and preserving a set of properties that guarantee that the deepest path in the tree is not longer than twice the shortest one.
A red-black tree is a binary search tree with the following properties (有 5 个性质保持红黑树查询速度快):
- Every node is colored with either red or black.
- All leaf (nil) nodes are colored with black (叶子节点总是黑色); if a node’s child is missing then we will assume that it has a nil child in that place and this nil child is always colored black.
- Both children of a red node must be black nodes (红色节点的所有孩子都必须是黑色节点).
- Every path from a node n to a descendent leaf has the same number of black nodes (not counting node n). We call this number the black height of n, which is denoted by bh(n).