静态查找技术二叉排序树6平衡二叉排序树AVL培训课件ppt

6.1静态查找技术

6.2二叉排序树

6.3平衡二叉排序树(AVL树)

*6.4红-黑树

*6.5B-树和B+树

6.6哈希(Hash)方法

第六章查找静态查找技术

1、搜索：

在数据集合之中，搜索具有特定关键字的结点。

通常分为静态搜索表：集合中的结点总数是固定的或者很少发生变化。可以无序或组 织成有序表。

动态搜索表：集合中的结点总数是经常在发生变化。组织成树形结构。在内存中进行的搜索：重点减少比较、或查找的次数。评价标准：平均搜索长度。在外存中进行的搜索：重点在于减少访问外存的次数。评价标准：读盘次数。2、静态搜索结构：………………012n-3n-2n-1niVector哨兵单元采用静态向量(或数组)，0号单元用作哨兵单元，1号单元到n号单元保存结点。8100100713静态查找表(ADT)template<classType>classVector{public:

Vector(intsize);//构造函数，静态查找表的结点个数为

size.~Vector(){delete[]Array;}constType&operator[](intindex)const;//具有越界检查的下标操作。

constVector&operator=(constVector&R);//大小相等的向量的复制。

int

Length()const{returnArraySize;}voidDouble(){Resize(ArraySize*2);}//在向量的单元用完时，容量加倍。

voidResize(intNewsize); //修改向量的大小。

voidSentinel(constTypekey){Array[0]=key;}//置0号单元的内容为待查

key。

protected:Type*Array;//保存结点的数组

int

ArraySize;//大小。

voidGetArray();Vector(constVector&R);//冻结使用构造函数复制另一向量的功能。};

静态查找表(ADT)

部分操作的实现：template<classType>constType&Vector<Type>::operator[](intindex)const

{Exception(index≤0||index>ArraySize,“Outofboundary!”);returnArray[index];}template<classType>constVector<Type>&Vector<Type>::operator=(constVector<Type>R){if(this!=&R){ Exception(ArraySize!=R.ArraySize,“Sizeisnotsame!”); for(intk=1;k<=ArraySize;k++)Array[k]=R.Array[k]; }return*this;}静态查找表(ADT)

部分操作的实现：template<classType>voidVector<Type>::Resize(intNewSize){Type*oldArray=Array;constintminsize=Min(ArraySize,NewSize);//取二者小者。

ArraySize=NewSize;GetArray();for(intk=1;k<=minsize;k++)Array[k]=oldArray[k];delete[]oldArray;}template<classType>voidVector<Type>::GetArray(

){Array=newType[ArraySize+1];}template<classType>Vector<Type>::Vector(intSize){ArraySize=Size;GetArray();}顺序查找

应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。………………012n-3n-2n-1ni向量Vectorkeye.g:查找x=8的结点所在的数组元素的下标。8100100713设置哨兵的好处：在顺序表中总可以找到待查结点。否则，必须将判断条件i>=0加进for语句。template<classType>intSeqSearch(constVector<Type>&A,constTypekey,intN){A[0]=key;//将待查

key置于哨兵单元，可省掉越界检查。

for(intk=N;A[k]!=key;--k)returnk;//返回0，查找失败。否则，找到关键字为

key的结点的下标}顺序查找

应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。………………012n-3n-2n-1ni向量Vectorkeye.g:查找x=8的结点所在的数组元素的下标。8100100713设置哨兵的好处：在顺序表中总可以找到待查结点。否则，必须将判断条件i>=0加进for语句。template<classType>intSeqSearch(constVector<Type>&A,constTypekey,intN){A[0]=key;//将待查

key置于哨兵单元，可省掉越界检查。

for(intk=N;A[k]!=key;--k)returnk;//返回0，查找失败。否则，找到关键字为

key的结点的下标}顺序查找

应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。………………012n-3n-2n-1ni向量Vectorkeye.g:查找x=8的结点所在的数组元素的下标。8100100713设置哨兵的好处：在顺序表中总可以找到待查结点。否则，必须将判断条件i>=0加进for语句。template<classType>intSeqSearch(constVector<Type>&A,constTypekey,intN){A[0]=key;//将待查

key置于哨兵单元，可省掉越界检查。

for(intk=N;A[k]!=key;--k)returnk;//返回0，查找失败。否则，找到关键字为

key的结点的下标}顺序查找

应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。………………012n-3n-2n-1ni向量Vectorkeye.g:查找x=8的结点所在的数组元素的下标。8100100713设置哨兵的好处：在顺序表中总可以找到待查结点。否则，必须将判断条件i>=0加进for语句。template<classType>intSeqSearch(constVector<Type>&A,constTypekey,intN){A[0]=key;//将待查

key置于哨兵单元，可省掉越界检查。

for(intk=N;A[k]!=key;--k)returnk;//返回0，查找失败。否则，找到关键字为

key的结点的下标}顺序查找

应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。………………012n-3n-2n-1ni向量Vectorkeye.g:查找x=8的结点所在的数组元素的下标。8100100713设置哨兵的好处：在顺序表中总可以找到待查结点。否则，必须将判断条件i>=0加进for语句。template<classType>intSeqSearch(constVector<Type>&A,constTypekey,intN){A[0]=key;//将待查

key置于哨兵单元，可省掉越界检查。

for(intk=N;A[k]!=key;--k)returnk;//返回0，查找失败。否则，找到关键字为

key的结点的下标}顺序查找

应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。………………012n-3n-2n-1ni向量Vectorkeye.g:查找x=8的结点所在的数组元素的下标。8100100713设置哨兵的好处：在顺序表中总可以找到待查结点。否则，必须将判断条件i>=0加进for语句。template<classType>intSeqSearch(constVector<Type>&A,constTypekey,intN){A[0]=key;//将待查

key置于哨兵单元，可省掉越界检查。

for(intk=N;A[k]!=key;--k)returnk;//返回0，查找失败。否则，找到关键字为

key的结点的下标}顺序查找

应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。………………012n-3n-2n-1ni向量Vectorkeye.g:查找x=8的结点所在的数组元素的下标。8100100713设置哨兵的好处：在顺序表中总可以找到待查结点。否则，必须将判断条件i>=0加进for语句。template<classType>intSeqSearch(constVector<Type>&A,constTypekey,intN){A[0]=key;//将待查

key置于哨兵单元，可省掉越界检查。

for(intk=N;A[k]!=key;--k)returnk;//返回0，查找失败。否则，找到关键字为

key的结点的下标}顺序查找

应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。………………012n-3n-2n-1ni向量Vectorkeye.g:查找x=7的结点所在的数组元素的下标。7100100713设置哨兵的好处：在顺序表中总可以找到待查结点。否则，必须将判断条件i>=0加进for语句。template<classType>intSeqSearch(constVector<Type>&A,constTypekey,intN){A[0]=key;//将待查

key置于哨兵单元，可省掉越界检查。

for(intk=N;A[k]!=key;--k)returnk;//返回0，查找失败。否则，找到关键字为

key的结点的下标}顺序查找

应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。………………012n-3n-2n-1ni向量Vectorkeye.g:查找x=7的结点所在的数组元素的下标。7100100713设置哨兵的好处：在顺序表中总可以找到待查结点。否则，必须将判断条件i>=0加进for语句。template<classType>intSeqSearch(constVector<Type>&A,constTypekey,intN){A[0]=key;//将待查

key置于哨兵单元，可省掉越界检查。

for(intk=N;A[k]!=key;--k)returnk;//返回0，查找失败。否则，找到关键字为

key的结点的下标}顺序查找

应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。………………012n-3n-2n-1ni向量Vectorkeye.g:查找x=7的结点所在的数组元素的下标。7100100713设置哨兵的好处：在顺序表中总可以找到待查结点。否则，必须将判断条件i>=0加进for语句。template<classType>intSeqSearch(constVector<Type>&A,constTypekey,intN){A[0]=key;//将待查

key置于哨兵单元，可省掉越界检查。

for(intk=N;A[k]!=key;--k)returnk;//返回0，查找失败。否则，找到关键字为

key的结点的下标}顺序查找的性能

设n为结点的总数。

平均查找长度AVL（AverageSearchLength）

成功查找情况下：设每个结点的查找概率相等

1

ASL＝

∑((n-i+1)) i=n

＝（n+1）/21n顺序查找的性能

一般查找情况下（包括成功、不成功两种情况）：设成功与不成功两种情况可能性相等，每个结点的查找概率也相等。

1

ASL＝∑((n-i+1))+∑((n+1))

＝3(n+1)/40121001008133456310108100共有n+1=7种不成功的查找情况

2n

1

2(n+1)

1

1

i=n+1

i=n

折半查找（二分查找）应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。012mid=4但key=9<10,向左keye.g:查找key=9的结点所在的数组元素的下标地址。查找成功的情况：数组Vector如下图所示有序数组Vector：递增序Vector[i].Key<=Vector[I+1].Key;

i=1,2,……n查找范围：low（低下标）=1;high（高下标）=7（初始时为最大下标n）;比较对象：中点元素，其下标地址为mid=（low+high）/2=4

48

9

10

11

13

1934567high=7low=1折半查找应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。012mid=4keye.g:查找key=9的结点所在的数组元素的下标地址。查找成功的情况：数组Vector如下图所示有序数组Vector：递增序Vector[i].Key<=Vector[I+1].Key;

i=1,2,……n

查找范围：low（低下标）=1;high（高下标）=3

48

9

10

11

13

1934567high=3(mid-1)low=1折半查找应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。012mid=2keye.g:查找key=9的结点所在的数组元素的下标地址。查找成功的情况：数组Vector如下图所示有序数组Vector：递增序Vector[i].Key<=Vector[I+1].Key;

i=1,2,……n

查找范围：low（低下标）=1;high（高下标）=3比较对象：中点元素，其下标地址为mid=（low+high）/2=2

48

9

10

11

13

1934567high=3(mid-1)low=1折半查找应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。012mid=2;但key=9>8,向右keye.g:查找key=9的结点所在的数组元素的下标地址。查找成功的情况：数组Vector如下图所示有序数组Vector：递增序Vector[i].Key<=Vector[I+1].Key;

i=1,2,……n

查找范围：low（低下标）=1;high（高下标）=3比较对象：中点元素，其下标地址为mid=（low+high）/2=2

48

9

10

11

13

1934567high=3(mid-1)low=1折半查找应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。012mid=2keye.g:查找key=9的结点所在的数组元素的下标地址。查找成功的情况：数组Vector如下图所示有序数组Vector：递增序Vector[i].Key<=Vector[I+1].Key;

i=1,2,……n

查找范围：low（低下标）=3;high（高下标）=3

48

9

10

11

13

1934567high=3(mid-1)low=3(mid+1)折半查找应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。012mid=3keye.g:查找key=9的结点所在的数组元素的下标地址。查找成功的情况：数组Vector如下图所示有序数组Vector：递增序Vector[i].Key<=Vector[I+1].Key;

i=1,2,……n

查找范围：low（低下标）=3;high（高下标）=3比较对象：中点元素，其下标地址为mid=（low+high）/2=3

48

9

10

11

13

1934567high=3low=3折半查找应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。012mid=3;key=9且中点值也为9，找到keye.g:查找key=9的结点所在的数组元素的下标地址。查找成功的情况：数组Vector如下图所示有序数组Vector：递增序Vector[i].Key<=Vector[I+1].Key;

i=1,2,……n查找范围：low（低下标）=3;high（高下标）=3比较对象：中点元素，其下标地址为mid=（low+high）/2=3

48

9

10

11

13

1934567high=3low=3折半查找012mid=4但key=5<10,向左keye.g:查找key=5的结点所在的数组元素的下标地址。查找不成功的情况：数组Vector如下图所示有序数组Vector：递增序Vector[i].Key<=Vector[I+1].Key;

i=1,2,……n

查找范围：low（低下标）=1;high（高下标）=7（初始时为最大下标n）;比较对象：中点元素，其下标地址为mid=（low+high）/2

48

9

10

11

13

1934567high=7low=1折半查找012mid=4keye.g:查找key=5的结点所在的数组元素的下标地址。查找不成功的情况：数组Vector如下图所示有序数组Vector：递增序Vector[i].Key<=Vector[I+1].Key;

i=1,2,……n

查找范围：low（低下标）=1;high（高下标）=3;

48

9

10

11

13

1934567high=3（mid-1）low=1折半查找012mid=2keye.g:查找key=5的结点所在的数组元素的下标地址。查找不成功的情况：数组Vector如下图所示有序数组Vector：递增序Vector[i].Key<=Vector[I+1].Key;

i=1,2,……n

查找范围：low（低下标）=1;high（高下标）=3;比较对象：中点元素，其下标地址为mid=（low+high）/2=2

48

9

10

11

13

1934567high=3（mid-1）low=1折半查找012mid=2;但key=5<8,向左keye.g:查找key=5的结点所在的数组元素的下标地址。查找不成功的情况：数组Vector如下图所示有序数组Vector：递增序Vector[i].Key<=Vector[I+1].Key;

i=1,2,……n

查找范围：low（低下标）=1;high（高下标）=3;比较对象：中点元素，其下标地址为mid=（low+high）/2=2

48

9

10

11

13

1934567high=3（mid-1）low=1折半查找012mid=2keye.g:查找key=5的结点所在的数组元素的下标地址。查找不成功的情况：数组Vector如下图所示有序数组Vector：递增序Vector[i].Key<=Vector[I+1].Key;

i=1,2,……n

查找范围：low（低下标）=1;high（高下标）=1

48

9

10

11

13

1934567high=1（mid-1）low=1折半查找012mid=1keye.g:查找key=5的结点所在的数组元素的下标地址。查找不成功的情况：数组Vector如下图所示有序数组Vector：递增序Vector[i].Key<=Vector[I+1].Key;

i=1,2,……n

查找范围：low（低下标）=1;high（高下标）=1比较对象：中点元素，其下标地址为mid=（low+high）/2=1

48

9

10

11

13

1934567high=1low=1折半查找012mid=1;但key=5>4,向右keye.g:查找key=5的结点所在的数组元素的下标地址。查找不成功的情况：数组Vector如下图所示有序数组Vector：递增序Vector[i].Key<=Vector[I+1].Key;

i=1,2,……n

查找范围：low（低下标）=1;high（高下标）=1比较对象：中点元素，其下标地址为mid=（low+high）/2=1

48

9

10

11

13

1934567high=1low=1折半查找012mid=1;但key=5>4,向右keye.g:查找key=5的结点所在的数组元素的下标地址。查找不成功的情况：数组Vector如下图所示有序数组Vector：递增序Vector[i].Key<=Vector[I+1].Key;

i=1,2,……n

查找范围：low（低下标）=1;high（高下标）=1比较对象：中点元素，其下标地址为mid=（low+high）/2=1

48

9

10

11

13

1934567high=1low=2失败条件：low>high;处于间隙中的键值导致这种情况！折半查找template<classType>

intBinarySearch(constVector<Type>&A,constTypekey,intN){intlow=1,//所查找的那一段的下界结点的下标。high=N,//所查找的那一段的上界结点的下标。mid;//所查找的那一段的中间结点的下标。while(

low<=high){ mid=(low+high)/2;

if(A[mid]==key)returnmid;

elseif(key<A[mid])high=mid–1;

elselow=mid+1;}

return0;}//返回0，查找失败.。否则，找到值为

