Binary tree and red black tree
Someone can explain to me what is the difference between a red-black tree and a binary tree, I see the difference only in the fact that the red-black tree is marked with color, but it is not clear why to rebuild the tree when it becomes unbalanced, is it not possible to do the same in a binary tree without marking, I can also rebuild.
1 answers
Isn't it possible to do the same in a binary tree without marking
Theoretically, you can. But this can take a very long time. In order for the balancing to go faster, and enter special signs.
And red-black trees are not the only way to speed up the process. There are also, for example, AUL trees .
One of the differences (defining other characteristics) between the c / h and the AVL is that in the c / h for the storage of this additional information is enough for 1 bit (bitwise data packing can complicate the algorithm a little, but it saves a lot of memory, which is important in some cases). And in the AVL-the whole (if you do not go into details), which is not so modest, but allows you to balance a little faster.
Comparison of other characteristics of both types of trees by this link.
But in fact, both red-black and AVL trees are a kind of binary trees.