数据结构-红黑树（平衡二叉查找树）
-
平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于1。
-
平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点，最先被发明的平衡二叉查找树是AVL树，它严格符合我刚讲到的平衡二叉查找树的定义，即任何节点的左右子树高度相差不超过1，是一种高度平衡的二叉查找树。
-
很多平衡二叉查找树并没有严格满足上面的定义，比如红黑树，它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。
-
什么是红黑树
红黑树是一种自平衡的二叉树查找树，需要满足以下5个条件
从根节点到最长的叶子节点距离不能大于比到最短的叶子节点距离的2倍。 -
红黑树通过什么方式来保持平衡
- 变色
- 左右旋转的方式
- AVL树与红黑树比较
AVL树是完全平衡的二叉树，而红黑树是较为平衡的二叉树，相对于AVL红黑树更加的稳定，尽管AVL比红黑树查询效率要高，但是在删除或者新增元素的时候，要继续保持平衡所花费的时间会更多，因为红黑树更加稳定。