关于二叉查找树，我们知道他在理想的情况下，各操作时间复杂度是O(logn)，但是他可能会退化成链表，这是时间复杂度就会变高，这是我们需要把它变成平衡的二叉树

1. 什么是“平衡二叉查找树”

定义：二叉树中任意一个节点的左右子树的高度相差不能大于 1

**

要解决的问题：普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题


2. 有哪些平衡二叉查找树

AVL树、红黑树、Splay Tree（伸展树）、Treap（树堆）…

3. 什么是红黑树

红黑树中的节点，一类被标记为黑色，一类被标记为红色

903ee0dcb62bce2f5b47819541f9069a.jpg

而且还需要满足以下要求：

  • 根节点是黑色的；
  • 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
  • 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
  • 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

红黑树的高度近似 log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)