二叉平衡树
一、前言
二叉搜索树
二、AVL树
1.特征：二叉搜索树中，任意结点的左右子树高度之差的绝对值不能超过1
2.结点：类似搜索树（key，可以有value，left，right），还有（parent ，balanceFactor 平衡因子）
- 平衡因子：BF= H（右子树）- H（左子树）
- 一颗AVL树，每个结点的BF，可以选择的值为：1，0，-1
3.AVL树的插入过程
三、红黑树
2.
3.红黑树的插入
- 按照普通搜索树的方式进行插入
- 只会插入红色的结点
- 如果没有破坏规则，插入结束
- 否则，进行修复
修复，分情况讨论
最后，如果在插入过程中，根最后是红色的，要改成黑色
四、比较
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O()，红黑树不追求绝对平衡，其只 需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能 比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多
- 无论是AVL树还是红黑树，因为都是二叉的，所以，只适合内存数据的搜索