标签归档:二叉查找树

键-值查找的基础——二叉查找树(Binary Search Tree)

在计算机程序设计中,我们经常需要一种将键与值联系并存储起来的数据结构,这个结构称为符号表。一个符号表应当至少支持插入、查询和删除等操作。

最简单的符号表之一是将键-值对作为一个结点,直接存入到一个数组中。每当要向符号表中插入新结点时,就将新的结点添加到数组的末尾。这个用数组构建的符号表是无序的,可以看到,当符号表的长度是 n 时,按键查询一个指定的结点最坏的情况下需要比较 n 次,搜索的时间复杂度是 O(n),这个简单实现是非常低效的。

要达到较高的搜索效率,最基本的思想是保持数据集合的有序性。在有序的数组中进行二分查找是一个典型的例子,二分查找可以达到对数级别的时间复杂度,效率远远优于在无序数组中顺序查找。遗憾的是,尽管在有序数组构成的符号表中执行二分查找非常高效,但符号表是应当支持动态插入和删除的,我们在数组上的实现此时陷入了一个矛盾:如果直接向数组尾部插入或删除结点,很可能破坏数组的有序性;如果在数组的中间插入或删除新结点,则因为移动插入或删除位置后的元素非常费时间,导致符号表的插入和删除的时间复杂度很高。另外值得一提的是链表拥有高效的插入和删除操作,但链表无法像数组那样随机访问,不能在链表上实现二分查找。

二叉查找树正是被设计用来解决插入/删除与查找效率矛盾的。将键与值同时保存在一棵二叉树的结点中,并保证所有结点的左子结点(如果不为空)的键小于右子结点(如果不为空)的键,那么这棵二叉树是二叉查找树。

二叉查找树的任一非空子树一定是二叉查找树。

利用以上这个性质,我们可以总结出在二叉查找树中查找键为 k 的结点的方法:
1.从根结点出发,作为当前结点;
2.比较 k 与当前结点键 kn 的大小,如果 k 等于 kn 那么查找命中返回;如果 k 小于 kn 那么继续查找左子树;如果 k 大于 kn ,那么继续查找右子树;
3.如果被查找的子树为空,那么查找失败,符号表中不存在要查找的结点。

向二叉查找树中插入新结点的过程与查找类似,先在二叉查找树中做一次查找,查找的健为 k ,根据情况做以下操作:
1.如果根为空(空二叉查找树)那么生成一个新结点作为根结点;
2.如果查找命中,那么用新的键和值替换命中的结点;
3.如果查找不命中,那么比较 k 与查找过程中最后一次访问的结点 noden 的键 kn ,如果 k 小于 kn ,那么生成一个新结点作为 noden 的左子树,反之如果 k 大于 kn ,那么生成一个新结点作为 noden 的右子树。

删除是二叉查找树中最难以实现的操作。

要向二叉查找树中删除结点时,先查找到指定结点,以下是较简单几种情形对应的操作:
1.没有查到结点,二叉查找树中不存在被删除的目标,删除失败;
2.查到的结点是叶子结点,直接删除;
3.查到的结点有且仅有一个非空子树,删除该结点,并把它的唯一子树连接到其父结点;

当查到的结点同时有两个非空子树时,删除这个结点就变得比较棘手,因为直接删掉这个结点后,会多出两个子树,而它们却只有一个父结点。T.Hibbard 在 1962 年提出了解决这个难题的第一个方法。[1] 为了方便描述,先考察“删除一棵二叉查找树中最小结点”的方法。显然地,一棵二叉查找树中最小的结点的左子树一定为空,所以这个操作符合上文所说的第 2 或第 3 种情形,可以很轻松地完成。定义一个函数:Node removeMinNode(Node node); 删除 node 结点的最小子结点并返回它的引用。现在删除二叉查找树中有两个非空子树的结点的算法可以描述如下:
1.查找到目标结点 nt,找出它的左结点 nl 和右结点 nr
2.执行“删除最小结点操作”,nn = removeMinNode(nr);,nn 替换到原来 nt 所在的位置;
3.分别设置 nl 和 nr 为 nn 的左、右结点。
这个操作可以保证删除目标结点后二叉查找树仍保持有序性。

用 Java 以非递归的方式实现了本文提到的二叉查找树的所有算法:查看

参考文献
[1] Sedgewick R, Wayne K. Algorithms[M]. 人民邮电出版社, 2012.