owo
二叉查找树
- 是一个二叉树
- 对于每个节点，左子结点比自己小，右子节点比自己大
弊端：可能退化成链表，导致查询效率降低
平衡二叉树
是一个二叉查找树
对于每个节点，左子树和右子树高度相差不超过1
插入节点之后可能会破坏平衡，需要通过旋转恢复平衡
旋转规则详见网络
红黑树
- 二叉查找B树
- 不是高度平衡的
- 红黑规则
红黑规则
- 每一个节点是红色或黑色
- 根节点黑色
- 若一个节点无子节点或父节点，则这个节点属性值为Nil，视为叶节点，每个Nil叶节点是黑色的
（根节点无父节点） - 红色节点的子节点必须是黑色
- 对每个节点，从这个节点到所有后代叶子结点的简单路径上，包含相同数目的黑色节点
添加节点
- 添加的节点默认红色（效率高）
添加的节点为根
- 直接变为黑色
添加的节点非根
父为黑
- 不需要操作
父为红
叔叔红
- 父 -> 黑，叔 -> 黑
- 祖父 -> 红
- 若祖父为根，祖父 -> 黑
- 若祖父非根，祖父 -> 当前节点
叔叔黑，当前节点是父节点右儿子
- 将父节点作为当前节点并左旋，接着判断
叔叔黑，当前节点是父节点左儿子
- 父 -> 黑
- 祖父 -> 红
- 以祖父为支点右旋
优点
增删改查性能很好