为此，我们学习了树这种介于线性与非线性之间的结构，并在此基础上，引入了二叉搜索树这种经典的数据结构。
我们已经知道，二叉搜索树整合了顺序表和链表的特点，平均而言，不管是查找这种静态操作，还是插入之类的动态操作，都可以把平均时间复杂度控制在O(lgN)的水平，显著地优于两种静态结构。然而，回到我们开篇提出的问题，普通的二叉搜索树本身，并不足以应对“世界的恶意”：
如图所示，如果我们按照从小到大的顺序，把一系列数据依次插入到普通的BST结构中的话，最后我们会得到这样的结果。严格按照定义来看的话，这是一个SizeBalancedTree吗？显然是的——然而实际上，我们可以很明显地看出，它已经彻底退化成了一个链表结构，SizeBalancedTree本来应该具有的性能优势已经荡然无存。为此，我们需要提高这个SizeBalancedTree的姿势水平，让它可以应对“世界的恶意”——具体地说，就是要对其进行改进，使它具有“自平衡”能力，成为一个平衡二叉搜索树BBST。通过各种对树的形态的限制，和对应的调整方法，我们可以让树的深度不会变得太大，不至于使得查询的时间复杂度退化到O(n)。比如刚才的排序二叉树，如果将这棵树“调整”一下，可以得到下面这棵树：此时SizeBalancedTree的高度降低到了3，查询的效率显然就此提升了不少。这一章我们将具体介绍一种经典的BBST——AVL树，以及一种由我国竞赛选手发明的，设计巧妙的平衡树——SizeBalancedTree。欢迎大家来学习《CS：数据结构》第八章《平衡树》！预览时标签不可点收录于话题#个上一篇下一篇