数据结构是数据的组织形式和访问方法，前文介绍了基础数据结构，在基础上发展出了很多高级数据结构，它们原理复杂，编程困难。
为什么需要这么多高级数据结构？这是在特定应用背景下高效处理数据的需要。基础数据结构不够强大，像数组、栈、队列这样的线性结构，计算复杂度为O(n)，在面对大量数据时力不从心；二叉树、堆、哈希很高效，但是它们过于简单，在处理很多特定问题时操作不便。高级数据结构与某些应用背景紧密结合，能高效地解决问题。例如，集合问题用并查集；区间问题用树状数组、线段树、分块、莫队算法；混合问题用块状链表；动态查询用平衡树，等等。本章介绍算法竞赛涉及的高级数据结构。
本篇介绍二叉查找树。
如果一棵二叉树能用于“查找”，说明每个节点有一个能区分大小的“键值”。这些节点最好按键值有序排列，才能进行高效查找，这就是二叉查找树(Binary Search Tree，BST)。
BST的特征
BST有以下特征。
(1) 每个节点有唯一的键值，这些键值可以比较大小。
(2) 在BST上，以任意节点为根的一棵子树，仍然是BST。任意节点的键值比它的左子树所有节点的键值大，比它的右子树所有节点的键值小。键值最大的节点，没有右儿子；键值最小的节点，没有左儿子。
根据特征(2)，用中序遍历能够得到有序排列。如图4.53所示，中序遍历的结果是“123456”。
■ 图4.53二叉查找树
如图4.53所示，画一些虚线，把每个节点隔开，节点正好按从小到大的顺序被虚线隔开了。有了虚线的帮助，很容易理解后文Treap树和Splay树中提到的“旋转”技术。
在BST上查找一个数，查找次数是二叉树的深度。例如，查找3，从根节点开始，沿着4-2-3查找两次就确定了。在建立一棵二叉查找树时，如果每层差不多都是满的，此时BST的层次最少，最能发挥BST的威力。
BST的形态
BST的形态是否唯一？根据特征(2)模拟建树的过程，从第1个数据a开始，以a为根节点，然后逐个插入其他数据。先插入第2个数据b，如果b<a，就往a的左子树插，否则就往右子树插；然后插入第3个数据b，仍然从根节点a开始比较，如果比a小，就向左子树走，如果左子树为空，就插到空位上，如果左子树为b，就与b比较…
从建树的过程可知，如果按给定序列的顺序进行插入，最后建成的BST是唯一的。形成的BST可能很好，也可能很坏。例如序列{1，2，3，4，5，6，7}，若按顺序插入，会全部插到右子树上，BST退化成一条只包含右子树的链，导致访问一个节点要走O(n)层。若把序列打乱成{4，2，1，3，6，5，7}，得到的BST是完全平衡的，访问一个节点只需要走O(log2n)层，如图4.54所示。
■ 图4.54退化的BST和平衡BST
一棵平衡的二叉树，可以理解成用分治法对一个数字序列按树的形态进行划分：根节点是整棵树的中间数字，树上的每棵子树的根是这棵子树的中间数字。
删除一个节点会改变BST的形态。模拟删除的过程，首先找到被删节点x，如果x是最底层的叶子节点，直接删除；如果x只有左子树L，或者只有右子树R，直接删除x，原位置由L或R代替。如果x的左、右子树都有，情况就复杂了，此时，原来以x为根节点的子树需要重新建树。一种做法是搜索x左子树中的最大元素y，移动到x的位置；这相当于原来以y为根节点的子树删除了y，然后继续对y的左子树进行类似的操作，但是这样的删除操作，可能导致BST的形态不再平衡。
所以，使用BST的基本问题是如何建立和维护一棵“平衡”的BST。常见的BST有替罪羊树、Treap树、Splay树、AVL树、红黑树、SBT树等，它们的重要内容就是维护二叉树的平衡性。
提示/
一棵平衡的二叉树从它的任何一个节点出发，到其他任意节点的距离都是O(log2n)。
《算法竞赛》系列推文正在连载中，欢迎持续关注！
扫码优惠购书
