Red-Black Trees

A red-black tree (RBT) is a binary search tree that satis¯es the following red-black properties:
1. Every node has a color that is either red or black.
2. Every leaf is black.
3. If a node is red, both children are black.
4. Every path from a given node down to any descendant leaf contains the same number of black nodes. The number of black nodes on such a path (not including the initial node but including leaves) is called the black-height (bh) of the node.
5. The root of the tree is black (not a CLR property, but should be).

Từ khóa: Red-Black Trees, điều khiểncấu trúc dữ liệu , ứng dụng máy tính, kỹ thuật máy tính, phần mềm ứng dụng, phần mềm cấu trúc dữ liệu , giao diện cấu trúc dữ liệu