数据结构 – 树

二叉排序树

• 特点：
  • 左子树小于根节点，右子树大于根节点。
  • 左子树和右子树都是二叉排序树。
• 问题：可能出现不平衡，退化成链表，导致查询性能从log(n)退化成n。

平衡二叉排序树

• 在二叉排序树基础上增加约束条件。
• 插入和删除时做少量调整，使树保持相对平衡。
• 其实现主要有 AVL 树和红黑树。

AVL 树

• 最早发明的平衡二叉排序树，命名来源于发明者的首字母。
• 在二叉排序树基础上增加约束条件：左右子树的高度差最多为 1。
• 问题：插入和删除时几乎都要旋转，频繁旋转导致性能下降。

红黑树

• 二叉排序树有不平衡问题，可能左子树很长右子树很短，导致查询性能从log(n)退化成n。
• AVL树能保证层数平均，但是维护又很麻烦，插入和删除都可能需要大幅调整树结构。
• 红黑树是一种相对平衡的二叉排序树。
• 约束条件：
  • 节点赋予红黑颜色。
  • 根节点为黑色。
  • 新插入的节点为红色。
  • 每个红色节点的两个子节点是黑色。
  • 任意节点到叶子节点的所有路径包含相同数目的黑色节点。
• 特点：
  • 插入时不超过 2 次旋转就可以符合约束条件。
  • 删除时不超过 3 次旋转就可以符合约束条件。
  • 故查询、插入和删除的复杂度都是log(n)。
• 应用：
  • java 的 hashmap。
  • linux 的进程调度。
  • linux 的多路复用 Epoll。

红黑树插入过程示例：

B树

• B 树是平衡多路查找树。
• 相比于二叉排序树，B 树增加节点分支数量从而降低深度。
• 适用场景：对于磁盘存储的数据，较低的深度可以减少 IO 次数。
• 约束条件：
  • 叶子节点都在同一层。
  • 节点的关键字数是子树个数减 1。
  • 子树的关键字保证左小右大的顺序。
• 缺点：节点上存储数据，当数据较大时节点的键数会减少，导致层高变高。

B+树

• 是对B树的改进，目的是降低树深度，容易全表扫描。
• 与B树在结构上的区别：
  • 只在叶子节点存储数据，非叶子节点只存储索引键。
  • 所有叶子节点之间通过指针串起来形成链表。
• 与B树在操作上的区别：
  • 插入时会先将数据插入到叶子节点中，然后再调整树结构。
  • 查询时需经过从根到叶子的路径。
• 应用：数据库索引，如 mysql 的 InnoDB的索引实现。

字典树

• 定义：一种用于存储和检索字符串集合的字典树。
• 特点：
  • 利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。
  • 每个结点代表一个字符，从根到叶子节点形成一个字符串。
• 应用：词频统计。

基数树

• 定义：一种压缩的字典树，相比于字典树，如果节点只有一个子节点则会合起来。
• 对比字典树的优势：更加节省空间，深度更低查找效率更高。
• 对比字典树的劣势：构造树时需要更多地处理分裂。
• 应用：路由查找。