[Algo] Red-Black tree

 Binary Search Tree：

AKA : ordered binary tree/sorted binary tree 

https://github.com/jianfeipan/LeetCode/tree/main/graph/tree/BST

二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升

如果可以让树维持平衡，也就是让h维持在${\displaystyle O(\log {n})}$的左右，就可以在${\displaystyle O(\log {n})}$的复杂度内完成各种基本操作

--> 

Self-balancing Binary Search Tree

The most famous self-balanceing BST is 

Red-Black tree

std::set<T>

https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在${\displaystyle {\text{O}}(\log n)}$时间内完成查找、插入和删除，这里的${\displaystyle n}$是树中元素的数目。

1. 节点是红色或黑色。
2. 根是黑色。
3. 所有叶子都是黑色（叶子是NIL节点）。
4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

Basic operation : Tree rotation

 

insertion : https://en.wikipedia.org/wiki/Red%E2%80%93black_tree