排序二叉树 (2)

1、排序二叉树Binary Sort Tree 线性表知识回顾 数组静态实现 链表实现 线性表知识回顾 数组静态实现 data:array of 1.maxn of integer 查找: 顺序查找O(n) 二分查找O(logn) 插入: O(n) 删除: O(n) 数组静态实现 （查找）data:array of 1.maxn of integer 查找: 顺序查找O(n)Function search(x:longint):longint;返回关键字为x的节点编号，如不存在返回0var i:longint;b:boolean;Begin i:=1;b:=false; while (in the

2、n search:=0;End;数组静态实现 （查找）data:array of 1.maxn of integer 查找: 二分查找O(logn)Function search(x,i,j:longint):longint;在i至j范围内查找,返回关键字为x的节点编号,如不存在返回0var m:longint;Begin if ij then begin search:=0;exit;end; if i=j then if x=datai then search:=i else search:=0 else begin m:=(i+j) div 2; if x=datam then sear

3、ch:=m if datamx then search:=search(x,i,m-1); if datamx then search:=search(x,m+1,j); end;End;数组静态实现 （插入）data:array of 1.maxn of integer 插入: O(n)procedure insert(x,k:longint):longint;将关键字为x的节点插入到k号节点前面var i:longint;Begin for i:=n downto k do datai+1:=datai; datak:=x; n:=n+1; End;数组静态实现 （删除）data:arra

4、y of 1.maxn of integer 删除: O(n)procedure delete(x:longint);删除k号节点var i:longint;Begin for i:=k+1 to n do datai-1:=datai; n:=n-1; End;线性表知识回顾 链表实现 data:array of 1.maxn,1.2 of integerdatai,2表示元素datai,1的后继编号 查找: 顺序查找O(n) 插入: O(1) 删除: O(1) data:array of 1.maxn,1.2 of integer Function search(x:longint):lo

5、ngint;返回关键字为x的节点编号,如不存在返回0,s为根结点编号var i:longint;b:boolean;Begin i:=s;b:=false; repeat if datai,1=x then begin search:=i;b:=true;end else i:=datai,2 until b or datas,2=0; if not(b) then search:=0;End;链表实现 （查找 O(n) ）data:array of 1.maxn,1.2 of integer procedure insert(x,i:longint);将关键字为x的节点插入到i号节点后面Be

6、gin n:=n+1; datan,2:=datai,2;datan,1:=x; datai,2:=nEnd;链表实现 （插入 O(1) ）data:array of 1.maxn,1.3 of integer datai,3表示i号节点的父节点编号procedure delete(i:longint);删除i号节点Begin y:= datai,3; if y=0 then s:=datai,2 else datay,2:=datai,2;End;链表实现 （删除 O(1) ）定义(递归) 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tr

7、ee)。 定义：二叉排序树或者是空树，或者是满足如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身又各是一棵二叉排序树。上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树。左 根 右特点 由BST性质可得：（1） 二叉排序树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。（2） 二叉排序树中，各结点关键字是唯一的。注意：实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉排序树定义中BST性质(1)里的小于改为

8、大于等于，或将BST性质(2)里的大于改为小于等于，甚至可同时修改这两个性质。（3） 按中序遍历该树所得到的中序序列是一个递增有序序列。排序二叉树 698752341中序遍历:1 2 3 4 5 6 7 8 9132231123123132排序二叉树n遍历(中序):O(n)n查找:O(logn)n插入: 直接递归 O(logn)n删除: O(logn) n先查找到该结点n无儿子: 直接删除O(1)n单个儿子: 用儿子代替它O(1)n两个儿子: 用后继(在右子树中一直左走)代替它排序二叉树链表实现TreeNode = record v:longint; left, right, p: longi

9、nt; end;Data:array1.maxn of longint;排序二叉树 遍历(中序):O(n)procedure print(x:longint);begin if datax.left0 then print(datax.left); writeln(datax.key); if datax.right0 then print(datax.right);end;注:datax.left=0表示该节点没有左子树，一般常用或者-来表示虚拟结点（没有孩子）排序二叉树 查找:O(logn) function search(x,i:longint):boolean;关键字为x的节点是否在以

