---

目录 start

1. 树
   1. 二叉树
   2. 二叉查找树
   3. AVL树
   4. B-Tree
   5. B+Tree
   6. 红黑树

目录 end|2020-11-16 12:11|

---

平衡二叉查找树

最早提出的数据结构, 应用不甚广泛, Windows对进程地址空间的管理有使用到 AVL 树

用在磁盘文件数据索引和数据库索引等

对称二叉 B 树

广泛使用在各种语言的基本容器中, Java 的 TreeSet TreeMap HashMap, C++ 的 map set

红黑树具有以下5种性质：

1. 节点是红色或黑色。
2. 根节点是黑色。
3. 每个叶节点（NIL节点，空节点）是黑色的。
4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树的时间复杂度为O(log n)，与树的高度成正比。 红黑树每次的插入、删除操作都需要做平衡，平衡时有可能会改变根节点的位置，颜色转换，左旋，右旋等。