key的结点的索引或下标。折半查找的性能

最坏情况分析：设key和中点的二次比较的时间代价1

如果n=1,则low=high=mid,则代价为1，记为S（1）＝1

如果n是奇数，那么中点元素的左、右段各有(n-1)/2个元素

如果n是偶数，中点元素的左段有n/2-1个元素；右段有n/2个元素 因此，算法工作的那一段，最多有n/2项 ∴S（n）=1+S（n/2）

=1+1+S（n/22

）

=1+1+1+S（n/23

）

=1+1+1+………+1+S（n/2k

）注意：(n-1)/2=n/2注意：n/2=n/2总共K个1

当1<=n/2k<2时；则n/2k=1

此时：2k<=n<2k+1即k<=log2n<k+1

注意：k不可为小数，它是正整数。∴k=log2n 故：S（n）=1+log2n 折半查找的性能012mid=4

48

9

10

11

13

1934567high=7low=1012mid=4

48

9

10

11

13

1934567low=120high=88折半查找的性能

最坏情况分析：

定理：在最坏情况下，二分查找法的查找有序表的最大的比较次数为

1+log2n，大体上和log2n成正比。 也可用判定树的方法进行推导。 如：16735248key=k4?<<<<<<>>>>>>><<012345678489101113192912345678

当寻找key=8及小于、大 于8的键值的相应结点时， 查找次数最大。达到了判定 树的深度或高度。

