二叉树
- 只有一个根节点
- 每个根节点至多有两个子节点
二叉树.png
查找二叉树
- 满足二叉树全部定义
- 当前节点的任意左子节点必须小于自身,任意右子节点需大于自身
查找二叉树.png
平衡查找二叉树(AVL)
- 满足查找二叉树的全部定义
- 左右子树高度差不得超过1
- 不满足第二点时进行旋转
平衡查找二叉树.png
旋转类型
左旋
左旋.png
右旋
右旋.png
失衡情况
左左失衡 (右旋)
参考右旋
左右失衡 (先左旋 再右旋)
左右失衡.png
右右失衡(左旋)
参考左旋图
右左失衡(先右旋 再左旋)
右左失衡.png
红黑树
- 弱平衡查找二叉树(不要求满足高度差<=1)
- 每个节点或者是黑色，或者是红色
- 根节点是黑色。
- 每个叶子节点是黑色,叶子节点是NIL。
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
