二叉查找树讲稿

江西省省选讲稿 1 p 二叉查找树

一、二叉查找树： 查找树是一种数据结构，它支持多种动态集合操作，包括search，minimum，maximum，predecessor，successor，insert以及delete。 在二叉查找树上执行的基本操作时间与树的高度成正比。对于一棵含有n个结点的完全二叉树，这些操作的时间复杂度为O(log2n)。但是，如果树是含有n个结点的线性链，则这些操作的最坏情况下的运行时间为O(n)。

（一）二叉查找树的概念： 二叉查找树（BST，Binary Search Tree）又称二叉排序树或二叉搜索树，它或者是一棵空树，或者是一棵具有如下性质的非空二叉树： （1）若它的左子树不空，则左子树上所有节点的值均不大于它的根节点的值； （2）若它的右子树不空，则右子树上所有节点的值均不小于它的根节点的值； （3）它的左、右子树也分别为二叉查找树。 等价定义：若以中序遍历二叉查找树，则会产生一个所有节点关键字值的递增序列。 例如：右下图的树，中序遍历得到的数值为（3，12，24，37，45，53，61，78，90，100）。 二叉查找树之所以又称为二叉排序树，因为它是“排过序”的二叉树，但并非是“用于排序”的二叉树。 不难发现，二叉查找树这种数据结构的优势在于它的有序性，这是其它类似功能的数据结构无法达到的。比如有序线性表虽然有序，但是插入算法的时间复杂度为O(n)；堆的插入算法虽然时间复杂度为O(log2n)，但是堆并不具有有序性。因此，我们要充分发挥二叉查找树的优势，就要充分利用其有序性和插入、查找算法的高效性。所以，如果要经常对有序数列进行“动态”的插入或查找工作，就可以采用二叉查找树来实现。 依据二叉查找树的定义，我们知道：具有相同结点集的二叉查找树，可能的形态很不同。例如对于集合{1，2，3}所建立的二叉查找树就可能是下图所示的五种形态的任一种。

（二）二叉查找树的数据结构

45 / \ 12 53 / \ \ 3 37 100 / / 24 61 \ 90 / 78

1 2 3 1 3 2 1 3 2 1 3 2 1

3 2 江西省省选讲稿 2 一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示，其中每一个结点都是一个对象。结点中除了key域和卫星数据域外，还包含域left，right和p，它们分别指向结点的左儿子、右儿子和父结点。如果某个儿子结点或父结点不存在，则相应域中的值即为NIL。根结点是树中唯一父结点域为NIL的结点。 一般情况下，一棵二叉查找树的存储结构如下： type node = record key : longint; {关键值} left, right, p : longint; {左儿子、右儿子、父结点} „„ {根据需要增加一些数据域} end; var bst : array[1..maxn] of node;

（三）二叉查找树的遍历 根据二叉查找树的性质，若要求按递增顺序输出树的所有关键字，只需要采用中序遍历算法递归即可： procedure inorder_print(root : integer); {递归中序输出，从小到大} begin if bst[root].left<>0 then inorder_print(bst[root].left); write(bst[root].key, ' '); if bst[root].right<>0 then inorder_print(bst[root].right); end; 也可以用广义表的形式输出： procedure out(root : integer); begin write('('); if bst[root].left<>0 then out(bst[root].left); write(bst[root].key); if bst[root].right<>0 then out(bst[root].right); write(')'); end; 二叉查找树看似简单，且没有太多的规则，其实它在题目中变化无常，所以要真正要用好它，是需要下一番功夫的。首先要熟练掌握好它的各种基本操作，下面一一给出。

二、查询二叉查找树 对于二叉查找树，最常见的操作是查找树中的某个关键字。除了search操作外，二叉查找树还能支持诸如minimum、maximum、predecessor和successor等查询。本节就来讨论这些操作，并说明对于高度为h的树，它们都可以在O(h)时间内完成。 江西省省选讲稿 3 （一）查找关键字值为k的节点 从树的根节点出发，查找关键字k的位置。由于二叉查找树本身的特点，所以这个查找过程总是沿着树的某条路径，逐层向下进行判断比较，或者找到匹配对象，返回k值的位置；或者找不到匹配对象，返回0。递归算法如下： function search(root, k : integer) : integer; begin if (root=0) or (k=bst[root].key) then exit(root); if k then search:=search(bst[root].left, k) else search:=search(bst[root].right, k); end; 从算法中可以看出，这个算法递归时一旦返回，就再也不会出现递归调用，这种递归叫做末尾递归。末尾递归可以写成非递归的形式，这样可以节省栈所用的空间与运行时间。相比较递归算法而言，非递归算法更加高效： function search(root, k : integer) : integer; begin while (root<>0) and (k<>bst[root].key) do if k else root:=bst[root].right; search:=root; end;

（二）求最小（大）关键字值的结点 要查找二叉树中具有最小关键字的结点，只要从根结点出发，沿着各结点的left指针查找下去，直到遇到NIL时为止。 下面给出从树的某个结点出发，查找其子树中最小关键字值的结点位置的函数。 function min(x : integer) : integer; begin while bst[x].left<>0 do x:=bst[x].left; min:=x; end; 二叉树的性质保证了上述函数的正确性。如果一个结点x无左子树，其右子树中的每个关键字都至少和key[x]一样大，则以x为根的子树中，最小关键字就是key[x]。如果结点x有左子树，因其左子树中的关键字都不大于key[x]，而右子树中的关键字都不小于key[x]，因此，在以x为根的子树中，最小关键字可以在以left[x]为根的左子树中找到。 同样地，要查找二叉树中具有最大关键字的结点，只要从根结点出发，沿着各结点的right指针查找下去，直到遇到NIL时为止。这个过程与查找最小关键字的结点是对称的。 江西省省选讲稿 4 下面给出从树的某个结点出发，查找其子树中最大关键字值的结点位置的函数： function max(x : integer) : integer; begin while bst[x].right<>0 do x:=bst[x].right; max:=x; end;

（三）求一棵二叉查找树中结点x的后继（前趋）结点。 给定一个二叉查找树中的结点，有时候要求找出在中序遍历顺序下它的后继（前驱）。如果所有的关键字都不相同，则某一个结点x的后继结点即具有大于key[x]中的关键字中最小者的那个结点。根据二叉查找树的结构，不用对关键字做任何比较，就可以找到某个结点的后继。 查找结点x的后继时需要考虑两种情况： （1）如果结点x的右子树非空，则x的后继即右子树中的最左（小）结点，如下图中关键字是6的结点的后继结点是关键字为7的结点，关键字是15的结点的后继结点是关键字为17的结点。 （2）如果结点x的右子树为空，且x有一个后继y，则y是x的最低祖先结点，且y的左儿子也是x的祖先。如下图中，关键字为13的结点的后继是关键字为15的结点。为找到y，可以从x开始往上查找，直到遇到某个结点是其父结点的左儿子结点时为止。

下面给出查找结点x的后继结点y的函数： function succ(x : integer) : integer; var y : integer; begin if bst[x].right<>0 then y:=min(bst[x].right) else begin y:=bst[x].p; while (bst[y].p<>0) and (x=bst[y].right) do

30 2 3 4 6 7 13 9 15 18 20 17