树（二叉树、二叉查找树、平衡二叉树、红黑树）
- 二叉查找树（二叉排序树、二叉搜索树）
- 添加元素
- 查找元素
- 遍历
- 弊端
- 平衡二叉树
- 旋转机制：左旋
- 旋转机制：右旋
- 需要旋转的四种情况
- 1. 左左：一次右旋
- 2. 左右：先局部左旋，再整体右旋
- 3. 右右：一次左旋
- 4. 右左：先局部右旋，再整体左旋
- 红黑树
- 红黑规则
- 添加节点的规则
来自黑马
树的演变：二叉树 → 二叉查找树 → 平衡二叉树
二叉查找树（二叉排序树、二叉搜索树）
添加元素
从根节点开始逐次比较：
查找元素
和添加一样，5首先和7比较，在7左边；然后和4比较，在4右边；然后和5比较，找到。
遍历
就是前中后序和层次遍历。
弊端
会高度不平衡：
此时如果要查询13，要一直查到最下面，显然不合理。一棵树如果要提高查询效率，需要左右差不多才行——平衡二叉树。
平衡二叉树
在二叉查找树的基础上又多了一条规则：任意节点左右子树高度差不超过1。
旋转机制：左旋
旋转触发时机：当添加一个节点之后，该树不再是一颗平衡二叉树。
更复杂的：
先不管9：
然后把9给降级的根节点7：
旋转机制：右旋
更复杂的：
需要旋转的四种情况
1. 左左：一次右旋
2. 左右：先局部左旋，再整体右旋
此时一次右旋无法平衡：
解决办法： 把根节点的左子树先局部左旋
然后再右旋即可：
3. 右右：一次左旋
4. 右左：先局部右旋，再整体左旋
红黑树
红黑树不是平衡二叉树：不需要满足高度差超过1，而需要满足红黑规则
红黑规则
添加节点的规则
这里具体的重点看B站黑马吧。。。