注意：当判定树为n=2t-1（ t=1,2,3……）时，为满二叉树。否则，除最下一层外，余为满二叉树。折半查找的性能

平均情况分析（在成功查找的情况下）：设每个结点的查找概率相同都为1/n。为了简单起见，设结点个数为n=2t-1（t=1,2,3……）。 ∴经过1次比较确定的结点个数为1=20个，红色标识的结点。 经过2次比较确定的结点个数为2=21个，绿色标识的结点。 经过3次比较确定的结点个数为4=22个，蓝色标识的结点。 . . . 经过t次比较确定的结点个数为2t-1个，黑色标识的结点。 注意：∵20+21+22+

…+2t-1=2t-1∴最多经过t次比较可以找到有序表中的任何一个结点 e.g:当t=4时的例子：最多经过t=4次比较找到任何一个结点489101113192912345678324765778193999101112131415折半查找的性能

平均情况分析（在成功查找的情况下）：

ASL=(20×1

+21×2

+22×3

+

…+2t-1×t

)/n t =∑(i×2i-1)

/n i=1 =[(n+1)×(log2(n+1)-1)+1]/n =(n+1)×(log2(n+1)/n-1 =(n+1)×(log2(n+1)/n-1

结论：在成功查找的情况下，平均查找的代价约为ASL=log2(n+1)-1 或者简单地记为：ASL=log2n-1

折半查找的性能

平均情况分析（考虑成功、非成功查找两种的情况下）:为了简单起见，设结点个数为n=2t-1（t=1,2,3……）。 这样，成功查找的情况共有n种情况，非成功查找的情况共有n+1情况。 设每种情况出现的概率相同，即都为1/(2n+1)。1673524<<<<<>>>>>><<01234567489101113191234567

e.g:当t=3时的例子： 成功：最多经过t=3次比较 失败：都必须经过t=3次比较

t ASL=(∑(i×2i-1)＋t×(n+1))/(2n+1) i=1 =log2n+1/2差值查找

1、除中点下标的选择和二分查找不同外，其余类似。用于关键字值 均匀的情况，平均特性更好。

2、实现设mid为中点的下标。low为具有最小关键字值结点的下标，high为具有最大关键字值结点的下标。

mid=low+(high-low-1)×

(Eelement[high].key-Element[low].key）

(x-Element[low].key)Fibonacci查找

1、Fibonacci数 定义： F0=0 F1=1 Fk=Fk-1+Fk-2(K>=2)

如：0,1,1,2,3,5,8,13,21,34,55,89,144,233

2、实现设结点的总数为n=Fu-1，查找键值为key的结点首先比较keyST[Fu－1].key如果key<ST[Fu－1].key，则比较key=ST[Fu－1-

Fu－3].key如果key>ST[Fu－1].key，则比较key=ST[Fu－1+

Fu－3].key

3、注意：

参照下图，设根结点（或子树的根结点）同它的左、右儿子的下标之差为Fu－3那么，根结点（或子树的根结点）的左儿子的同它的儿子的下标之差为Fu－4

根结点（或子树的根结点）的右儿子的同它的儿子的下标之差为Fu－5

可以设计类似于二分查找的算法。但先要把Fu－3、Fu－4、Fu－5计算出来，它们也构成

Fibonacci数??＝？Fibonacci查找

4、e.g:n=F7-1=13-1=12个结点的查找过程

Fu－1=8Fu－3=3Fu－4=2Fu－5=1 3111271058<<<>>26419>><<<<ST[Fu－1].key差为Fu－3=3差为Fu－5=1差为Fu－4=2共Fu－1

－1＝8－1＝7个结点共Fu－2

－1＝5－1＝4个结点

5、优点：只用＋、－法，不用除法。平均查找速度更快。O（log2n）级。 缺点：最坏情况下比二分查找法差。必须先给出Fibonacci数。 注意：Fu－2=5如：0,1,1,2,3,5,8,13,21,34,55,89,144,233

0,1,2,3,4,5,6,7,8,9,10,11,12,13,注意：本示意图从1开始编号，书上是从0开始进行编号。二叉排序树

特点：用于频繁进行插入、删除、查找的所谓动态查找表。

二叉排序树(二叉查找树)：空或有一个根，根的左子树若非空，则左子树上的所有结点的关键 字值均小于根结点的值。根的右子树若非空，则右子树上的所有结点的关键字值 均大于根结点的值。根结点的左右子树同样是二叉排序树。12225030011020099e、g：二叉排序树(二叉查找树)，确定结点的大小，可根据结点类型进行定义。LNPEMCY105230216二叉排序树(ADT)template<classType>classBST{//二叉排序树的

ADTpublic:

BST(){}

//二叉排序树的构造函数。

~BST(){}

//二叉排序树的析构函数。

virtualintInsert(constType&x)=0;//插入

x。

virtualintRemove(constType&x)=0;//删除

x。

virtualconstType&Find(constType&x)=0;//查找值为

x的结点。

virtualint

IsFound(constType&x)=0;//若

x找到，则返回

1。

virtualconstType&FindMin()=0;//返回最小值。

virtualconstType&FindMax()=0;//返回最大值。

virtualint

IsEmpty()const=0;//二叉排序树为空，返回

1，否则为0。

virtualint

IsFull()const=0;//二叉排序树为满，返回

1，否则为0。

virtualvoidMakeEmpty()=0;//清除二叉排序树中的所有结点。};

二叉排序树的结点类

二叉排序树中的结点类的实现，为了表示简单，没有采用继承的方式，采用结构。二叉排序树BST的结点表示。

template<classType>struct

BSTNode{//二叉排序树的结点的表示。

Typedata; //结点的数据场。

BSTNode*left;//给出结点的左儿子的地址。

BSTNode*right;//给出结点的右儿子的地址。

int

BalanceFactor;//结点的平衡度，用于

AVL树。

int

Size;//以本结点为根的子树的所有结点的个数，用于顺序统计。

BSTNode():left(NULL),right(NULL),Size(1),BalanceFactor(1){} BSTNode(constTypex):data(x),left(NULL),right(NULL),Size(1), BalanceFactor(1){} BSTNode(constTypex,BSTNode*L,BSTNode*R): data(x),left(L),right(R),Size(1),BalanceFactor(1){} ~BSTNode(){}};

二叉排序树类template<classType>

classBinarySearchTree

：

publicBST<Type>{public:

BinarySearchTree():LastFind(NULL),Root(NULL){}~BinarySearchTree(){FreeTree(Root);}intInsert(constType&x){returnInsert(x,Root);} //插入

x到以

Root为根的二叉排序树。成功则返回

1。

constType&Find(constType&x){ return(LastFind=Find(x,Root))?LastFind->data:ItemNotFound

}//若查找

x成功，则返回二叉排序树中的相应数据项。否则，返回ItemNotFound。

constType&FindMin()const{ constBSTNode*p=FindMin(Root); returnp?p->data:ItemNotFound;}//返回二叉排序树中的最小的数据项。若树为空，返回

ItemNotFound。

constType&FindMax()const{ constBSTNode*p=FindMax(Root); returnp?p->data:ItemNotFound;}//返回二叉排序树中的最大的数据项。若树为空，返回

ItemNotFound。二叉排序树类int

IsFound(constType&x){returnFind(x,Root)!=NULL;}//若

x找到，则返回

True。

int

WasFound()const{returnLastFind!=NULL;}//最近一次查找成功，则返回

True。

intRemove(constType&x){returnRemove(x,Root);} //从二叉排序树中删除值为

x的结点，删除成功返回

True。

intRemoveMin(){returnRemoveMin(Root);} //从二叉排序树中删除最小结点，删除成功返回

True。

int

IsEmpty()const{returnRoot==NULL;} //二叉排序树为空，返回

True，否则为

False。

voidMakeEmpty(){FreeTree(Root);Root=NULL;}//清除二叉排序树中的所有结点。protected:

BSTNode<Type>*Root;const

BSTNode<Type>*LastFind;TypeItemNotFound;//用于查找失败时返回。

const

BSTNode<Type>*Find(constType&x，const

BSTNode<Type>*T)const;const

BSTNode<Type>*FindMin(const

BSTNode<Type>*T)const;const

BSTNode<Type>*FindMax(const

BSTNode<Type>*T)const;intInsert(constType&x，BSTNode<Type>*&T);intRemoveMin(

BSTNode<Type>*&T);intRemove(constType&x，BSTNode<Type>*&T);};

二叉排序树的查找分割式查找法：查找步骤：若根结点的关键字值等于查找的关键字，成功。 否则，若小于根结点的关键字值，查其左子树。大于根结点的关键 字值，查其右子树。在左右子树上的操作类似。12225030011020099105230216template<classType>BSTNode<Type>*BinarySearchTree<Type>::Find(constType&x,constBSTNode<Type>*T)const{while(T!=NULL) if(X<T->data)T=T->leftelseif(X>T->data)T=T->right;elsereturnT;returnNULL；}//查找失败，返回空。查找成功，返回指向相应结点的指针。二叉排序树的查找分析

156070302050平均情况分析（在成功查找两种的情况下）e.g:下述两种情况下的成功的平均查找长度ASL156070302050ASL=(1+2+2+3+3+3)/6=14/6AVL=(1+2+3+4+5+6)/6=21/6二叉排序树的查找分析

平均情况分析（在成功查找两种的情况下）在一般情况下，设P（n，i）且它的左子树的结点个数为i时的平均查找长度。右图的结点个数为n=6且i=3;则P（n,i）=P（6,3）=[1+(P(3)+1)*3+(P(2)+1)*2]/6=[1+(5/3+1)*3+(3/2+1)*2]/6注意：这里P(3)、P(2)是具有3个结点、2个结点的二叉排序树的平均查找长度。在一般情况下，P（i）为具有i个结点二叉排序树的平均查找长度。

P(3)＝（1+2+2）/3=5/3P(2)＝（1+2）/2=3/2∴P（n,i）=[1+(P(i)+1)*i+(P(n-i-1)+1)*(n-i-1)]/n∴n-1 P（n）=∑

P（n,i）/n i=0 <=2(1+I/n)lnn因为：

2(1+I/n)lnn≈1.38logn故：P(n)=O(logn)156070302050左子树0到n-1个结点右子树n-1到0个结点插入操作插入算法：首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。12225030011028099e、g：将数的序列：122、99、250、110、300、280作为二叉排序树的结 点的关键字值，生成二叉排序树。12212299122250991222501109912225030011099插入操作插入算法：输入一系列数据，分别置为结点的数据场之值。至特定的数据时结束。

template<classType>int

BinarySearchTree<Type>::Insert(constType&x,BSTNode<Type>*&T){if(T==NULL){T=newBSTNode<Type>(x);

return1;}//新结点插入。

else if(x<T->data)returnInsert(x,T->left)//转向左子树。

elseif(x>T->data)returnInsert(x,T->right)//转向右子树。

return0；//若结点已经存在，返回不必重复插入标志。}//插入结点到以

T为根的二叉排序树中去。插入成功返回

1，插入失败返回

0。

12225030011099280思考：设计一个非递归的插入程序时，应注意的问题？删除操作

叶子结点：直接删除，更改它的父亲结点的相应指针场为空。如：删除数据场为15、70的结点。15607030205060302050

子树的根结点：若被删结点的左儿子为空或者右儿子为空。如何处理呢？删除操作12225030011020099105230216400450500子树的根结点：若被删结点的左儿子为空。

如下图所示，删除结点的数据场的关键字值为为99的结点。被删结点122250300200230216400450500110105删除99删除操作12225030011020099105330316400450500被删结点122250300230216400450500删除33011099105子树的根结点：若被删结点的右儿子为空。如下图所示，删除结点的数据场的关键字值为为330的结点。316删除操作

12225030011020099105330316400450500被删结点结论：·将被删结点的另一儿子作为它的父亲结点的儿子，究竟是作为左儿子还是右儿子依原被删结点和其父亲结点的关系而定。

·释放被删结点的空间。这样，就同被删结点是叶子的情况统一起来了。被删结点子树的根结点：若被删结点的左儿子为空或者右儿子为空。如下图所示，删除结点的数据场的关键字值为为99、330的结点。删除操作

子树的根结点：若被删结点的左、右子树皆不空，则：通常的做法：选取“替身”取代被删结点。有资格充当该替身的是谁哪？ 左子树中最大的结点(被删结点的左子树中的最右的结点，其右儿子指针场为空)或右子树中最小的结点(被删结点的右子树中的最左的结点，其左儿子指针场为空)，参看下图。 要点：维持二叉排序树的特性不变。在中序周游中紧靠着被删结点的结点才有资格作为“替身”。12225030011020099105330316400450500被删结点替身替身11025030010520099330316400450500做法：将替身的数据场复制到被删结点的数据场。将结点的左儿子作为的父结点的右儿子。11011099注意：结点右儿子必为空结点的父结点为11011099删除操作

12225030011020099105330316400450500被删结点替身替身20025030011099105400450500子树的根结点：若被删结点的左、右子树皆不空，则：通常的做法：选取“替身”取代被删结点。有资格充当该替身的是谁哪？ 左子树中最大的结点(被删结点的左子树中的最右的结点，其右儿子指针场为空)或右子树中最小的结点(被删结点的右子树中的最左的结点，其左儿子指针场为空)，参看下图。 要点：维持二叉排序树的特性不变。在中序周游中紧靠着被删结点的结点才有资格作为“替身”。做法：将替身的数据场复制到被删结点的数据场。将结点的右儿子作为的父结点的左儿子。注意：结点左儿子必为空结点的父结点为200200200200250330316删除操作

12225030011020099105230216400450500被删结点替身替身子树的根结点：若被删结点的左、右子树皆不空，则：通常的做法：选取“替身”取代被删结点。有资格充当该替身的是谁哪？ 左子树中最大的结点(被删结点的左子树中的最右的结点，其右儿子指针场为空)或右子树中最小的结点(被删结点的右子树中的最左的结点，其左儿子指针场为空)，参看下图。 要点：维持二叉排序树的特性不变。在中序周游中紧靠着被删结点的结点才有资格作为“替身”。结论：·先将替身的数据场复制到被删结点

·将原替身的另一儿子作为它的父亲结点的儿子，究竟是作为左儿子还是右儿子依原被删结点和其父亲结点的关系而定。

·释放原替身结点的空间。删除操作的实现template<classType>int

BinarySearchTree<Type>::Remove(constType&x,BSTNode<Type>*&T){BSTNode<Type>*p;if(T==NULL)return0;//删除失败，返回

0。

elseif(x<T->data)returnRemove(x,T->left);//转向左子树。

elseif(x>T->data)returnRemove(x,T->right);//转向右子树。

elseif(T->left!=NULL&&T->right!=NULL){//被删结点的左右儿子非空。

p=(BSTNode<Type>*)FindMin(T->right); T->data=p->data;//复制右子树最小结点数据值。

returnRemoveMin(T->right);//删除被删结点的右子树的最小结点。

}p=T;//处理被删结点的至少一个儿子结点为空的情况。T=(T->left==NULL)?T->right:T->left;deletep;return1；}//删除成功，返回1。删除失败，返回

0。

12225030011020099105400450500被删结点替身删除操作的实现template<classType>int

BinarySearchTree<Type>::RemoveMin(BSTNode<Type>*&T){if(T==NULL)return0;elseif(T->left!=NULL) returnRemoveMin(T->left);BSTNode<Type>*p;p=T;T=T->right;deletep;return1；}//删除

T的最左方的左后代，删除成功，返回1。删除失败，返回

0。12225030011020099105400450500顺序统计求出序列中的第k个大的或小的结点。实现：设二叉排序树中的每一个结点附加了一个信息

size，它给出以该结点为根的子树中的所有结点的个数(注意：包括根结点本身在内)。这样我们就可以利用信息size，求得第k个最小的结点。则：

设

SL为任何一个结点x的左子树中的结点个数的总和。

1、在

k<SL+1时，那么第k个最小的结点存在于结点x的左子树之中，下一步应转向它的左子树寻找第

k个小的结点。

2、若k=SL+1，那么结点x即为所求，因为左子树上已经有SL=k–1个小于结点x的结点。

3、若k>SL+1时，那么第k个最小的结点存在于结点x的右子树之中，由于结点x和它的左子树中的结点都小于第k小的结点，所以下一步只需在结点x的右子树中寻找第

(k-SL-1)的结点就可以了。

SL

SR

X

SL

SR

X

SL

SR

X(1)K<SL+1