- Red-Black Tree
A red-black Tree is a self-balanced binary search Tree, known as a symmetric binary B Tree. It can find, insert, and delete in order (logn) time, where n is the number of elements in the tree.
Nodes in a red-black tree, one class is marked black and one class is marked red. In addition, a red-black tree needs to meet several requirements:
(1) The root node is black;
(2) Every leaf node is black and NIL, that is, the leaf node does not store data;
(3) No adjacent nodes can be red at the same time, that is, red nodes are separated by black nodes;
(4) All [simple paths] from any node to each of its leaves contain the same number of black nodes.
These constraints ensure the key properties of red-black trees: the shortest possible paths are all black nodes, and the longest possible paths have alternating red and black nodes. The longest possible path from root to leaf is no more than twice as long as the shortest possible path. The result is that the tree is roughly balanced. Because the worst-case times for operations such as inserting, deleting, and finding a value are required to be proportional to the height of the tree, this theoretical upper limit on height allows red-black trees to be efficient in worst-case scenarios.
The performance of many operations on binary lookup trees is proportional to the height of the tree. The height of a perfectly balanced binary tree (full or complete) is about log base 2n, so if we want to prove that a red-black tree is approximately balanced, we just need to analyze whether the height of a red-black tree tends to log base 2n steadily.
If we remove red nodes from a red-black tree, the height of a quadtree containing only black nodes is smaller than the height of a complete binary tree containing the same number of nodes. The height of a complete binary tree is approximately log2n, and the quad “black tree” here is lower than the height of the complete binary tree, so the “black tree” with the red nodes removed is no higher than log2n:
Because each red-black tree is also a specialized binary lookup tree, the read-only operations on red-black trees are the same as those on ordinary binary lookup trees. However, inserting and deleting on a red-black tree results in a loss of compliance with the red-black tree’s properties, which requires a small O(logn) color change (which is actually very fast) and no more than three tree rotations (two for inserts). The operation time of red-black tree insertion and deletion can remain O(logn) times.
- Red black tree vs AVL tree vs skip table
AVL tree is a highly balanced binary tree, so the search efficiency is very high. However, there are advantages and disadvantages, and AVL tree has to pay more costs in order to maintain such a high balance. Each insertion and deletion needs to be adjusted, which is complicated and time-consuming. Therefore, AVL trees can be a bit expensive for data sets with frequent insert and delete operations. Red-black trees are approximately balanced, not strictly balanced, so the cost of maintaining equilibrium is lower than AVL trees.
Because red-black tree is a binary search tree with very stable performance, it can be used in projects where dynamic insertion, deletion and data search are used. However, it is more complicated to implement, if you write your own code implementation, it will be a bit more difficult, this time, in fact, prefer to use hops instead of it.
- Red – black tree insertion and deletion