TS数据结构与算法之为何二叉树如此重要，而不是三叉树、四叉树？

注意事项

• 本节要“不求甚解”，掌握结果，不纠细节
• 你将体会计算机科学的精妙与伟大

性能，性能，还是性能

• 数组：查找快O(1)，增删慢O(n)
• 链表：查找慢O(n)，增删快O(1)
• 二叉搜索树BST：查找快，增删快 - “木桶效应”

二叉搜索树BST可以通过二分查找快速搜索结果

平衡二叉树

• BST如果不平衡，那就又成了链表了
• 所以要尽量平衡：平衡二叉搜索树BBST
• BBST增删查，时间复杂度都是 O(logn)，即树的高度

二叉查找树其性能在某些特殊情况可能降级到 O(n)。比如树不平衡，一侧有非常多节点，而另一侧几乎没有，则其性能会退化，导致后续操作都非常低效。所以，构建一个平衡的二叉树是高效处理数据的前提。平衡的二叉查找树，它能自动保持平衡状态。这种平衡的二叉查找树称为AVL 树，名字来源于其发明人：G.M. Adelson-Velskii 和E.M.Land。

红黑树

• 一种自平衡二叉树
• 分为 红/黑 两种颜色，通过颜色转换来维持树的平衡
• 相对于普通平衡二叉树，它的维持平衡的效率更高

红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

B树

• 物理上是多叉树，但逻辑上是二叉树
• 一般用于高效I/O，关系型数据库常用B树来组织数据

B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构。

小结

• 数组、链表，各有各的缺点
• 特定的二叉树（BBST）可以让整体效果最优
• 各种高级二叉树，继续优化，满足不同场景