10、i号节点为根的二叉树上begin if datai.v=x then search:=true else if xdatai.v then if datax.left=0 then search:=false else search(x,datai.left); if xx then if datai.left0 then insert(datai.left,x) else begin inc(s);datai.left:=s;datas.v:=x;end else if datai.right0 then insert(datai.right,x) else begin inc(s);dat

11、ai.right:=s;datas.v:=x;end; end;end;排序二叉树 插入:O(logn) procedure insert(x,i:longint);将编号为x的节点插入到以i号节点为根的二叉树中begin y:=0; while i0 do begin y:=i; if datax.vdatai.v then i:=datai.left else i:=datai.right; end; datax.p:=y; if y=0 then root:=x else if datax.vdatay.v then datay.left:=x else datay.right:=x;e

12、nd;排序二叉树 6987523415.55.55.55.55.5排序二叉树 最大最小值:O(logn) function max(i:longint):longint;返回以i号节点为根的二叉树上的最大节点的编号begin while datai.right0 do i:=datai.right; max:=i;end;function min(i:longint):longint;返回以i号节点为根的二叉树上的最大节点的编号begin while datai.left0 do i:=datai.left; min:=i;end;排序二叉树 687523419排序二叉树 前趋 :O(logn

13、) X无左儿子X有左儿子：x前趋是其左子树的最大值 （1）X是其父的右儿子：x前趋是其父 （2）X是其父的左儿子：找到其最低的祖先(满足是其父的右儿子),该节点的父节点是x的前趋若无这样的祖先，无后继X无父亲节点(根):无后继,x是最大节点（3）（4）X的前趋排序二叉树 前趋 :O(logn) function pred(i:longint):longint;返回i号节点的前趋节点的编号,如果无后继返回0begin if datai.left0 do pred:=max(datai.left) else begin x:=datai.p; while (x0)and(datax.left=i)

14、 do begin i:=x;x:=datax.p end; pred:=x; end;end;前趋情况（1） 6987523416的前趋是其左子树的最大值56987523415的前趋是其父4前趋情况（2） 912111082341前趋情况（3） 676的前趋是其最近的祖先（该节点是其父节点的右儿子,若该节点是其父的左儿子则再向上追溯）8的父节点469876无前趋前趋情况（4） 排序二叉树 后继 :O(logn) X无右儿子X有右儿子：x后继是其右子树的最小值 （1）X是其父的右儿子：x前趋是其父 （2）X是其父的左儿子：找到其最低的祖先(满足是其父的右儿子),该节点的父节点是x的前趋若无这样

15、的祖先，无后继X无父亲节点(根):无后继,x是最大节点（3）（4）X的后继排序二叉树 后继:O(logn) function succ(i:longint):longint;返回i号节点的后继节点的编号,如果无后继返回0begin if datai.right0 do succ:=min(datai.right) else begin x:=datai.p; while (x0)and(datax.right=i) do begin i:=x;x:=datax.p end; succ:=x; end;end;后继情况（1） 6987523416的后继是其右子树的最小值7152018177236

16、11399的后继是其父节点13后继情况（2） 71098523415的后继是其最近的祖先（该节点是其父节点的左儿子,若该节点是其父的右儿子则再向上追溯）4的父节点7后继情况（3） 后继情况（4） 6523416无后继排序二叉树 删除:O(logn) procedure delete(i:longint);删除编号为i的节点begin if (datai.left=0)or(datai.right=0) then y:=i else y:=succ(i); if datay.left0 then x:=datay.left else x:=datay.rhght if x0 then datax

17、.p:=datay.p if datay.p=0 then root:=x else if y=datadatay.p.left then datadatay.p.left:=x else datadatay.p.right:=x; if yi then datai.v:=datay.vend;排序二叉树 71098523416被删除节点6无儿子，直接删除排序二叉树 71092341被删除节点5有一个儿子，由其儿子接替其位置566排序二叉树 7109852341被删除的节点4有两个儿子，找到其后继节点，先删除其后继节点（即右子树的最小节点，不会有两个儿子），再用后继节点替代其位置6排序二叉树

