红黑树

作者：杨云召

日期：2023-10-21

版本	日期	提交人	说明
v1.0	2023-10-21	杨云召	初始版本

理论

• 每个节点，不是红节点，就是黑节点
• 根节点必须是黑节点
• 如果一个节点是红的，那么两个儿子都是黑的
• 对任意节点，从该节点到所有叶子节点的路径上，黑点个数相同
• 新插入的为红节点（后期可能调整）

• 不同于AVL树，不需要维持整个树高度差，而是维护黑节点高度差。目的是减少插入、删除时的旋转次数

• 上图中黑色空节点可以省略

删除红色节点后，完全四叉树