二叉查找树讲稿.doc

江西省省选讲稿 23p二叉查找树一、二叉查找树：查找树是一种数据结构，它支持多种动态集合操作，包括search，minimum，maximum，predecessor，successor，insert以及delete。在二叉查找树上执行的基本操作时间与树的高度成正比。对于一棵含有n个结点的完全二叉树，这些操作的时间复杂度为O(log2n)。但是，如果树是含有n个结点的线性链，则这些操作的最坏情况下的运行时间为O(n)。（一）二叉查找树的概念：二叉查找树（BST，Binary Search Tree）又称二叉排序树或二叉搜索树，它或者是一棵空树，或者是一棵具有如下性质的非空二叉树：（1）若它的左子树不空，则左子树上所有节点的值均不大于它的根节点的值；（2）若它的右子树不空，则右子树上所有节点的值均不小于它的根节点的值；（3）它的左、右子树也分别为二叉查找树。等价定义：若以中序遍历二叉查找树，则会产生一个所有节点关键字值的递增序列。 45 / 12 53 / 3 37 100 / / 24 61 90 / 78例如：右下图的树，中序遍历得到的数值为（3，12，24，37，45，53，61，78，90，100）。二叉查找树之所以又称为二叉排序树，因为它是“排过序”的二叉树，但并非是“用于排序”的二叉树。不难发现，二叉查找树这种数据结构的优势在于它的有序性，这是其它类似功能的数据结构无法达到的。比如有序线性表虽然有序，但是插入算法的时间复杂度为O(n)；堆的插入算法虽然时间复杂度为O(log2n)，但是堆并不具有有序性。因此，我们要充分发挥二叉查找树的优势，就要充分利用其有序性和插入、查找算法的高效性。所以，如果要经常对有序数列进行“动态”的插入或查找工作，就可以采用二叉查找树来实现。依据二叉查找树的定义，我们知道：具有相同结点集的二叉查找树，可能的形态很不同。例如对于集合1，2，3所建立的二叉查找树就可能是下图所示的五种形态的任一种。123132132132132（二）二叉查找树的数据结构一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示，其中每一个结点都是一个对象。结点中除了key域和卫星数据域外，还包含域left，right和p，它们分别指向结点的左儿子、右儿子和父结点。如果某个儿子结点或父结点不存在，则相应域中的值即为NIL。根结点是树中唯一父结点域为NIL的结点。一般情况下，一棵二叉查找树的存储结构如下：type node = record key : longint; 关键值 left, right, p : longint; 左儿子、右儿子、父结点 根据需要增加一些数据域 end;var bst : array1.maxn of node;（三）二叉查找树的遍历根据二叉查找树的性质，若要求按递增顺序输出树的所有关键字，只需要采用中序遍历算法递归即可：procedure inorder_print(root : integer); 递归中序输出，从小到大 begin if bstroot.left0 then inorder_print(bstroot.left); write(bstroot.key, ); if bstroot.right0 then inorder_print(bstroot.right); end;也可以用广义表的形式输出：procedure out(root : integer); begin write(); if bstroot.left0 then out(bstroot.left); write(bstroot.key); if bstroot.right0 then out(bstroot.right); write(); end;二叉查找树看似简单，且没有太多的规则，其实它在题目中变化无常，所以要真正要用好它，是需要下一番功夫的。首先要熟练掌握好它的各种基本操作，下面一一给出。二、查询二叉查找树对于二叉查找树，最常见的操作是查找树中的某个关键字。除了search操作外，二叉查找树还能支持诸如minimum、maximum、predecessor和successor等查询。本节就来讨论这些操作，并说明对于高度为h的树，它们都可以在O(h)时间内完成。（一）查找关键字值为k的节点从树的根节点出发，查找关键字k的位置。由于二叉查找树本身的特点，所以这个查找过程总是沿着树的某条路径，逐层向下进行判断比较，或者找到匹配对象，返回k值的位置；或者找不到匹配对象，返回0。递归算法如下：function search(root, k : integer) : integer; begin if (root=0) or (k=bstroot.key) then exit(root); if kbstroot.key then search:=search(bstroot.left, k) else search:=search(bstroot.right, k); end;从算法中可以看出，这个算法递归时一旦返回，就再也不会出现递归调用，这种递归叫做末尾递归。末尾递归可以写成非递归的形式，这样可以节省栈所用的空间与运行时间。相比较递归算法而言，非递归算法更加高效：function search(root, k : integer) : integer; begin while (root0) and (kbstroot.key) do if kbstroot.key then root:=bstroot.left else root:=bstroot.right; search:=root; end;（二）求最小（大）关键字值的结点要查找二叉树中具有最小关键字的结点，只要从根结点出发，沿着各结点的left指针查找下去，直到遇到NIL时为止。下面给出从树的某个结点出发，查找其子树中最小关键字值的结点位置的函数。function min(x : integer) : integer; begin while bstx.left0 do x:=bstx.left; min:=x; end;二叉树的性质保证了上述函数的正确性。如果一个结点x无左子树，其右子树中的每个关键字都至少和keyx一样大，则以x为根的子树中，最小关键字就是keyx。如果结点x有左子树，因其左子树中的关键字都不大于keyx，而右子树中的关键字都不小于keyx，因此，在以x为根的子树中，最小关键字可以在以leftx为根的左子树中找到。同样地，要查找二叉树中具有最大关键字的结点，只要从根结点出发，沿着各结点的right指针查找下去，直到遇到NIL时为止。这个过程与查找最小关键字的结点是对称的。下面给出从树的某个结点出发，查找其子树中最大关键字值的结点位置的函数：function max(x : integer) : integer; begin while bstx.right0 do x:=bstx.right; max:=x; end;（三）求一棵二叉查找树中结点x的后继（前趋）结点。给定一个二叉查找树中的结点，有时候要求找出在中序遍历顺序下它的后继（前驱）。如果所有的关键字都不相同，则某一个结点x的后继结点即具有大于keyx中的关键字中最小者的那个结点。根据二叉查找树的结构，不用对关键字做任何比较，就可以找到某个结点的后继。查找结点x的后继时需要考虑两种情况：（1）如果结点x的右子树非空，则x的后继即右子树中的最左（小）结点，如下图中关键字是6的结点的后继结点是关键字为7的结点，关键字是15的结点的后继结点是关键字为17的结点。（2）如果结点x的右子树为空，且x有一个后继y，则y是x的最低祖先结点，且y的左儿子也是x的祖先。如下图中，关键字为13的结点的后继是关键字为15的结点。为找到y，可以从x开始往上查找，直到遇到某个结点是其父结点的左儿子结点时为止。302346713915182017下面给出查找结点x的后继结点y的函数：function succ(x : integer) : integer; var y : integer; begin if bstx.right0 then y:=min(bstx.right) else begin y:=bstx.p; while (bsty.p0) and (x=bsty.right) do begin x:=y; y:=bsty.p; end; end; succ:=y; end;相应地，查找结点x的前驱与后继是对称的，也需要考虑两种情况：（1）如果结点x的左子树非空，则x的前趋即左子树中的最右（大）结点，如上图中关键字是15的结点的前驱结点是关键字为13的结点。（2）如果结点x的左子树为空，且x有一个前趋y，则y是x的最低祖先结点，且y的右儿子也是x的祖先。如上图中，关键字为9的结点的前驱是关键字为7的结点。也就是要从x开始，往上找某个结点y，它的右儿子是x的祖先。其实，在没有左子树的情况下，如果x是右儿子，则前趋就是x的父结点。下面给出查找结点x的前驱结点y的函数：function pred(x : integer) : integer; var y : integer; begin if bstx.left0 then y:=max(bstx.left) else begin y:=bstx.p; while (bsty.p0) and (x=bsty.left) do begin x:=y; y:=bsty.p; end; end; pred:=y; end;三、二叉查找树的插入与删除插入和删除操作会引起以二叉查找树表示的动态集合的变化。要反应出这种变化，就要修改数据结构，但在修改的同时，还要保持二叉查找树性质。（一）二叉查找树的插入把结点z插入到二叉查找树T中，使T仍然满足二叉查找树的性质。例如，下图是把关键字为14的结点，插入到一棵已存在的二叉查找树中的情况。从插入后的结果中可以看出：只要从根结点开始，不断沿着树枝下降即可。用指针x跟踪这条路径，而y始终指向x的父结点。根据keyz与keyx的比较结果，可以决定向左或者向右。直到x成为NIL时为止。这个NIL所占位置即我们想插入z的地方。在下面描述的插入过程中，先将插入结点z的相关信息存放在bst数组的位置i上，插入结点的关键字为t。143426151820179137procedure insert(i, t : integer); var x, y : integer; begin y:=0; x:=1; while (x0) and (bstx.key0) do begin 从上往下找位置 y:=x; if t0 then if tbsty.key then bsty.left:=i else bsty.right:=i; end;上述过程也可以用递归过程实现。递归过程中x为空结点位置，y为父结点位置，i为查找树数组位置，t为待插入结点z的关键字：procedure insert(x, y, i, t : integer); begin if x=0 then begin bsti.key:=t; bsti.p:=y; if tbsty.key then bsty.left:=i else bsty.right:=i; end else if tbstx.key then insert(bstx.left, x, i, t) else insert(bstx.right, x, i, t); end;（二）二叉查找树的删除二叉查找树的删除比它的插入要复杂一些，因为除了把某个结点删除外，还需要考虑几个限制：（1）删除后，断开的二叉树需要重新链接起来。（2）删除后，需保证二叉查找树性质不变。（3）二叉树的高度决定效率，所以删除某个结点后，不能增加原二叉树的高度。综合考虑上面的三个因素，针对被删除结点z的类型，可以分3种情况讨论：（1）如果被删除结点z为叶结点，只需清空其父结点指向它的指针，再把该结点释放即可，即：bstbstz.p.left:=0 或 bstbstz.p.right:=0。（2）如果被删除结点z只有一个儿子，则可通过在其父结点和它的儿子结点之间建立一个链接，从而删除结点z。即若结点z无左子树，则用结点z右子树的根结点代替结点z，如下左图；若结点z无右子树，则用结点z左子树的根结点代替结点z，如下右图。或子树Z子树子树Z子树（3）如果被删除结点z的左右子树均存在，那么可以在其右子树中寻找关键字最小的结点，用它来代替被删除的结点，再把这个代替结点从原来的位置上删除；也可以在其左子树中寻找关键字最大的结点，用它来代替被删除的结点，再把这个代替结点从原来的位置上删除；还可以交替地用左子树中关键字最大的结点或者右子树中关键字最小的结点来代替被删除的结点，再把这个代替结点从原来的位置上删除。17237195132517237193132用右子树中最小值来代替31723719513217237193132用左子树中最大值来代替以下是一个实现删除结点z的过程：procedure delete(z : integer); var x, y : integer; begin if (bstz.left=0) or (bstz.right=0) then y:=z else y:=succ(z); 找到要删除的结点y if bsty.left0 then x:=bsty.left else x:=bsty.right; x是y的孩子 if x0 then bstx.p:=bsty.p; if bsty.p=0 then root:=x 删除的是根 else if y=bstbsty.p.left then bstbsty.p.left:=x else bstbsty.p.right:=x; if yz then bstz.key:=bsty.key; 如果结点中还有其它域，需要一并进行复制 end;【例1】编程输入一组不同的大于0的整数（共n个），建立一棵二叉搜索树；再输入一个整数，作为关键字，找到这个关键字所指定的结点，并将这个结点删除；最后按中序遍历输出广义表形式。参考程序type node = record key : integer; left, right, p : integer; end;var bst : array1.5000 of node; n, root : integer; k, x : integer;procedure insert(i, t : integer); var x, y : integer; begin y:=0; x:=1; while (x0) and (bstx.key0) do begin y:=x; if t0 then if tbsty.key then bsty.left:=i else bsty.right:=i; end;procedure main; var i, t : integer; begin readln(n); for i:=1 to n do begin read(t); insert(i, t); end; readln; readln(k); end;function min(x : integer) : integer; begin while bstx.left0 do x:=bstx.left; min:=x; end;function succ(x : integer) : integer; var y : integer; begin if bstx.right0 then y:=min(bstx.right) else begin y:=bstx.p; while (bsty.p0) and (x=bsty.right) do begin x:=y; y:=bsty.p; end; end; succ:=y; end;function search(root, k : integer) : integer; begin while (root0) and (kbstroot.key) do if kbstroot.key then root:=bstroot.left else root:=bstroot.right; search:=root; end;procedure delete(z : integer); var x, y : integer; begin if (bstz.left=0) or (bstz.right=0) then y:=z else y:=succ(z); if bsty.left0 then x:=bsty.left else x:=bsty.right; if x0 then bstx.p:=bsty.p; if bsty.p=0 then root:=x else if y=bstbsty.p.left then bstbsty.p.left:=x else bstbsty.p.right:=x; if yz then bstz.key:=bsty.key; end;procedure out(root : integer); begin write(); if bstroot.left0 then out(bstroot.left); write(bstroot.key); if bstroot.right0 then out(bstroot.right); write(); end;begin fillchar(bst, sizeof(bst), 0); main; root:=1; x:=search(root, k); if x0 then delete(x); out(root);end.至此，一般的二叉查找树的基本模块介绍完毕。当然二叉查找树能帮助我们实现的远不止上述功能，我们可以通过对二叉查找树数据结构中域的改变来实现一些我们需要的操作。如查找关键字为第k大（小）的结点，我们可以增加一个count域，countz的值为结点z的左右子树中共有多少个结点，这样，就可以帮助我们在O(h)的时间复杂度内找出我们要找的结点。但是二叉查找树并不一定是平衡树，它在最坏的情况下，二叉查找树可能会退化成含有n个结点的线性链（如输入结点信息时，其关键字严格按递增或递减顺序排列），此时在二叉查找树上进行的所有操作的时间复杂度都会退化达到O(n)。四、随机构造的二叉查找树Treap树Treap树的基本思想是用随机化来优化BST，当一些元素以一个给定的顺序加入BST时，我们无法保证这些元素顺序的随机性。于是，我们可以给每个元素一个随机的优先权（可以通过系统的随机函数取得），通过这个优先权使元素的顺序也具有随机性。即我们要构造这样一棵树：这棵树上的元素，它们的值符合BST的性质，它们的优先权符合堆（Heap，下文中均指最小堆）的性质。这就是Treap名字的由来，“Treap”“Tree + Heap”。例如，用（值，优先权）来表示元素，下面的左图就是合法的Treap；而右图是BST，但不是合法Treap；(4,50)/ (1,40) (8,73) / (6,92) (20,27)(4,5)/ (1,40) (8,27) / (6,92) (20,73)我们如何给这棵树插入元素呢？大体是两个步骤，首先是按照BST的规则插入元素；然后再通过旋转，在不影响BST性质的同时保证它满足堆的性质。 X Y / / A Y X C / / B C A B右旋左旋第一步非常简单，整个算法的关键就在第二步。首先介绍一种非常简单而实用的树的旋转，看这样的两棵树（如下图）：不难发现，不论A、B、C是怎样的结构，如果其中一棵树符合BST性质，那么另一棵树就必定也符合BST性质。这样我们就可以在不影响A、B、C的同时，完成X、Y的交换。基于这条性质，如果在右图中X的优先权比Y的小，不符合堆的性质，我们就可以通过从右往左的一次变换，使X出现在了Y的上方，从而恢复其堆的性质。由此可见，要完成插入元素的调整，只要不停地在它和它的父节点之间作旋转操作，直到他的父节点的优先权比他小就可以了。看下面的例子，假设要插入的数依次为1、2、3、4、5、6，通过随机函数得到的优先权分别为10、22、5、80、37、45，插入过程可以描述如下：(1,10) (1,10) (2,22)这两次插入都没有影响堆的性质，所以就不需要进行旋转维护。(1,10) (1,10) (3,5) / (2,22) (3,5) (1,10) / (3,5) (2,22) (2,22)(3,5)插入后，由于5比22、10都小，所以要进行两次旋转操作，把(3,5)调整到了最上面，保证了优先权的堆性质。 (3,5) (3,5) (3,5) / / / (1,2) (4,80) (1,2) (5,37) (1,2) (5,37) / / (2,22) (5,37) (2,22) (4,80) (2,22) (4,80) (6,45)接着插入4、5、6，并对4，5进行了旋转调整，完成了整棵树的插入。通过观察，不难发现：如果把每个元素按照优先权大小的顺序（在上例中，即按照3、1、2、5、6、4的顺序）依次插入BST，形成的树和以上插入调整后的结果完全一致。这就是Treap的作用，使得数据的插入实现了无关与数据本身的随机性，其效果与把数据打乱后插入完全相同。但与此同时，它没有改变插入的顺序，这使得它几乎能应用于所有需要使用平衡BST的地方。Treap的实质是元素的优先权具有堆性质的BST。Treap的应用，可以降低实现AVL的编程复杂度，同时它又具有不错的时间效率。在一般情况下，Treap的所建成的树的最大高度不大于4log2n，用它实现排序，时间也仅仅为没有退化的Qsort的2倍左右，可以说是比较理想的。附、源程序：const maxn = 100000;type point = record lc, rc, fa : longint; num, priority : longint; end;var data : array1.maxn of longint; tree : array0.maxn of point; root, top, n : longint;function randompriority : longint; begin randompriority:=random(maxint); end;procedure init; var i : longint; begin readln(n); for i:=1 to n do read(datai); readln; randomize; top:=1; root:=1; tree1.num:=data1; tree1.priority:=randompriority; end;procedure tree_rotation_l(x, y, b : longint); /左旋 begin if treey.fa0 then if treetreey.fa.lc=y then treetreey.fa.lc:=x else treetreey.fa.rc:=x; treex.fa:=treey.fa; treex.rc:=y; treey.fa:=x; if b0 then begin treey.lc:=b; treeb.fa:=y; end else treey.lc:=0; end;procedure tree_rotation_r(x, y, b : longint); /右旋 begin if treey.fa0 then if treetreey.fa.lc=y then treetreey.fa.lc:=x else treetreey.fa.rc:=x; treex.fa:=treey.fa; treex.lc:=y; treey.fa:=x; if b0 then begin treey.rc:=b; treeb.fa:=y; end else treey.rc:=0; end;procedure tree_adjust(k : longint); /调整，保证元素优先权的堆性质 var t : longint; begin t:=treek.fa; while (t0) and (treet.prioritytreek.priority) do begin if treet.lc=k then tree_rotation_l(k, t, treek.rc) else tree_rotation_r(k, t, treek.lc); if t=root then root:=k; t:=treek.fa; end; end;procedure treap_add(k, num, priority : longint); /按照BST顺序插入 begin if treek.num=0 then begin treek.num:=num; treek.priority:=priority; tree_adjust(k); end else if numtreek.num then if treek.rc=0 then begin inc(top); treetop.fa:=k; treek.rc:=top; treap_add(top, num, priority); end else treap_add(treek.rc, num, priority) else if treek.lc=0 then begin inc(top); treetop.fa:=k; treek.lc:=top; treap_add(top, num, priority); end else treap_add(treek.lc, num, priority); end;procedure doit; var i : longint; begin for i:=2 to n do begin treap_add(root, datai, randompriority); end; end;procedure out(k : longint); begin if treek.lc0 then out(treek.lc); writeln(treek.num); if treek.rc0 then out(treek.rc); end;begin assign(input, treap.in); reset(input); assign(output, treap.out); rewrite(output); init; doit; out(root); close(input); close(output);end.五、应用举例【例2】魔兽争霸（war）。【问题描述 Description】小x正在销魂地玩魔兽，他正控制着死亡骑士和n个食尸鬼（编号1n）去打猎。死亡骑士有个魔法，叫做“死亡缠绕”，可以给食尸鬼补充HP，战斗过程中敌人会对食尸鬼实施攻击，食尸鬼的HP会减少。小x希望随时知道自己部队的情况，即HP值第k多的食尸鬼有多少HP，以便决定如何施放魔法，请同学们帮助他。小x向你发出3种信号：（下划线在输入数据中表现为空格）A_i_a 表示敌军向第i个食尸鬼发出了攻击，并使第i个食尸鬼损失了a点HP，如果它的HP=0，那么这个食尸鬼就死了。敌军不会攻击一个已死的食尸鬼。C_i_a 表示死亡骑士向第i个食尸鬼放出了死亡缠绕，并使其增加了a点HP。HP值没有上限。死亡骑士不会向一个已死的食尸鬼发出死亡缠绕。Q_k 表示小x向你发出询问。输入格式 Input Format第一行，一个正整数n；第二行n个整数，表示n个食尸鬼的初始HP值；第三行一个正整数m；以下m行，每行一个小x发出的信号。输出格式 Output Format对于小x的每个询问，输出HP第k多的食尸鬼有多少HP，如果食尸鬼总数不足k个，输出-1。每个一行数。最后一行输出一个数：战斗结束后剩余的食尸鬼数。样例输入 Sample Input51 2 3 4 510Q 2A 4 6C 1 4Q 2A 2 1A 3 3A 1 3Q 4C 2 10Q 1样例输出 Sample Output45-1113【数据范围 Date Range】40%的数据：n=3000，m=5000；70%的数据：n=8000，m=10000；100%的数据：n=30000，m=50000。90%的数据随机生成，食尸鬼HP没有上限，数据保证任意时刻食尸鬼的HP值在longint范围内，数据保证A和C命令中的食尸鬼是活着的，输入数据中没有多余空格、换行。算法分析本题考查二叉树的应用。修改HP时把原HP值在树中删除，再将新的HP值插入，复杂度O(logn)。同时在树的每个节点上维护以该点为根的子树上共有多少个节点，则可以在O(logn)时间内回答询问。总复杂度为O(m*logn)。具体实现请参考标准程序参考程序之一：使用二叉查找树的简单实现，可以得到90分，第8个点采用了相对极端的数据，在构造二叉搜索树时几乎形成单边的树，蜕化为一条线。const inf=war.in; outf=war.out; maxn=30000;var hp, bst : array0.maxn of longint; l, r, count : array0.maxn of longint; n, m : longint; root, size, free : longint;function insert(i, x : longint) : longint; begin if i=0 then begin if free=0 then begin inc(size); i:=size; end else begin i:=free; free:=0; end; bsti:=x; li:=0; ri:=0; counti:=1; exit(i); end; if xbsti then begin inc(counti); li:=insert(li, x); end else begin inc(counti); ri:=insert(ri, x); end; insert:=i; end;function find_min(i : longint) : longint; begin while li0 do i:=li; find_min:=bsti; end;function remove(i, x : longint) : longint; begin dec(counti); if xbsti then ri:=remove(ri, x) else if (li0) and (ri0) th