18、7109862351被删除的节点4有两个儿子，找到其后继节点，先删除其后继节点（即右子树的最小节点，不会有两个儿子），再用后继节点替代其位置说明有两个儿子的节点的后继节点不可能有两个儿子其右子树的最小值节点不会有左儿子（若有，其左儿子小于它，非最小值）排序二叉树 7109852341被删除的节点4有两个儿子，找到其前趋节点，先删除其前趋节点（即左子树的最大节点，不会有两个儿子），再用前趋节点替代其位置6被删除的节点4有两个儿子，找到其前趋节点，先删除其前趋节点（即左子树的最大节点，不会有两个儿子），再用前趋节点替代其位置7109851236排序二叉树 71098523416被删除的节点4有两个

19、儿子，找到其前趋节点，先删除其前趋节点（不会有两个儿子），再用前趋节点替代其位置排序二叉树 710985123被删除的节点4有两个儿子，找到其前趋节点，先删除其前趋节点（不会有两个儿子），再用前趋节点替代其位置6说明有两个儿子的节点的前趋节点不可能有两个儿子其左子树的最大值节点不会有右儿子（若有，其右儿子大于它，非最大值）排序二叉树动态实现TreeNode = record v:integer; left, right, father: TreeNode; end;优点: 可实现在线算法缺点: 编程容易出错(删除和指针操作), 树容易不平衡排序二叉树动态实现TreeNode = record

20、v:integer; left, right, father: integer; end;Data:array 1.maxn of TreeNode;排序二叉树静态实现（用类完全二叉树实现）Value:array1.maxn of integer;Count:array1.maxn of integer;优点: 编程简单(插入删除查找统一), 树完美平衡缺点: 只能实现离线算法, 需要知道所有数据并排序问题: 可能不平衡解决: AVL, RB-Tree, Splay Tree, Treap排序二叉树 排序二叉树(Binary Sort Tree)又称二叉搜索树(Binary Search Tr

21、ee)。它是这样一种二叉树定义： 不包含任何结点的空树是一棵排序二叉树； 在一棵非空的排序二叉树中，它的左子树是一棵键值都小于根的排序二叉树，它的右子树是一棵键值都大于根的排序二叉树； 不难发现，相同的节点可以组成多种不同形状的排序二叉树，请问：对于n个不同的节点，最多可以组成多少种不同形状的排序二叉树。bsta.in3bsta.out5样例分析 132231123123132样例分析 分析 N个节点的二叉树可以分为N类（以第N个节点为根的二叉树） g(i)表示以第i个节点为根的不同二叉树数 f(i)=g(1)+g(2)+g(i) f(i)表示i个不同节点组成的不同二叉树数 分析 f(1)=1

22、 f(3)=g(1)+g(2)+g(3)=2+1+2=5f(2)=2 g(1)=f(2)=2 g(2)=f(1)*f(1)=1 g(3)=f(2)=2分析 f(4)=g(1)+g(2)+g(3)+g(4)=5+2+2+5=14 g(1)=f(3)=5 g(2)=f(1)*f(2)=1*2=2 g(3)=f(2)*f(1)=2*1=2 g(4)=f(3)=5分析 f(k)=f(k-1)+f(1)*f(k-2)+f(k-2)*f(1)+f(k-1)21) 1(*)() 1(*2)(kiikfifkfkf算法：递推 算法分析 时间复杂度：O(n2) 空间复杂度：O(n) 统计数字 某次科研调查时得到

23、了某次科研调查时得到了n个自然数，每个数均个自然数，每个数均不超过不超过1500000000(1.5*109)。已知不相同的。已知不相同的数不超过数不超过10000个，现在需要统计这些自然数各自个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统出现的次数，并按照自然数从小到大的顺序输出统计结果。计结果。 输入输出样例输入： 8242451002100输出：2 34 25 1100 2数字统计nconst maxm=10000;ntype vice=recordn key,left,right,num:longint;n end;nvar f:text;n data:ar

24、ray1.maxm of vice;n,s:longint;init procedure init;var i:longint;begin assign(f,count.in);reset(f);readln(f,n); for i:=1 to maxm do begin with datai do begin left:=0;right:=0;num:=0; end; end; readln(f,data1.key);inc(data1.num);s:=1;end;main procedure main;var i,x:longint;begin for i:=2 to n do begin readln(f,x); insert(1,x); end; close(f);end;procedure insert(x,y:longint);将y插入到以x号节点为根的二叉树中begin if datax.key=y then inc(datax.num) else begin i