? 集合及其表示
? 并查集
? 静态搜索表
? 二叉搜索树
? AVL树
集合基本概念
集合及其表示
? 集合是成员 (对象或元素 )的一个群集。
集合中的成员可以是原子 (单元素 )，也
可以是集合。
? 集合的成员必须互不相同。
? 在算法与数据结构中所遇到的集合，其
单元素通常是整数、字符、字符串或指
针，且同一集合中所有成员具有相同的
数据类型。
colour = { red,orange,yellow,green,
black,blue,purple,white }
name = {,An”,“Cao”,“Liu”,“Ma”,
“Peng”,“Wang”,“zhang” }
? 集合中的成员一般是无序的，但在表示
它时，常写在一个序列里。
? 常设定集合中的单元素具有线性有序关
系，此关系可记作,<”，表示“优先
于”。
? 整数、字符和字符串都有一个自然线性
顺序。指针也可依据其在序列中安排的
位臵给予一个线性顺序。
集合 (Set)的抽象数据类型
template <class Type> class Set {
Set (int MaxSetSize), MaxSize(MaxSetSize);
void MakeEmpty (Set& s);
int AddMember (Set& s,const Type x);
int DelMember (Set& s,const Type& x);
A?B 或 A+B A?B 或 A?B A-B
A A AB BB
void Assign (Set& s1,Set& s2);
void Union (Set& s1,Set& s2);
void Intersection (Set& s1,Set& s2);
void Difference (Set& s1,Set& s2);
int Contains (Set& s,const Type& x);
int Equal (Set& s1,Set& s2);
int SubSet (Set& s1,Set& s2);
}
用位向量实现集合抽象数据类型
? 当集合是全集合 { 0,1,2,…,n }的一个子
集，且 n是不大的整数时，可用位 (0,1)向量
来实现集合。
? 当全集合是由有限的可枚举的成员组成的
集合时，可建立全集合成员与整数 0,1,
2,… 的一一对应关系，用位向量来表示该
集合的子集。
集合的位向量 (bit Vector)类的定义
#include <assert.h>
const int DefaultSize = 100;
class Set {
private:
int * bitVector;
int MaxSize;
public:
Set ( int MaxSetSize = DefaultSize );
~Set ( ) { delete [ ] bitVector; }
void MakeEmpty ( ) {
for ( int i = 0; i < MaxSize; i++ )
bitVector[i] = 0;
}
int GetMember ( const int x ) {
return x >= 0 && x < MaxSize?
bitVector[x], -1; }
int AddMember ( const int x );
int DelMember ( const int x );
Set& operator = ( Set& right );
Set& operator + ( Set& right );
Set& operator * ( Set& right );
Set& operator - ( Set& right );
int Contains ( const int x );
int SubSet ( Set& right );
int operator == ( Set& right );
};
使用示例
Set s1,s2,s3,s4,s5; int index,equal;
for ( int k = 0; k < 10; k++ ) //集合赋值
{ s1.AddMember( k ); s2.AddMember( k +7 ); }
// s1, { 0,1,2,…,9 },s2, { 7,8,9,…,16 }
s3 = s1+s2; //求 s1与 s2的并 { 0,1,…,16 }
s4 = s1*s2; //求 s1与 s2的交 { 7,8,9 }
s5 = s1-s2; //求 s1与 s2的差 { 0,1,…,6 }
// s1, { 0,1,2,…,9 }
index = s1.SubSet ( s4 ); //s4在 s1中首次匹配
cout << index << endl; //位置, index = 7
// s1, { 0,1,2,3,4,5,6,7,8,9 }
// s4, { 7,8,9 }
equal = s1 == s2; //集合 s1与 s2比较相等
cout << equal << endl; //为 0,两集合不等
用位向量实现集合时部分操作的实现
Set,,Set (int MaxSetSize),
MaxSize (MaxSetSize) {
assert ( MaxSize > 0 );
bitVector = new int [MaxSize];
assert ( bitVector != 0 );
for ( int i = 0; i < MaxSize; i++ )
bitVector[i] = 0;
}
int Set,,Addmember ( const int x ) {
assert ( x >= 0 && x < MaxSize );
if ( ! bitVector[x] )
{ bitVector[x] = 1; return 1; }
return 0;
}
int Set,,DelMember ( const int x ) {
assert ( x >= 0 && x < MaxSize );
if ( bitVector[x] )
{ bitVector[x] = 0; return 1; }
return 0;
}
Set& Set,,operator = ( Set& right ) {
assert ( MaxSize == right.MaxSize );
for ( int i = 0; i < MaxSize; i++ )
bitVector[i] = right.bitVector[i];
return *this;
}
int Set,,Contains ( const int x ) {
assert ( x >= 0 && x < MaxSize );
return bitVector[x];
}
Set& Set,,operator + ( Set& right ) {
assert ( MaxSize == right.MaxSize );
Set temp ( MaxSize );
for ( int i = 0; i < MaxSize; i++ )
temp.bitVector[i] =
bitVector[i] || right.bitVector[i];
return temp;
}
this
right
temp
0 1 1 1 0 0 0 0 1 1 0
0 0 1 0 0 1 0 1 0 1 0
0 1 1 1 0 1 0 1 1 1 0
Set& Set,,operator * ( Set & right ) {
assert ( MaxSize == right.MaxSize );
Set temp ( MaxSize );
for ( int i = 0; i < MaxSize; i++)
temp.bitVector[i] =
bitVector[i] && right.bitVector[i];
return temp;
}
this
right
temp
0 1 1 1 0 0 0 0 1 1 0
0 0 1 0 0 1 0 1 0 1 0
0 0 1 0 0 0 0 0 0 1 0
Set& Set,,operator - ( Set & right ) {
assert ( MaxSize == right.MaxSize );
Set temp ( MaxSize );
for ( int i = 0; i < MaxSize; i++ )
temp,bitVector[i] =
bitVector[i] && !right.bitVector[i];
return temp;
}
this
right
temp
0 1 1 1 0 0 0 0 1 1 0
0 0 1 0 0 1 0 1 0 1 0
0 1 0 1 0 0 0 0 1 0 0
int Set,,operator == ( Set& right ) {
assert ( MaxSize == right.MaxSize );
for ( int i = 0; i < MaxSize; i++)
if ( bitVector[i] != right.bitVector[i] )
return 0;
return 1;
}
this
right
0 0 1 1 0 0 0 0 1 1 0
0 0 1 0 0 1 0 1 0 1 0
i
int Set,,SubSet (Set& right ) {
assert ( MaxSize == right.MaxSize );
for ( int i = 0; i < MaxSize; i++)
if (bitVector[i] && ! right.bitVector[i])
return 0;
return 1;
}
this
right
0 0 1 1 0 0 0 0 1 1 0
0 0 1 0 0 1 0 1 0 1 01 1 0 1 1 0 1 0 1 0 1
i
用有序链表实现集合的抽象数据类型
用带表头结点的有序链表表示集合
first
first 08 17 23 35 49 72
? 用有序链表来表示集合时，链表中的每个
结点表示集合的一个成员。
? 各结点所表示的成员 e0,e1,…,en 在链表中
按升序排列，即 e0 < e1 < … < en。
? 集合成员可以无限增加。因此，用有序链
表可以表示无穷全集合的子集。
template <class Type> class SetList;
template <class Type> class SetNode {
friend class SetList<Type>;
public:
SetNode (const Type& item ),
data (item),link (NULL);
private:
Type data;
SetNode<Type> * link;
};
集合的有序链表类的定义
template <class Type> class SetList {
private:
SetNode<Type> *first,*last;
//有序链表的表头指针,表尾指针
public:
SetList ( ) //构造函数
{ first = last = new SetNode<Type>(0); }
~SetList ( ) { MakeEmpty( ); delete first; }
void MakeEmpty ( ); //置空集合
int AddMember ( const Type& x );
int DelMember ( const Type& x );
SetList<Type> & operator = ( SetList<Type>&
right ); //将集合 right赋给集合 this
SetList<Type> & operator + ( SetList<Type>&
right ); //求集合 this与集合 right的并
SetList<Type> & operator * ( SetList<Type>&
right ); //求集合 this与集合 right的交
SetList<Type> & operator - ( SetList<Type>&
right ); //求集合 this与集合 right的差
int Contains ( const Type& x );
//判 x是否集合的成员
int operator == ( SetList<Type>& right );
//判集合 this与集合 right相等
Type& Min ( ); //返回集合中最小元素值
Type& Max ( ); //返回集合中最大元素值
}
集合的搜索、加入和删除操作
template <class Type> int SetList<Type>,:
Contains ( const Type& x ) {
//若 x是集合成员,则函数返回 1,否则返回 0
SetNode<Type> * temp = first->link;
while ( temp != NULL && temp->data < x )
temp = temp->link; //循链搜索
if ( temp != NULL && temp->data == x )
return 1; //找到,返回 1
else return 0; //未找到,返回 0
}
template <class Type> int SetList<Type>,:
AddMember ( const Type& x ) {
SetNode<Type> *p = first->link,*q = first;
while ( p != NULL && p->data < x )
{ q = p; p = p->link; } //循链扫描
if ( p != NULL && p->data == x ) return 0;
//集合中已有此元素
SetNode<Type> * s = new SetNode (x);
s->link = p; q->link = s; //链入
if ( p == NULL ) last = s;
//链到链尾时改链尾指针
return 1;
}
template <class Type> int SetList<Type>,:
DelMember ( const Type& x ) {
SetNode<Type> * p = first->link,* q = first;
while ( p != NULL && p->data < x )
{ q = p; p = p->link; } //循链扫描
if ( p != NULL && p->data == x ) { //找到
q->link = p->link; //重新链接
if ( p == last ) last = q;
//删去链尾结点时改链尾指针
delete p; return 1; //删除含 x结点
}
else return 0; //集合中无此元素
}
用有序链表表示集合时的几个重载函数
template <class Type>
SetList<Type>& SetList<Type>,,
operator = ( SetList<Type>& right ) {
//复制集合 right到 this
SetNode<Type> * pb = right.first->link; //源
SetNode<Type> * pa = first = //目标
new SetNode<Type>;
while ( pb != NULL ) { //逐个结点复制
pa->link = new SetNode<Type>(pb->data);
pa = pa->link; pb = pb->link;
}
pa->link = NULL; last = pa;
return *this; //目标链表收尾
}
//求集合 this与集合 right的并,结果通过临时
//集合 temp返回,this集合与 right集合不变。
template <class Type>
SetList<Type>& SetList<Type>,,
operator + ( SetList<Type>& right ) {
first
right.first 08 17 23 49
temp.first 23
17 35
pa
pbpc
08 17 23 35 49
SetNode<Type> *pb = right.first->link;
SetNode<Type> *pa = first->link;
SetList<Type> temp;
SetNode<Type> *pc = temp.first;
while ( pa != NULL && pb != NULL ) {
if ( pa->data == pb->data ) { //共有元素
pc->link=new SetNode<Type>(pa->data);
pa = pa->link; pb = pb->link;
} else if ( pa->data < pb->data ) {
pc->link=new SetNode<Type>(pa->data);
pa = pa->link;
} else { //pa->data > pb->data
pc->link=new SetNode<Type>(pb->data);
pb = pb->link;
}
pc = pc->link;
}
if ( pa != NULL ) pb = pa; //pb指未扫完集合
while ( pb != NULL ) { //向结果链逐个复制
pc->link = new SetNode<Type>(pb->data);
pc = pc->link; pb = pb->link;
}
pc->link = NULL; temp.last = pc; //链表收尾
return temp;
}
template <class Type> int SetList<Type>,,
operator == ( SetList<Type> & right ) {
SetNode<Type> * pb = right.first->link;
SetNode<Type> * pa = first->link;
while ( pa != NULL && pb != NULL )
if ( pa->data == pb->data ) //相等,继续
{ pa = pa->link; pb = pb->link; }
else return 0; //不等时中途退出,返回 0
if ( pa != NULL || pb != NULL ) return 0;
//链不等长时,返回 0
return 1;
}
并查集 (Union-Find Sets)
? 并查集支持以下三种操作：
? Union (Root1,Root2) //并操作
? Find (x) //搜索操作
? UFSets (s) //构造函数
? 对于并查集来说，每个集合用一棵树表示。
? 为此，采用 树的双亲表示 作为集合存储表示。
集合元素的编号从 0到 n-1。其中 n 是最大
元素个数。
? 在 双亲表示 中,第 i 个数组元素代表包含
集合元素 i 的树结点 。根结点的双亲为 -1，
表示集合中的元素个数。
? 在同一棵树上所有结点所代表的集合元素
在同一个子集合中。
? 为此，需要有两个映射：
? 集合元素到存放该元素名的树结点间的
对应；
? 集合名到表示该集合的树的根结点间的
对应。
? 设 S1= {0,6,7,8 },S2= { 1,4,9 },S3= { 2,3,
5 }
集合名 指针
0 S1
1 S2
2 S3
0 4 2
76 8 1 9 3 5
? 为简化讨论, 忽略实际的集合名, 仅用表
示集合的树的根来标识集合 。
? 初始时,用构造函数 UFSets(s) 构造一个森
林,每棵树只有一个结点,表示集合中各元
素自成一个子集合 。
? 用 Find(i) 寻找集合元素 i 的根 。 如果有两
个集合元素 i 和 j,Find(i) == Find(j),表明
这两个元素在同一个集合中,
? 如果两个集合元素 i 和 j 不在同一个集合
中,可用 Union(i,j) 将它们合并到一个集合
中 。
S1 ? S2的可能的表示方法
下标
parent
集合 S1,S2 和 S3 的双亲表示
-1 4 -1 2 -1 2 0 0 0 4
0 1 2 3 4 5 6 7 8 9
0
76 8 4
1 9
4
1 90
876
const int DefaultSize = 10;
class UFSets { //并查集类定义
private:
int *parent; //集合元素数组
int size; //集合元素的数目
public:
UFSets ( int s = DefaultSize ); //构造函数
~UFSets ( ) { delete [ ] parent; } //析构函数
const UFSets& operator = (UFSets& right);
//重载函数, 集合赋值
void Union ( int Root1,int Root2 );
//基本例程, 两个子集合合并
int Find ( int x );
//基本例程, 搜寻集合 x的根
void UnionByHeight ( int Root1,int Root2 );
//改进例程, 压缩高度的合并算法
};
UFSets,,UFSets ( int s ) { //构造函数
size = s; //集合元素个数
parent = new int [size]; //双亲指针数组
for ( int i = 0; i < size; i++ ) parent[i] = -1;
//每一个自成一个单元素集合
}
?并查集操作的算法
? 查找
-5 0 1 2 3
0 1 2 3 4
Find (4)
Find (3) = 3
Find (2) =2
Find (1) = 1
Find (0) = 0
= -5 < 0 结束
int UFSets,,Find ( int x ) {
if ( parent [x] < 0 ) return x;
else return Find ( parent [x] );
}
-5 0 1 2 3parent
Parent[4]
=3 Parent[3]
=2Parent[2]
=1
Parent[1]
=0
Parent[0]
=-5
0 1 2 3 4
void UFSets,,Union ( int Root1,int Root2 ) {
//求两个不相交集合 Root1与 Root2的并
parent[Root2] = Root1;
//将 Root2连接到 Root1下面
}
? Find和 Union操作性能不好。假设最初 n
个元素构成 n 棵树组成的森林,parent[i]
= -1。做处理 Union(n-2,n-1),…,Union(1,
2),Union(0,1)后，将产生退化的树。
? 合并 -1-1 -1 -1 -10 2 3 4
-3
-5
0
3
2
1
3
3
4 1
3 3
22
0
2
3
1
4
Union(0,1)
-2
3
-4
1
4
2
1
2
3
4
Union(1,2)
Union(2,3)
Union(3,4)
? 执行一次 Union操作所需时间是 O(1),n-1
次 Union操作所需时间是 O(n)。
? 若再执行 Find(0),Find(1),…,Find(n-1),若
被搜索的元素为 i，完成 Find(i) 操作需要时
间为 O(i),完成 n 次搜索需要的总时间将达
到
? 改进的方法
? 按树的结点个数合并
? 按树的高度合并
? 压缩元素的路径长度
?
?
?
n
i
ni
1
2OO )()(
? 按树结点个数合并
?结点个数多的树的根结点作根
-1-1 -1 -1 -1
0
1
2 3 4
-1 -1
0
-7
2
5 6
-5 -2
2 2
3 3
2 0
1
3
4
5
6
2
3 3 0
2 0
56
2
31
4
Union(2,0)
void UFSets,,
WeightedUnion ( int Root1,int Root2 ) {
//按 Union的加权规则改进的算法
int temp = parent[Root1] + parent[Root2];
if ( parent[Root2] < parent[Root1] ) {
parent[Root1] = Root2; //Root2中结点数多
parent[Root2] = temp; //Root1指向 Root2
}
else {
parent[Root2] = Root1; //Root1中结点数多
parent[Root1] = temp; //Root2指向 Root1
}
}
? 按树高度合并
? 高度高的树的根结点作根
-0-0 -0 -0 -0
0
1
2 3 4
-0 -0
0
-2
2
5 6
-2 -1
2 2
3 3
2 0
1
3
4
5
6
2
3 3 0
2 0
56
2
31
4
Union(2,0)
Union操作的折叠规则
? 为进一步改进树的性能, 可以使用如下折叠
规则来, 压缩路径, 。 即,如果 j 是从 i 到
根的路径上的一个结点, 且 parent[j] ?
root[j],则把 parent[j] 臵为 root[i]。
0 0
6 7 8 6 7 8
1 9 1
9
3 5
3
5
从 i = 5 压缩路径
int UFSets,,CollapsingFind ( int i ) {
//使用折叠规则的搜索算法
for ( int j = i; parent[j] >= 0; j = parent[j] );
//让 j 循双亲指针走到根
while ( i != j ) { //换 parent[i] 到 j
int temp = parent[i];
parent[i] = j; i = temp;
}
return j;
}
搜索 (Search)的概念
静态搜索表
? 所谓 搜索,就是 在数据集合中寻找满足某
种条件的数据对象 。
? 搜索的结果通常有两种可能：
? 搜索成功,即找到满足条件的数据对象
这时,作为结果,可报告该对象在结构中
的位臵,还可给出该对象中的具体信息。
? 搜索不成功,或搜索失败。作为结果,
应报告一些信息,如失败标志、位臵等。
? 通常称用于搜索的数据集合为 搜索结构,
它是由 同一数据类型的对象 (或记录 )组成。
? 在每个对象中有若干属性，其中有一个属
性，其值可唯一地标识这个对象。称为关
键码。 使用基于关键码的搜索，搜索结果
应是唯一的。 但在实际应用时，搜索条件
是多方面的，可以 使用基于属性的搜索方
法，但搜索结果可能不唯一。
? 实施搜索时有两种不同的环境。
? 静态环境,搜索结构在插入和删除等操
作的前后不发生改变。 ? 静态搜索表
? 动态环境,为保持较高的搜索效率,搜
索结构在执行插入和删除等操作的前后
将自动进行调整，结构可能发生变化。
? 动态搜索表
静态搜索表
template <class Type> class dataList;
template <class Type> class Node {
friend class dataList<Type>;
private:
Type key;
other;
public:
Node ( const Type& value ), key (value) { }
Type getKey ( ) const { return key; }
void setKey ( Type k ) { key = k; }
};
template <class Type> class dataList {
protected:
Node <Type> *Element; //数据存储数组
int ArraySize,CurrentSize;
//数组最大长度和当前长度
public:
dataList ( int sz = 10 ), ArraySize (sz)
{ Element = new Node <Type> [sz]; }
virtual ~dataList ( ) { delete [ ] Element; }
friend ostream& operator <<
(ostream& OutStream,
const dataList<Type>& OutList );
friend istream & operator >>
( istream& InStream,
dataList<Type>& InList );
};
template <class Type> class searchList,
public dataList<Type> {
//作为派生类的静态搜索表的类定义
public,
searchList ( int sz = 10 ),
dataList<Type> (sz) { }
virtual ~searchList ( ) { }
virtual int Search ( const Type & x ) const;
};
template <class Type> istream& operator >>
( istream& InStream,dataList<Type>& InList )
{
//从输入流对象 InStream输入数据到表 InList中
cout <<,输入数组当前大小,,;
Instream >> InList.CurrentSize;
cout <<,输入数组元素值, \n”;
for ( int i = 0; i < InList.CurrentSize; i++ ) {
cout <<,元素, << i <<,,,;
InStream >> InList.Element[i];
}
return InStream;
}
template <class Type> ostream& operator <<
( ostream& OutStream,const dataList<Type>
& OutList ) {
//将表 OutList内容输出到输出流对象 OutStream
OutStream <<,数组内容, \n”;
for ( int i = 0; i < OutList.CurrentSize; i++ )
OutStream << OutList.Element[i] << ? ?;
OutStream << endl;
OutStream <<,数组当前大小,, <<
OutList.CurrentSize << endl;
return OutStream;
}
? 衡量一个搜索算法的时间效率的标准是：
在搜索过程中关键码的 平均比较次数 或 平
均读写磁盘次数 (只适合于外部搜索 ),也称
为 平均搜索长度 ASL(Average Search
Length),通常它是 搜索结构中对象总数 n
或文件结构中物理块总数 n 的函数 。
? 在静态搜索表中,利用数组元素的下标作为
数据对象的存放地址 。 搜索算法 根据给定
值 x,在数组中进行搜索 。 直到 找到 x在数组
中的位臵或可确定在数组中 找不到 x为止 。
? 另外衡量一个搜索算法还要考虑算法所需
要的存储量和算法的复杂性等问题。
顺序搜索 (Sequential Search)
? 所谓顺序搜索,又称线性搜索,主要用于在
线性结构中进行搜索 。
? 设若表中有 CurrentSize 个对象, 则顺序
搜索从表的先端开始,顺序用各对象的关键
码与 给定值 x进行比较,直到找到与其值相
等的对象,则搜索成功 ; 给出该对象在表中
的位臵 。
? 若整个表都已检测完仍未找到关键码与 x相
等的对象,则搜索失败 。 给出失败信息 。
template <class Type>
int searchList<Type>,:
Search ( const Type& x ) const {
//顺序搜索关键码为 x的数据对象,第 0号位置
//作为控制搜索自动结束的, 监视哨, 使用
Element[0].key = x; int i = CurrentSize;
//将 x送 0号位置设置监视哨
while ( Element[i].key != x ) i-- ;
//从后向前顺序搜索
return i;
}
const int Size = 10;
main ( ) { //顺序搜索的主过程
searchList<float> List1 (Size); //定义搜索表
float Target; int Location;
cin >> List1; cout << List1; //输入 List1
cout <<,搜索浮点数,,; cin >> Target;
if ( ( Location = List1.search ( Target ) ) != 0 )
cout <<,找到位置在, << Location <<
endl; //搜索成功,输出找到的位置
else cout <<, 没有找到,\n”; //搜索失败
}
顺序搜索的平均搜索长度
??
?
?
?
?
???
1
0
1
0
n
i
i
n
i
iis u c c pcpA S L ) 1 (,
)( 1
1
???? ?
?
inpAS L
n
i
is u c c
设搜索 第 i 个 元素的概率为 pi,搜索到 第 i 个
元素所需 比较次数 为 ci,则搜索成功的平均
搜索长度,
在顺序搜索并设臵“监视哨”情形：
ci = n- i +1,i = n,n-1,?,1，因此
.)()(?
?
???????? n
i
s u c c
nnn
n
in
n
A S L
1 2
1
2
1111
在等概率情形,pi = 1/n,i = 1,2,?,n。
在搜索不成功情形,ASLunsucc = n+1.
template <class Type> int SearchList<Type>,:
Search ( const Type& x,int& loc ) const {
//顺序搜索的递归算法
if ( loc >= CurrentSize ) return -1;
else if ( Element[loc].getKey( ) == x )
return loc;
else return Search ( x,loc+1 );
}
基于有序顺序表的顺序搜索算法
template <class Type>
int searchList<Type>,:
Search ( const Type& x ) const {
//顺序搜索关键码为 x的数据对象
for ( int i = 0; i < CurrentSize; i++ )
if ( Element[i].key == x ) return i; //成功
else if ( Element[I].key > x ) break;
return -1;
//顺序搜索失败,返回失败信息
}
? 有序顺序表的顺序搜索
( 10,20,30,40,50,60 )
10
50
60
=
=
=
=
=
=
20
30
40
<
<
<
<
<
<
>
>
>
>
>
>
? ?
2
71
6
1 5
0
??? ?
?i
s u c c iA S L
? ?
7
27
61
7
1 5
0
??
?
?
?
?
?
???
?
?
?i
un s uc c
i
A S L
基于有序顺序表的折半搜索
? 设 n个对象 存放在一个有序顺序表中, 并
按其关键码从小到大排好了序 。
? 折半搜索时,先求位于搜索区间正中的对象
的下标 mid,用其关键码与 给定值 x比较,
? Element[mid].key == x,搜索成功 ；
? Element[mid].key > x,把搜索区间缩小
到表的 前半部分, 继续折半搜索 ；
? Element[mid].key < x,把搜索区间缩小
到表的 后半部分, 继续折半搜索 。
? 如果搜索区间已缩小到一个对象, 仍未找
到想要搜索的对象, 则搜索失败 。
搜索成功的例子
-1 0 1 3 4 6 8 10 126
0 1 2 3 4 5 6 7 8
搜索 low mid high6
6 8 10 12
5 6 7 8
low mid high
6 6
5
low mid high
6
搜索失败的例子
-1 0 1 3 4 6 8 10 125
0 1 2 3 4 5 6 7 8
搜索 low mid high5
6 8 10 12
5 6 7 8
low mid high
65
5
low mid high
5
template <class Type> class orderedList,
public dataList<Type> {
//有序表的类定义,继承了数据表
public:
orderedList (int sz = 10),
dataList<Type> (sz) { }
virtual ~orderedList ( ) { }
virtual int Search ( const Type& x ) const;
};
template <class Type>
int orderedList<Type>,,//折半搜索算法
BinarySearch ( const Type & x,const int low,
const int high ) const {
//折半搜索的递归算法
int mid = -1;
if ( low <= high ) {
mid = ( low + high ) / 2;
if ( Element[mid].key < x )
mid = BinarySearch ( x,mid +1,high );
else if ( Element[mid].key > x )
mid = BinarySearch ( x,low,mid -1 );
}
return mid;
}
template<class Type> int orderedList <Type>:,
BinarySearch ( const Type & x ) const {
//折半搜索的迭代算法
int high = CurrentSize-1,low = 0,mid;
while ( low <= high ) {
mid = ( low + high ) / 2;
if ( Element[mid].key < x )
low = mid + 1; //右缩搜索区间
else if ( Element[mid].key ) > x )
high = mid - 1; //左缩搜索区间
else return mid; //搜索成功
}
return -1; //搜索失败
}
? 搜索成功时检测指针停留在树中某个结点。
? 搜索不成功时检测指针停留在某个外结点
（失败结点）。
35
15 45
502510
20 30
搜索 22
搜索 45
? 有序顺序表的折半搜索的判定树
( 10,20,30,40,50,60 )
10 50
=
=
==
=
=
30
<
<
<
<
<
<
>
>
> >
> >
20 40 60
(2*1+3*6)/7
折半搜索性能分析
? 若设 n = 2h-1,则描述折半搜索的判定树是
高度为 h-1 的满二叉树 。
2h = n+1,h = log2(n+1)。
? 第 0层结点有 1个,搜索第 0层结点要比较 1次 ;
第 1层结点有 2个,搜索第 1层结点要比较 2
次 ; …,第 i (0 ? i ? h) 层结点有 2i 个,搜索第
i 层结点要比较 i+1次, … 。
? 假定每个结点的搜索概率相等，即 pi = 1/n，
则搜索成功的平均搜索长度为
)221)(23
2211
11
122
1
1
0
1
??
?
?
?
?
????????
???????? ??
hh
n
i
i
n
0i
iis u c c
hh
(
n
C
n
CpA S L
?
121)(
221)( 232211 1221
????
???????????? ??
h
hh
h
hh?
11)(log11)(log
1
)1)(1 ) l o g((
1
1)21)((
1
22
2
?????
?
?
????????
nn
n
n
nnn
n
h
n
A S L
h
s u c c
可以用归纳法证明
这样
定义
二叉搜索树或者是一棵空树，或者是具有
下列性质的二叉树：
?每个结点都有一个作为搜索依据的关键
码 (key)，所有结点的关键码互不相同。
?左子树 (如果存在 )上 所有结点的关键码
都小于根结点的关键码 。
?右子树 (如果存在 )上 所有结点的关键码
都大于根结点的关键码 。
?左子树和右子树也是二叉搜索树。
二叉搜索树 ( Binary Search Tree )
35
15 45
50402510
20 30
二叉搜索树例
? 结点左子树上
所有关键码小
于结点关键码
? 右子树上所有
关键码大于结
点关键码
? 注意：若从根结点到某个叶结点有一条路
径，路径左边的结点的关键码不一定小于
路径上的结点的关键码。
n 个结点的二叉搜索树的数目
【例】 3 个结点的二叉搜索树
5
1*2*3
4*5*6*
4
1C
13
1 3
3*2 ???
1
2
2
1
3
3 1 3
2
1
2
3
1
2
3
{123} {132} {213} {231} {312} {321}
二叉搜索树的类定义
#include <iostream.h>
template <class Type> class BST;
template <class Type> Class BstNode <Type>,
public BinTreeNode {
friend class BST <Type>;
如果对一棵二叉搜索树进行中序遍历，可
以按从小到大的顺序，将各结点关键码排列
起来，所以也称二叉搜索树为二叉排序树。
protected:
Type data;
BstNode<Type> *leftChild,*rightChild;
};
public:
BstNode ( ), leftChild (NULL),
rightChild (NULL) { } //构造函数
BstNode ( const Type d ), data (d),
leftChild (NULL),rightChild (NULL) { }
BstNode ( const Type d = 0,BstNode<Type> *
L = NULL,BstNode<Type> *R = NULL)
,data (d),leftChild (L),rightChild (R) { }
Type GetData ( ) { return data; }
~BstNode ( ) { } //析构函数
};
template <class Type> class BST
,public BinaryTree<Type> {
private:
BstNode<Type> *root; //根指针
Type RefValue; //数据输入停止的标志
void MakeEmpty ( BstNode<Type> *& ptr );
void Insert ( Type& x,
BstNode<Type> *& ptr ); //插入
void Remove ( Type& x,
BstNode<Type> *& ptr ); //删除
void PrintTree ( BstNode<Type> * ptr ) const;
BstNode<Type> *Copy
( const BstNode<Type> * ptr ); //复制
BstNode<Type> *Find ( Type& x,
BstNode<Type> * ptr ); //搜索
BstNode<Type> *Min ( BstNode<Type> *
ptr ) const; //求最小
BstNode<Type> *Max ( BstNode<Type> *
ptr ) const; //求最大
public:
BST ( ), root (NULL) { } //构造函数
BST ( Type value ), RefValue (value),
root (NULL) { } //构造函数
~BST ( ); //析构函数
const BST& operator = ( const BST& Value );
void MakeEmpty ( )
{ MakeEmpty ( root ); root = NULL; }
void PrintTree ( ) const { PrintTree ( root ); }
int Find ( const Type& x ) //搜索元素
{ return Find ( x,root ) != NULL; }
Type Min ( return Min ( root )->data );
Type Max ( return Max ( root )->data );
void Insert ( const Type& x )
{ Insert ( x,root ); } //插入新元素
void Remove (const Type& x )
{ Remove ( x,root ); } //删除含 x的结点
}
在二叉搜索树上进行搜索,是一个从根结
点开始，沿某一个分支逐层向下进行比较判
等的过程 。它可以是一个递归的过程。
二叉搜索树上的搜索
? 假设想要在二叉搜索树中搜索关键码为 x
的元素, 搜索过程从根结点开始 。
? 如果根指针为 NULL,则搜索不成功；否
则用给定值 x与根结点的关键码进行比较：
? 如果给定值等于根结点的关键码, 则搜
索成功 。
? 如果给定值小于根结点的关键码, 则继
续递归搜索根结点的左子树；
? 否则 。 递归搜索根结点的右子树 。
35
15 45
50402510
20 30
搜索 45
搜索成功
搜索 28
搜索失败
template <class Type>
BstNode<Type> * BST<Type>,,Find ( const
Type& x,BstNode<Type> * ptr ) const {
//二叉搜索树的递归的搜索算法
if ( ptr == NULL ) return NULL; //搜索失败
else if ( x < ptr->data ) //在左子树搜索
return Find ( x,ptr->leftChild );
else if ( x > ptr->data ) //在右子树搜索
return Find ( x,ptr->rightChild );
else return ptr; //相等,搜索成功
}
template <class Type>
BstNode <Type> * BST <Type>,,Find (const
Type& x,BstNode<Type> * ptr ) const {
//二叉搜索树的迭代的搜索算法
if ( ptr != NULL ) {
BstNode<Type> * temp = ptr; //从根搜索
while ( temp != NULL ) {
if ( temp->data == x ) return temp;
if ( temp->data < x )
temp = temp->rightChild; //右子树
else temp = temp->leftChild; //左子树
}
}
return NULL; //搜索失败
}
二叉搜索树的插入 35
15 45
50402510
20 30
28
每次结点的插入，都
要从根结点出发搜索插
入位臵，然后把新结点
作为叶结点插入。
插入新结点 28
? 为了向二叉搜索树中插入一个新元素, 必
须先检查这个 元素是否在树中已经存在 。
? 在插入之前, 先使用搜索算法在树中检查
要插入元素有还是没有 。
? 搜索成功, 树中已有这个元素,不再插入 。
? 搜索不成功, 树中原来没有关键码等于
给定值的结点, 把新元素加到搜索操作
停止的地方 。
递归的二叉搜索树插入算法
template <class Type> void BST<Type>::
Insert ( const Type& x,
BstNode<Type> * & ptr) {
if ( ptr == NULL ) { //空二叉树
ptr = new BstNode<Type> (x); //创建结点
if ( ptr == NULL )
{ cout <<,存储不足 " << endl; exit (1); }
}
else if ( x < ptr->data ) //在左子树插入
Insert ( x,ptr->leftChild );
else if ( x > ptr->data ) //在右子树插入
Insert ( x,ptr->rightChild );
}
输入数据，建立二叉搜索树的过程
输入数据 { 53,78,65,17,87,09,81,15 }
53 53
78
53
78
65
53
78
65
17
53
78
65 87
17
53
78
6509
17
87
53
78
65
81
17
8709
53
78
65
15
17
8709
81
template <class Type>
BST<Type>,,BST ( Type value ) {
//输入数据,建立二叉搜索树 。 RefValue 是输入
//结束标志。这个值应取不可能在输入序列中
//出现的值,例如输入序列的值都是正整数时,
//取 RefValue为 0或负数。
Type &x;
root = NULL; RefValue = value;
cin >> x;
while ( x != RefValue )
{ Insert ( x,root ); cin >> x; }
}
同样 3 个数据 { 1,2,3 }，输入顺序不同，
建立起来的二叉搜索树的形态也不同。这直
接影响到二叉搜索树的搜索性能。
如果输入序列选得不好，会建立起一棵单
支树，使得二叉搜索树的高度达到最大。
{2,1,3}
{1,2,3} {1,3,2} {2,3,1} {3,1,2} {3,2,1}
1
2
3
1
1 1
1
3
2 2
2
3
3
2
3
二叉搜索树的删除
? 在二叉搜索树中删除一个结点时, 必须将
因删除结点而断开的二叉链表重新链接起
来, 同时确保二叉搜索树的性质不会失去 。
? 为保证在删除后树的搜索性能不至于降低,
还 需要防止重新链接后树的高度增加 。
? 删除叶结点, 只需将其双亲结点指向它
的指针清零, 再释放它即可 。
? 被删结点缺右子树, 可以拿它的左子女
结点顶替它的位臵, 再释放它 。
? 被删结点缺左子树, 可以拿它的右子女
结点顶替它的位臵, 再释放它 。
? 被删结点左, 右子树都存在, 可以在它
的右子树中寻找中序下的第一个结点 (关
键码最小 ),用它的值填补到被删结点中,
再来处理这个结点的删除问题 。
53
78
65
17
8709
23
45
删除 45
缺右子树,用
左子女顶替
53
78
65
17
8709 23
88
53
78
88
17
9409 23
删除 78
缺左子树,用
右子女顶替
53
94
88
17
09 23
53
78
81
17
9409 45
删除 78
在右子树上找
中序下第一个
结点填补23
65
53
81
88
17
9409 45
23
65
二叉搜索树的删除算法
template <class Type> void BST <Type>,:
Remove (const Type& x,
BstNode<Type> * & ptr) {
BstNode<Type> * temp;
if ( ptr != NULL )
if ( x < ptr->data ) //在左子树中删除
Remove ( x,ptr->leftChild );
else if ( x > ptr->data ) //在右子树中删除
Remove ( x,ptr->rightChild );
else if ( ptr->leftChild != NULL &&
ptr->rightChild != NULL ) {
temp = ptr->rightChild;
while ( temp->leftChild != NULL )
temp = temp->leftChild;
//找 ptr右子树中序下第一个结点
ptr->data = temp->data; //填补上
Remove ( ptr->data,temp );
//在 temp为根的子树中删除该结点
}
else { // ptr结点只有一个或零个子女
temp = ptr;
if ( ptr->leftChild == NULL )
ptr = ptr->rightChild;
else if ( ptr->rightChild == NULL )
ptr = ptr->leftChild; //只有左子女
delete temp;
}
}
二叉搜索树性能分析
? 对于有 n 个关键码的集合，其关键码有 n!
种不同排列，可构成不同二叉搜索树有
(棵 )
? 用树的搜索效率来评价这些二叉搜索树。
C n nn 21 1?
? 例，已知关键码集合 { a1,a2,a3 } = { do,if,
to }，对应搜索概率 p1,p2,p3,在各搜索不
成功间隔内搜索概率分别为 q0,q1,q2,q3。
可能的二叉搜索树如下所示。
do
if
to
do
if
to
q0 q1
p1 q2
p2 q3
p3
q0 q1 q2 q3
p1
p2
p3
(a) (b)
do
if
to
扩充二叉搜索树
q0
q1
p1
q2
p2
q3
p3
do
if
to
q0
q1
p1
q2
p2
q3
p3
(d)(c) do
if
to
q0
q1
p1
q2
p2 q3
p3
(e)
? 在扩充二叉搜索树中
? ○ 表示内部结点, 包含了关键码集合中
的某一个关键码；
? □ 表示外部结点, 代表各关键码间隔中
的不在关键码集合中的关键码 。
? 在每两个外部结点间必存在一个内部结点 。
? 设二叉树的 内部结点有 n 个, 外部结点有
n+1 个 。 如果定义每个结点的路径长度为
该结点的层次, 并用 I 表示所有 n 个内部
结点的路径长度之和, 用 E 表示 n+1 个外
部结点的路径长度之和, 可以用归纳法证
明, E = I+2n。
一棵扩充二叉搜索树的 搜索成功的平均搜
索长度 ASLsucc可以定义为 该树所有内部结点
上的权值 p[i]与搜索该结点时所需的 关键码
比较次数 c[i] (= l[i] + 1)乘积之和：
).][(*][ 1p
1
?? ?
?
i liAS L
n
i
s u c c
搜索不成功的平均搜索长度 ASLunsucc为树中
所有外部结点上权值 q[j]与到达外部结点所需
关键码比较次数 c'[j](= l'[j])乘积之和：
?
?
?
n
j
u n s u c c jljAS L
0
q ].[ *][
扩充二叉搜索树总的平均搜索长度为,
ASL = ASLsucc + ASLunsucc
所有内、外部结点上的权值关系为
? ?
? ?
??
n
i
n
j
ji
1 0
qp 1][][
(1) 相等搜索概率的情形
设树中所有内, 外部结点的搜索概率都相等：
p[i] = q[j] = 1/7,1? i ? 3,0 ? j ? 3
图 (a),ASLsucc = 1/7*3+1/7*2+1/7*1 = 6/7,
ASLunsucc = 1/7*3*2+1/7*2+1/7*1 = 9/7。
总平均搜索长度 ASL = 6/7 + 9/7 = 15/7。
图 (a),ASL = 15/7 图 (d),ASL = 15/7
图 (b),ASL = 13/7 图 (e),ASL = 15/7
图 (c),ASL = 15/7
图 (b)的情形所得的平均搜索长度最小。 一
般把平均搜索长度达到最小的扩充二叉搜索树
称作最优二叉搜索树。
在 相等搜索概率的情形 下，所有内部、外部
结点的搜索概率都相等，视它们的权值都为 1。
同时，第 k 层有 2k 个结点,k = 0,1,?。则有
n 个内部结点的扩充二叉搜索树的内部路径长
度 I 至少等于序列
0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,…
的 前 n 项 的和。
因此，最优二叉搜索树的搜索成功的平均搜
索长度和搜索不成功的平均搜索长度分别为,
? ?? ?.?
?
??
n
i
s u c c iA S L
1
2 1l o g
? ?,?
?
??
?
1n
ni
u n s u c c iAS L
2
1
2l o g
(2) 不相等搜索概率的情形
设树中所有内、外部结点的搜索概率互不
相等。
p[1] = 0.5,p[2] = 0.1,p[3] = 0.05
q[0] = 0.15,q[1] = 0.1,q[2] = 0.05,q[3] = 0.05
do
if
to
do
if
to
q0=0.15
q1=0.1
p1=0.5 q2=0.05
p2=0.1
q3=0.05p3=0.05
q0=0.15 q1=0.1 q2=0.05
q3=
0.05
p1=0.5
p2=0.1
p3=0.05
(a) (b)
图 (a),ASLsucc = 0.5*3+0.1*2+0.05*1 = 1.75，
ASLunsucc = 0.15*3+0.1*3+0.05*2+0.05*1= 0.9。
ASL = ASLsucc + ASLunsucc = 2.65。
do
if
to
q0=
0.15
q1=0.1
p1=0.5
q2=0.05
p2=0.1
q3=0.05
p3=0.05
do
if
to
q0=0.15
q1=0.1
p1=0.5
q2=0.05
p2=0.1
q3=0.05p3=0.05
(d)(c)
图 (c), ASLsucc = 0.5*1+0.1*2+0.05*3 = 0.85,
ASLunsucc = 0.15*1+0.1*2+0.05*3+0.05*3 = 0.75.
ASL = 0.85+0.75 = 1.6
图 (b), ASL = 1.9; 图 (d), ASL = 2.15;
do
if
to
q0=0.15
q1=0.1
p1=0.5
q2=0.05
p2=0.1 q3=0.05
p3=0.05
(e)
图 (e), ASLsucc = 0.5*1
+0.05*2+0.1*3 = 0.9;
ASLunsucc = 0.15*1+
0.1*3+0.05*3+0.05*2
= 0.55;
ASL = 0.9+0.7 = 1.6.
由此可知，图 (c)和图 (e)的情形下树的平均搜
索长度达到最小，因此，图 (c)和图 (e)的情形
是最优二叉搜索树。
AVL树 高度平衡的二叉搜索树
AVL树的定义
一棵 AVL树或者是空树，或者是具有下列
性质的二叉搜索树,它的左子树和右子树都
是 AVL树，且左子树和右子树的高度之差的
绝对值不超过 1。
高度不平衡 高度平衡A
B
C
A
B
C
D
ED E
结点的平衡因子 balance (balance factor)
? 每个结点附加一个数字,给出该结点 右子
树的高度减去左子树的高度 所得的 高度差,
这个数字即为结点的平衡因子 balance
? AVL树任一结点平衡因子只能取 -1,0,1
? 如果一个结点的平衡因子的绝对值大于 1,
则这棵二叉搜索树就失去了平衡,不再是
AVL树。
? 如果一棵二叉搜索树是高度平衡的,且有 n
个结点，其高度可保持在 O(log2n),平均搜
索长度也可保持在 O(log2n)。
AVL树的类定义
template <class Type> class AVLTree {
public:
struct AVLNode { //AVL树结点
Type data; int balance;
AVLNode<Type> * left,* right;
AVLNode ( ), left (NULL),right (NULL),
balance (0) { }
AVLNode ( Type d,AVLNode<Type> *
l = NULL,AVLNode<Type> *r = NULL)
,data (d),left (l),right (r),balance (0) { }
};
protected:
Type RefValue;
AVLNode *root;
int Insert (AVLNode<Type>*& Tree,Type x);
void RotateLeft (AVLNode<Type> * Tree,
AVLNode<Type> *& NewTree);
void RotateRight (AVLNode<Type> * Tree,
AVLNode<Type> *& NewTree);
void LeftBalance (AVLNode<Type> *& Tree);
void RightBalance (AVLNode<Type> *&Tree);
int Height (AVLNode<Type> * t) const;
public:
AVLTree ( ), root (NULL) { }
AVLNode (Type Ref ), RefValue (Ref),
root (NULL) { }
int Insert (Type x)
{ return Insert (root,x); }
friend istream& operator >> (istream& in,
AVLTree<Type>& Tree);
friend ostream& operator << (ostream& out,
const AVLTree<Type>& Tree);
int Height ( ) const;
}
平衡化旋转
? 如果在一棵平衡的二叉搜索树中插入一个
新结点，造成了不平衡。此时必须调整树
的结构，使之平衡化。
? 平衡化旋转有两类：
? 单旋转 (左旋和右旋 )
? 双旋转 (左平衡和右平衡 )
? 每插入一个新结点时,AVL 树中相关结点
的平衡状态会发生改变。因此,在插入一
个新结点后，需要 从插入位臵沿通向根的
路径回溯, 检查各结点的平衡因子 。
? 如果在某一结点发现高度不平衡，停止回
溯。从发生不平衡的结点起，沿刚才回溯
的路径取直接下两层的结点。
? 如果这三个结点处于一条直线上，则采用
单旋转进行平衡化 。 单旋转可按其方向分
为左单旋转和右单旋转,其中一个是另一
个的镜像，其方向与不平衡的形状相关。
? 如果这三个结点处于一条折线上，则采用
双旋转进行平衡化 。 双旋转分为先左后右
和先右后左两类。
右单旋转 左单旋转 左右双旋转 右左双旋转
左单旋转 (RotateLeft )
h
h h
A
C
E
B
D
h
h
h+
1
B
A
C
ED
h h
h+
1
C
EA
B D
+1 +2
0 +1 0
0
? 在子树 E中插入新结点, 该子树高度增 1导
致结点 A的平衡因子变成 +2,出现不平衡 。
? 沿插入路径检查三个结点 A,C和 E。 它们
处于方向为, \”的直线上, 需做左单旋转 。
? 以结点 C为旋转轴, 让结点 A反时针旋转 。
template <class Type>
void AVLTree<Type>,:
RotateLeft ( AVLNode<Type> * Tree,
AVLNode<Type> *& NewTree ) {
//左单旋转的算法
NewTree = Tree->right;
Tree->right = NewTree->left;
NewTree->left = Tree;
}
右单旋转 (RotateRight )
h
h h
A
C
E
B
D h
h+
1
B
A
C
ED
h h
h+
1
CE
A
B
D
? 在左子树 D上插入新结点使其高度增 1，导
致结点 A的平衡因子增到 -2，造成不平衡。
? 为使树恢复平衡，从 A沿插入路径连续取 3
个结点 A,B和 D，它们处于一条方向为,/”
的直线上，需要做右单旋转。
? 以结点 B为旋转轴，将结点 A顺时针旋转。
h
0
0
0
-1
-1
-2
template <class Type>
void AVLTree <Type>::
RotateRight ( AVLNode<Type> * Tree,
AVLNode<Type> *& NewTree) {
//右单旋转的算法
NewTree = Tree->left;
Tree->left = NewTree->right;
NewTree->right = Tree;
}
先左后右双旋转 (RotationLeftRight)
? 在子树 F或 G中插入新结点, 该子树的高度
增 1。 结点 A的平衡因子变为 -2,发生了不
平衡 。
? 从结点 A起沿插入路径选取 3个结点 A,B和
E,它们位于一条形如, ?” 的折线上, 因此
需要进行先左后右的双旋转 。
? 首先以结点 E为旋转轴, 将结点 B反时针旋
转, 以 E代替原来 B的位臵, 做左单旋转 。
? 再以结点 E为旋转轴, 将结点 A顺时针旋转,
做右单旋转 。 使之平衡化 。
插入
0
0
-1 -2
+1
-1
h
h
A
C
ED
0
h-1h-1
h
h
A
h-1h
B C
ED
B
左单
旋转
F G F G
0
0
-2 0
0 +1
h
h
A
CE
D
-2
h-1
h
hh
A
h-1h
B C
E
D
B
右单
旋转
F
G FG
先右后左双旋转 (RotationRightLeft)
? 右左双旋转是左右双旋转的镜像 。
? 在子树 F或 G中插入新结点, 该子树高度增 1。
结点 A的平衡因子变为 2,发生了不平衡 。
? 从 结点 A起沿插入路径选取 3个结点 A,C和
D,它们位于一条形如, ?” 的折线上, 需要
进行先右后左的双旋转 。
? 首先做右单旋转：以结点 D为旋转轴, 将结
点 C顺时针旋转, 以 D代替原来 C的位臵 。
? 再做左单旋转：以结点 D为旋转轴, 将结点
A反时针旋转, 恢复树的平衡 。
插入
右
单
旋
转
+1
0
0
0
-1
+1
0h
h
A
C
ED
h-1
B
F G
h-1
+2
0
0
0h
h
A
C
E
h
B
F G
h-1
D
00
+2 0
-1 0
h
h
A
C
E
+2
h-1
h
hh
A
h-1 h
B C
E
D
B
左单
旋转
F
G
FG
D
AVL树的插入
? 在向一棵本来是高度平衡的 AVL树中插入
一个新结点时, 如果树中某个结点的平衡
因子的绝对值 |balance| > 1,则出现了不平
衡, 需要做平衡化处理 。
? 在 AVL树上定义了重载操作,>>”和,<<”，
以及中序遍历的算法。利用这些操作可以
执行 AVL树的建立和结点数据的输出。
? 算法 从一棵空树开始,通过输入一系列对
象关键码,逐步建立 AVL树 。在插入新结
点时 使用平衡旋转方法进行平衡化处理 。
1616
例，输入关键码序列为 { 16,3,7,11,9,26,18,
14,15 },插入和调整过程如下。
0
3
16
3
-1
0
7
0
1
-2
左右双旋 7
3 16
0 0
0
7
3
11
0
-1
1
7
3 16
16
11
9
0
-1
-2
右单旋 3
7
169
0 0
0
1
3
7
11
26
9 16
11
0
1
1
22
18 18
0
3
16
3
-1
0
16
0
2 右左双旋
7
3 9
0
0
0
18
26
11
-1
7
3 26
16
11
9
-1
左单旋
9
7
16
14
0
0
1
7
11
26
269
1
1
11
15
18
2
3
18
16
-2
左右双旋
7
3
0
0
0
11
7
14
9
-1
16
15
0
1
11
26 26
141
-2
9
从空树开始的建树过程
AVL树的删除
(1) 如果 被删结点 x最多只有一个子女, 那么
问题比较简单,
? 将 结点 x从树中删去 。
? 因为结点 x最多有一个子女, 可以简单地
把 x的双亲结点中原来指向 x的指针改指
到这个子女结点 ；
? 如果结点 x没有子女, x双亲结点的相应
指针臵为 NULL。
? 将原来以结点 x为根的子树的高度减 1。
(2) 如果 被删结点 x有两个子女,
? 搜索 x 在 中序次序下的直接前驱 y (同样
可以找直接后继 )。
? 把 结点 y 的内容传送给 结点 x,现在问题
转移到删除 结点 y。 把 结点 y当作 被删结
点 x。
? 因为结点 y最多有一个子女, 我们可以简
单地用 (1)给出的方法进行删除 。
? 必须沿 x 通向根的路径反向追踪高度的变
化对路 径上各个结点的影响。
? 用一个布尔变量 shorter 来指明子树的高
度是否被缩短。在每个结点上要做的操作
取决于 shorter 的值和结点的 balance，有
时还要依赖子女的 balance 。
? 布尔变量 shorter 的值初始化为 True。然
后对于 从 x 的双亲到根的路径上的各个结
点 p，在 shorter 保持为 True 时执行下面
操作。如果 shorter 变成 False，算法终止。
? case 1, 当前结点 p 的 balance为 0。如果它
的左子树或右子树被缩短，则它的 balance
改为 1 或 -1，同时 shorter 臵为 False。
0
h hh-1
删除一个结点,
高度降低一层
不旋转
1
hh-1
p p
? case 2, 结点 p 的 balance不为 0，且较高的
子树被缩短，则 p 的 balance改为 0，同时
shorter 臵为 True。
-1
h+1 hh
删除一个结点,高度降低一层
不旋转
0
hh
p p
高度减 1
? case 3, 结点 p 的 balance不为 0，且较矮的
子树又被缩短，则在结点 p 发生不平衡。
需要进行平衡化旋转来恢复平衡。
? 令 p 的较高的子树的根为 q (该子树未被缩
短 ),根据 q 的 balance，有如下 3 种平衡化
操作。
? 在 case 3a,3b和 3c的情形中，旋转的方向取
决于是结点 p 的哪一棵子树被缩短。
? case 3a, 如果 q (较高的子树 ) 的 balance为
0,执行一个单旋转来恢复结点 p 的平衡，
臵 shorter为 False。
1
h
h
h-1
删除
结点
左单旋
p
h
0 q 1
hh-1
p
h
q-1
? case 3b, 如果 q 的 balance与 p 的 balance相
同，则执行一个单旋转来恢复平衡,结点 p
和 q 的 balance均改为 0,同时臵 shorter 为
True。
1
hh-1
删除结点
左单旋
p
h
1 q 0
h-1
p
h
q0
h-1 h-1
0
? case 3c, 如果 p 与 q 的 balance相反,则执行
一个双旋转来恢复平衡,先围绕 q 转再围绕
p 转。新根结点的 balance臵为 0，其它结点
的 balance相应处理,同时臵 shorter为 True。
1
hh-1
删除
结点
p
-1 q
h-1或
h-2
h-1或
h-2
h-1
r
h-1h-1h-1h-1
0 0p
q
r
右左双旋
高度减 1
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
0
0
0 0
0 0
0
-1
-1
-1-1
-1
-1
-1 1
1 1
11
树的初始状态
举例
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
0
0
0 0
0 0
0
-1
-1
-1-1
-1
-1
-1 1
1 1
11
删除结点 P
寻找结点 P在中序下的直接前驱 O,用 O顶
替 P,删除 O。
用 O取代 P
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
Q
R
S
T
0
0
0 0
0
0
-1
-1
-1-1
-1
-1
-1 1
1 1
11
删除结点 P 左单旋转
O与 R的平衡因子同号,以 R为旋转轴做左单
旋转,M的子树高度减 1。
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
Q
R
S
T
0
0
0 0
0 0
-1
-1
-1-1
-1
-1
-1 1
0
01
删除结点 P
M的子树高度减 1,M发生不平衡。 M与 E的
平衡因子反号,做左右双旋转。
0
向上继续调整
A
B
C
D
E
F
G
H
I
J
N
K
L
M
O
R
0 0
0
0
0 -1
0
0
-1
-1 -1
-1 01
00
删除结点 P
00
T
Q
0
S
AVL树的高度
? 设在新结点插入前 AVL树的高度为 h,结
点个数为 n,则插入一个新结点的时间是
O(h)。 对于 AVL树来说, h多大？
? 设 Nh 是高度为 h 的 AVL树的最小结点数 。
根的 一棵子树的高度为 h-1,另一棵子树
的高度为 h-2,这两棵子树也是高度平衡
的 。 因此有
? N-1 = 0 (空树 )
? N0 = 1 (仅有根结点 )
? Nh = Nh-1 + Nh-2 +1,h > 0
? 可以证明,对于 h ? 0,有 Nh = Fh+3 -1 成立。
? 有 n 个结点的 AVL树的高度不超过
1.44*log2(n+1)-1
? 在 AVL树删除一个结点并做平衡化旋转所
需时间为 O(log2n)。
? 二叉搜索树适合于组织在内存中的较小的
索引 (或目录 )。对于存放在外存中的较大的
文件系统，用二叉搜索树来组织索引不太
合适。
? 在文件检索系统中大量使用的是用 B树或
B+树做文件索引。
? 并查集
? 静态搜索表
? 二叉搜索树
? AVL树
集合基本概念
集合及其表示
? 集合是成员 (对象或元素 )的一个群集。
集合中的成员可以是原子 (单元素 )，也
可以是集合。
? 集合的成员必须互不相同。
? 在算法与数据结构中所遇到的集合，其
单元素通常是整数、字符、字符串或指
针，且同一集合中所有成员具有相同的
数据类型。
colour = { red,orange,yellow,green,
black,blue,purple,white }
name = {,An”,“Cao”,“Liu”,“Ma”,
“Peng”,“Wang”,“zhang” }
? 集合中的成员一般是无序的，但在表示
它时，常写在一个序列里。
? 常设定集合中的单元素具有线性有序关
系，此关系可记作,<”，表示“优先
于”。
? 整数、字符和字符串都有一个自然线性
顺序。指针也可依据其在序列中安排的
位臵给予一个线性顺序。
集合 (Set)的抽象数据类型
template <class Type> class Set {
Set (int MaxSetSize), MaxSize(MaxSetSize);
void MakeEmpty (Set& s);
int AddMember (Set& s,const Type x);
int DelMember (Set& s,const Type& x);
A?B 或 A+B A?B 或 A?B A-B
A A AB BB
void Assign (Set& s1,Set& s2);
void Union (Set& s1,Set& s2);
void Intersection (Set& s1,Set& s2);
void Difference (Set& s1,Set& s2);
int Contains (Set& s,const Type& x);
int Equal (Set& s1,Set& s2);
int SubSet (Set& s1,Set& s2);
}
用位向量实现集合抽象数据类型
? 当集合是全集合 { 0,1,2,…,n }的一个子
集，且 n是不大的整数时，可用位 (0,1)向量
来实现集合。
? 当全集合是由有限的可枚举的成员组成的
集合时，可建立全集合成员与整数 0,1,
2,… 的一一对应关系，用位向量来表示该
集合的子集。
集合的位向量 (bit Vector)类的定义
#include <assert.h>
const int DefaultSize = 100;
class Set {
private:
int * bitVector;
int MaxSize;
public:
Set ( int MaxSetSize = DefaultSize );
~Set ( ) { delete [ ] bitVector; }
void MakeEmpty ( ) {
for ( int i = 0; i < MaxSize; i++ )
bitVector[i] = 0;
}
int GetMember ( const int x ) {
return x >= 0 && x < MaxSize?
bitVector[x], -1; }
int AddMember ( const int x );
int DelMember ( const int x );
Set& operator = ( Set& right );
Set& operator + ( Set& right );
Set& operator * ( Set& right );
Set& operator - ( Set& right );
int Contains ( const int x );
int SubSet ( Set& right );
int operator == ( Set& right );
};
使用示例
Set s1,s2,s3,s4,s5; int index,equal;
for ( int k = 0; k < 10; k++ ) //集合赋值
{ s1.AddMember( k ); s2.AddMember( k +7 ); }
// s1, { 0,1,2,…,9 },s2, { 7,8,9,…,16 }
s3 = s1+s2; //求 s1与 s2的并 { 0,1,…,16 }
s4 = s1*s2; //求 s1与 s2的交 { 7,8,9 }
s5 = s1-s2; //求 s1与 s2的差 { 0,1,…,6 }
// s1, { 0,1,2,…,9 }
index = s1.SubSet ( s4 ); //s4在 s1中首次匹配
cout << index << endl; //位置, index = 7
// s1, { 0,1,2,3,4,5,6,7,8,9 }
// s4, { 7,8,9 }
equal = s1 == s2; //集合 s1与 s2比较相等
cout << equal << endl; //为 0,两集合不等
用位向量实现集合时部分操作的实现
Set,,Set (int MaxSetSize),
MaxSize (MaxSetSize) {
assert ( MaxSize > 0 );
bitVector = new int [MaxSize];
assert ( bitVector != 0 );
for ( int i = 0; i < MaxSize; i++ )
bitVector[i] = 0;
}
int Set,,Addmember ( const int x ) {
assert ( x >= 0 && x < MaxSize );
if ( ! bitVector[x] )
{ bitVector[x] = 1; return 1; }
return 0;
}
int Set,,DelMember ( const int x ) {
assert ( x >= 0 && x < MaxSize );
if ( bitVector[x] )
{ bitVector[x] = 0; return 1; }
return 0;
}
Set& Set,,operator = ( Set& right ) {
assert ( MaxSize == right.MaxSize );
for ( int i = 0; i < MaxSize; i++ )
bitVector[i] = right.bitVector[i];
return *this;
}
int Set,,Contains ( const int x ) {
assert ( x >= 0 && x < MaxSize );
return bitVector[x];
}
Set& Set,,operator + ( Set& right ) {
assert ( MaxSize == right.MaxSize );
Set temp ( MaxSize );
for ( int i = 0; i < MaxSize; i++ )
temp.bitVector[i] =
bitVector[i] || right.bitVector[i];
return temp;
}
this
right
temp
0 1 1 1 0 0 0 0 1 1 0
0 0 1 0 0 1 0 1 0 1 0
0 1 1 1 0 1 0 1 1 1 0
Set& Set,,operator * ( Set & right ) {
assert ( MaxSize == right.MaxSize );
Set temp ( MaxSize );
for ( int i = 0; i < MaxSize; i++)
temp.bitVector[i] =
bitVector[i] && right.bitVector[i];
return temp;
}
this
right
temp
0 1 1 1 0 0 0 0 1 1 0
0 0 1 0 0 1 0 1 0 1 0
0 0 1 0 0 0 0 0 0 1 0
Set& Set,,operator - ( Set & right ) {
assert ( MaxSize == right.MaxSize );
Set temp ( MaxSize );
for ( int i = 0; i < MaxSize; i++ )
temp,bitVector[i] =
bitVector[i] && !right.bitVector[i];
return temp;
}
this
right
temp
0 1 1 1 0 0 0 0 1 1 0
0 0 1 0 0 1 0 1 0 1 0
0 1 0 1 0 0 0 0 1 0 0
int Set,,operator == ( Set& right ) {
assert ( MaxSize == right.MaxSize );
for ( int i = 0; i < MaxSize; i++)
if ( bitVector[i] != right.bitVector[i] )
return 0;
return 1;
}
this
right
0 0 1 1 0 0 0 0 1 1 0
0 0 1 0 0 1 0 1 0 1 0
i
int Set,,SubSet (Set& right ) {
assert ( MaxSize == right.MaxSize );
for ( int i = 0; i < MaxSize; i++)
if (bitVector[i] && ! right.bitVector[i])
return 0;
return 1;
}
this
right
0 0 1 1 0 0 0 0 1 1 0
0 0 1 0 0 1 0 1 0 1 01 1 0 1 1 0 1 0 1 0 1
i
用有序链表实现集合的抽象数据类型
用带表头结点的有序链表表示集合
first
first 08 17 23 35 49 72
? 用有序链表来表示集合时，链表中的每个
结点表示集合的一个成员。
? 各结点所表示的成员 e0,e1,…,en 在链表中
按升序排列，即 e0 < e1 < … < en。
? 集合成员可以无限增加。因此，用有序链
表可以表示无穷全集合的子集。
template <class Type> class SetList;
template <class Type> class SetNode {
friend class SetList<Type>;
public:
SetNode (const Type& item ),
data (item),link (NULL);
private:
Type data;
SetNode<Type> * link;
};
集合的有序链表类的定义
template <class Type> class SetList {
private:
SetNode<Type> *first,*last;
//有序链表的表头指针,表尾指针
public:
SetList ( ) //构造函数
{ first = last = new SetNode<Type>(0); }
~SetList ( ) { MakeEmpty( ); delete first; }
void MakeEmpty ( ); //置空集合
int AddMember ( const Type& x );
int DelMember ( const Type& x );
SetList<Type> & operator = ( SetList<Type>&
right ); //将集合 right赋给集合 this
SetList<Type> & operator + ( SetList<Type>&
right ); //求集合 this与集合 right的并
SetList<Type> & operator * ( SetList<Type>&
right ); //求集合 this与集合 right的交
SetList<Type> & operator - ( SetList<Type>&
right ); //求集合 this与集合 right的差
int Contains ( const Type& x );
//判 x是否集合的成员
int operator == ( SetList<Type>& right );
//判集合 this与集合 right相等
Type& Min ( ); //返回集合中最小元素值
Type& Max ( ); //返回集合中最大元素值
}
集合的搜索、加入和删除操作
template <class Type> int SetList<Type>,:
Contains ( const Type& x ) {
//若 x是集合成员,则函数返回 1,否则返回 0
SetNode<Type> * temp = first->link;
while ( temp != NULL && temp->data < x )
temp = temp->link; //循链搜索
if ( temp != NULL && temp->data == x )
return 1; //找到,返回 1
else return 0; //未找到,返回 0
}
template <class Type> int SetList<Type>,:
AddMember ( const Type& x ) {
SetNode<Type> *p = first->link,*q = first;
while ( p != NULL && p->data < x )
{ q = p; p = p->link; } //循链扫描
if ( p != NULL && p->data == x ) return 0;
//集合中已有此元素
SetNode<Type> * s = new SetNode (x);
s->link = p; q->link = s; //链入
if ( p == NULL ) last = s;
//链到链尾时改链尾指针
return 1;
}
template <class Type> int SetList<Type>,:
DelMember ( const Type& x ) {
SetNode<Type> * p = first->link,* q = first;
while ( p != NULL && p->data < x )
{ q = p; p = p->link; } //循链扫描
if ( p != NULL && p->data == x ) { //找到
q->link = p->link; //重新链接
if ( p == last ) last = q;
//删去链尾结点时改链尾指针
delete p; return 1; //删除含 x结点
}
else return 0; //集合中无此元素
}
用有序链表表示集合时的几个重载函数
template <class Type>
SetList<Type>& SetList<Type>,,
operator = ( SetList<Type>& right ) {
//复制集合 right到 this
SetNode<Type> * pb = right.first->link; //源
SetNode<Type> * pa = first = //目标
new SetNode<Type>;
while ( pb != NULL ) { //逐个结点复制
pa->link = new SetNode<Type>(pb->data);
pa = pa->link; pb = pb->link;
}
pa->link = NULL; last = pa;
return *this; //目标链表收尾
}
//求集合 this与集合 right的并,结果通过临时
//集合 temp返回,this集合与 right集合不变。
template <class Type>
SetList<Type>& SetList<Type>,,
operator + ( SetList<Type>& right ) {
first
right.first 08 17 23 49
temp.first 23
17 35
pa
pbpc
08 17 23 35 49
SetNode<Type> *pb = right.first->link;
SetNode<Type> *pa = first->link;
SetList<Type> temp;
SetNode<Type> *pc = temp.first;
while ( pa != NULL && pb != NULL ) {
if ( pa->data == pb->data ) { //共有元素
pc->link=new SetNode<Type>(pa->data);
pa = pa->link; pb = pb->link;
} else if ( pa->data < pb->data ) {
pc->link=new SetNode<Type>(pa->data);
pa = pa->link;
} else { //pa->data > pb->data
pc->link=new SetNode<Type>(pb->data);
pb = pb->link;
}
pc = pc->link;
}
if ( pa != NULL ) pb = pa; //pb指未扫完集合
while ( pb != NULL ) { //向结果链逐个复制
pc->link = new SetNode<Type>(pb->data);
pc = pc->link; pb = pb->link;
}
pc->link = NULL; temp.last = pc; //链表收尾
return temp;
}
template <class Type> int SetList<Type>,,
operator == ( SetList<Type> & right ) {
SetNode<Type> * pb = right.first->link;
SetNode<Type> * pa = first->link;
while ( pa != NULL && pb != NULL )
if ( pa->data == pb->data ) //相等,继续
{ pa = pa->link; pb = pb->link; }
else return 0; //不等时中途退出,返回 0
if ( pa != NULL || pb != NULL ) return 0;
//链不等长时,返回 0
return 1;
}
并查集 (Union-Find Sets)
? 并查集支持以下三种操作：
? Union (Root1,Root2) //并操作
? Find (x) //搜索操作
? UFSets (s) //构造函数
? 对于并查集来说，每个集合用一棵树表示。
? 为此，采用 树的双亲表示 作为集合存储表示。
集合元素的编号从 0到 n-1。其中 n 是最大
元素个数。
? 在 双亲表示 中,第 i 个数组元素代表包含
集合元素 i 的树结点 。根结点的双亲为 -1，
表示集合中的元素个数。
? 在同一棵树上所有结点所代表的集合元素
在同一个子集合中。
? 为此，需要有两个映射：
? 集合元素到存放该元素名的树结点间的
对应；
? 集合名到表示该集合的树的根结点间的
对应。
? 设 S1= {0,6,7,8 },S2= { 1,4,9 },S3= { 2,3,
5 }
集合名 指针
0 S1
1 S2
2 S3
0 4 2
76 8 1 9 3 5
? 为简化讨论, 忽略实际的集合名, 仅用表
示集合的树的根来标识集合 。
? 初始时,用构造函数 UFSets(s) 构造一个森
林,每棵树只有一个结点,表示集合中各元
素自成一个子集合 。
? 用 Find(i) 寻找集合元素 i 的根 。 如果有两
个集合元素 i 和 j,Find(i) == Find(j),表明
这两个元素在同一个集合中,
? 如果两个集合元素 i 和 j 不在同一个集合
中,可用 Union(i,j) 将它们合并到一个集合
中 。
S1 ? S2的可能的表示方法
下标
parent
集合 S1,S2 和 S3 的双亲表示
-1 4 -1 2 -1 2 0 0 0 4
0 1 2 3 4 5 6 7 8 9
0
76 8 4
1 9
4
1 90
876
const int DefaultSize = 10;
class UFSets { //并查集类定义
private:
int *parent; //集合元素数组
int size; //集合元素的数目
public:
UFSets ( int s = DefaultSize ); //构造函数
~UFSets ( ) { delete [ ] parent; } //析构函数
const UFSets& operator = (UFSets& right);
//重载函数, 集合赋值
void Union ( int Root1,int Root2 );
//基本例程, 两个子集合合并
int Find ( int x );
//基本例程, 搜寻集合 x的根
void UnionByHeight ( int Root1,int Root2 );
//改进例程, 压缩高度的合并算法
};
UFSets,,UFSets ( int s ) { //构造函数
size = s; //集合元素个数
parent = new int [size]; //双亲指针数组
for ( int i = 0; i < size; i++ ) parent[i] = -1;
//每一个自成一个单元素集合
}
?并查集操作的算法
? 查找
-5 0 1 2 3
0 1 2 3 4
Find (4)
Find (3) = 3
Find (2) =2
Find (1) = 1
Find (0) = 0
= -5 < 0 结束
int UFSets,,Find ( int x ) {
if ( parent [x] < 0 ) return x;
else return Find ( parent [x] );
}
-5 0 1 2 3parent
Parent[4]
=3 Parent[3]
=2Parent[2]
=1
Parent[1]
=0
Parent[0]
=-5
0 1 2 3 4
void UFSets,,Union ( int Root1,int Root2 ) {
//求两个不相交集合 Root1与 Root2的并
parent[Root2] = Root1;
//将 Root2连接到 Root1下面
}
? Find和 Union操作性能不好。假设最初 n
个元素构成 n 棵树组成的森林,parent[i]
= -1。做处理 Union(n-2,n-1),…,Union(1,
2),Union(0,1)后，将产生退化的树。
? 合并 -1-1 -1 -1 -10 2 3 4
-3
-5
0
3
2
1
3
3
4 1
3 3
22
0
2
3
1
4
Union(0,1)
-2
3
-4
1
4
2
1
2
3
4
Union(1,2)
Union(2,3)
Union(3,4)
? 执行一次 Union操作所需时间是 O(1),n-1
次 Union操作所需时间是 O(n)。
? 若再执行 Find(0),Find(1),…,Find(n-1),若
被搜索的元素为 i，完成 Find(i) 操作需要时
间为 O(i),完成 n 次搜索需要的总时间将达
到
? 改进的方法
? 按树的结点个数合并
? 按树的高度合并
? 压缩元素的路径长度
?
?
?
n
i
ni
1
2OO )()(
? 按树结点个数合并
?结点个数多的树的根结点作根
-1-1 -1 -1 -1
0
1
2 3 4
-1 -1
0
-7
2
5 6
-5 -2
2 2
3 3
2 0
1
3
4
5
6
2
3 3 0
2 0
56
2
31
4
Union(2,0)
void UFSets,,
WeightedUnion ( int Root1,int Root2 ) {
//按 Union的加权规则改进的算法
int temp = parent[Root1] + parent[Root2];
if ( parent[Root2] < parent[Root1] ) {
parent[Root1] = Root2; //Root2中结点数多
parent[Root2] = temp; //Root1指向 Root2
}
else {
parent[Root2] = Root1; //Root1中结点数多
parent[Root1] = temp; //Root2指向 Root1
}
}
? 按树高度合并
? 高度高的树的根结点作根
-0-0 -0 -0 -0
0
1
2 3 4
-0 -0
0
-2
2
5 6
-2 -1
2 2
3 3
2 0
1
3
4
5
6
2
3 3 0
2 0
56
2
31
4
Union(2,0)
Union操作的折叠规则
? 为进一步改进树的性能, 可以使用如下折叠
规则来, 压缩路径, 。 即,如果 j 是从 i 到
根的路径上的一个结点, 且 parent[j] ?
root[j],则把 parent[j] 臵为 root[i]。
0 0
6 7 8 6 7 8
1 9 1
9
3 5
3
5
从 i = 5 压缩路径
int UFSets,,CollapsingFind ( int i ) {
//使用折叠规则的搜索算法
for ( int j = i; parent[j] >= 0; j = parent[j] );
//让 j 循双亲指针走到根
while ( i != j ) { //换 parent[i] 到 j
int temp = parent[i];
parent[i] = j; i = temp;
}
return j;
}
搜索 (Search)的概念
静态搜索表
? 所谓 搜索,就是 在数据集合中寻找满足某
种条件的数据对象 。
? 搜索的结果通常有两种可能：
? 搜索成功,即找到满足条件的数据对象
这时,作为结果,可报告该对象在结构中
的位臵,还可给出该对象中的具体信息。
? 搜索不成功,或搜索失败。作为结果,
应报告一些信息,如失败标志、位臵等。
? 通常称用于搜索的数据集合为 搜索结构,
它是由 同一数据类型的对象 (或记录 )组成。
? 在每个对象中有若干属性，其中有一个属
性，其值可唯一地标识这个对象。称为关
键码。 使用基于关键码的搜索，搜索结果
应是唯一的。 但在实际应用时，搜索条件
是多方面的，可以 使用基于属性的搜索方
法，但搜索结果可能不唯一。
? 实施搜索时有两种不同的环境。
? 静态环境,搜索结构在插入和删除等操
作的前后不发生改变。 ? 静态搜索表
? 动态环境,为保持较高的搜索效率,搜
索结构在执行插入和删除等操作的前后
将自动进行调整，结构可能发生变化。
? 动态搜索表
静态搜索表
template <class Type> class dataList;
template <class Type> class Node {
friend class dataList<Type>;
private:
Type key;
other;
public:
Node ( const Type& value ), key (value) { }
Type getKey ( ) const { return key; }
void setKey ( Type k ) { key = k; }
};
template <class Type> class dataList {
protected:
Node <Type> *Element; //数据存储数组
int ArraySize,CurrentSize;
//数组最大长度和当前长度
public:
dataList ( int sz = 10 ), ArraySize (sz)
{ Element = new Node <Type> [sz]; }
virtual ~dataList ( ) { delete [ ] Element; }
friend ostream& operator <<
(ostream& OutStream,
const dataList<Type>& OutList );
friend istream & operator >>
( istream& InStream,
dataList<Type>& InList );
};
template <class Type> class searchList,
public dataList<Type> {
//作为派生类的静态搜索表的类定义
public,
searchList ( int sz = 10 ),
dataList<Type> (sz) { }
virtual ~searchList ( ) { }
virtual int Search ( const Type & x ) const;
};
template <class Type> istream& operator >>
( istream& InStream,dataList<Type>& InList )
{
//从输入流对象 InStream输入数据到表 InList中
cout <<,输入数组当前大小,,;
Instream >> InList.CurrentSize;
cout <<,输入数组元素值, \n”;
for ( int i = 0; i < InList.CurrentSize; i++ ) {
cout <<,元素, << i <<,,,;
InStream >> InList.Element[i];
}
return InStream;
}
template <class Type> ostream& operator <<
( ostream& OutStream,const dataList<Type>
& OutList ) {
//将表 OutList内容输出到输出流对象 OutStream
OutStream <<,数组内容, \n”;
for ( int i = 0; i < OutList.CurrentSize; i++ )
OutStream << OutList.Element[i] << ? ?;
OutStream << endl;
OutStream <<,数组当前大小,, <<
OutList.CurrentSize << endl;
return OutStream;
}
? 衡量一个搜索算法的时间效率的标准是：
在搜索过程中关键码的 平均比较次数 或 平
均读写磁盘次数 (只适合于外部搜索 ),也称
为 平均搜索长度 ASL(Average Search
Length),通常它是 搜索结构中对象总数 n
或文件结构中物理块总数 n 的函数 。
? 在静态搜索表中,利用数组元素的下标作为
数据对象的存放地址 。 搜索算法 根据给定
值 x,在数组中进行搜索 。 直到 找到 x在数组
中的位臵或可确定在数组中 找不到 x为止 。
? 另外衡量一个搜索算法还要考虑算法所需
要的存储量和算法的复杂性等问题。
顺序搜索 (Sequential Search)
? 所谓顺序搜索,又称线性搜索,主要用于在
线性结构中进行搜索 。
? 设若表中有 CurrentSize 个对象, 则顺序
搜索从表的先端开始,顺序用各对象的关键
码与 给定值 x进行比较,直到找到与其值相
等的对象,则搜索成功 ; 给出该对象在表中
的位臵 。
? 若整个表都已检测完仍未找到关键码与 x相
等的对象,则搜索失败 。 给出失败信息 。
template <class Type>
int searchList<Type>,:
Search ( const Type& x ) const {
//顺序搜索关键码为 x的数据对象,第 0号位置
//作为控制搜索自动结束的, 监视哨, 使用
Element[0].key = x; int i = CurrentSize;
//将 x送 0号位置设置监视哨
while ( Element[i].key != x ) i-- ;
//从后向前顺序搜索
return i;
}
const int Size = 10;
main ( ) { //顺序搜索的主过程
searchList<float> List1 (Size); //定义搜索表
float Target; int Location;
cin >> List1; cout << List1; //输入 List1
cout <<,搜索浮点数,,; cin >> Target;
if ( ( Location = List1.search ( Target ) ) != 0 )
cout <<,找到位置在, << Location <<
endl; //搜索成功,输出找到的位置
else cout <<, 没有找到,\n”; //搜索失败
}
顺序搜索的平均搜索长度
??
?
?
?
?
???
1
0
1
0
n
i
i
n
i
iis u c c pcpA S L ) 1 (,
)( 1
1
???? ?
?
inpAS L
n
i
is u c c
设搜索 第 i 个 元素的概率为 pi,搜索到 第 i 个
元素所需 比较次数 为 ci,则搜索成功的平均
搜索长度,
在顺序搜索并设臵“监视哨”情形：
ci = n- i +1,i = n,n-1,?,1，因此
.)()(?
?
???????? n
i
s u c c
nnn
n
in
n
A S L
1 2
1
2
1111
在等概率情形,pi = 1/n,i = 1,2,?,n。
在搜索不成功情形,ASLunsucc = n+1.
template <class Type> int SearchList<Type>,:
Search ( const Type& x,int& loc ) const {
//顺序搜索的递归算法
if ( loc >= CurrentSize ) return -1;
else if ( Element[loc].getKey( ) == x )
return loc;
else return Search ( x,loc+1 );
}
基于有序顺序表的顺序搜索算法
template <class Type>
int searchList<Type>,:
Search ( const Type& x ) const {
//顺序搜索关键码为 x的数据对象
for ( int i = 0; i < CurrentSize; i++ )
if ( Element[i].key == x ) return i; //成功
else if ( Element[I].key > x ) break;
return -1;
//顺序搜索失败,返回失败信息
}
? 有序顺序表的顺序搜索
( 10,20,30,40,50,60 )
10
50
60
=
=
=
=
=
=
20
30
40
<
<
<
<
<
<
>
>
>
>
>
>
? ?
2
71
6
1 5
0
??? ?
?i
s u c c iA S L
? ?
7
27
61
7
1 5
0
??
?
?
?
?
?
???
?
?
?i
un s uc c
i
A S L
基于有序顺序表的折半搜索
? 设 n个对象 存放在一个有序顺序表中, 并
按其关键码从小到大排好了序 。
? 折半搜索时,先求位于搜索区间正中的对象
的下标 mid,用其关键码与 给定值 x比较,
? Element[mid].key == x,搜索成功 ；
? Element[mid].key > x,把搜索区间缩小
到表的 前半部分, 继续折半搜索 ；
? Element[mid].key < x,把搜索区间缩小
到表的 后半部分, 继续折半搜索 。
? 如果搜索区间已缩小到一个对象, 仍未找
到想要搜索的对象, 则搜索失败 。
搜索成功的例子
-1 0 1 3 4 6 8 10 126
0 1 2 3 4 5 6 7 8
搜索 low mid high6
6 8 10 12
5 6 7 8
low mid high
6 6
5
low mid high
6
搜索失败的例子
-1 0 1 3 4 6 8 10 125
0 1 2 3 4 5 6 7 8
搜索 low mid high5
6 8 10 12
5 6 7 8
low mid high
65
5
low mid high
5
template <class Type> class orderedList,
public dataList<Type> {
//有序表的类定义,继承了数据表
public:
orderedList (int sz = 10),
dataList<Type> (sz) { }
virtual ~orderedList ( ) { }
virtual int Search ( const Type& x ) const;
};
template <class Type>
int orderedList<Type>,,//折半搜索算法
BinarySearch ( const Type & x,const int low,
const int high ) const {
//折半搜索的递归算法
int mid = -1;
if ( low <= high ) {
mid = ( low + high ) / 2;
if ( Element[mid].key < x )
mid = BinarySearch ( x,mid +1,high );
else if ( Element[mid].key > x )
mid = BinarySearch ( x,low,mid -1 );
}
return mid;
}
template<class Type> int orderedList <Type>:,
BinarySearch ( const Type & x ) const {
//折半搜索的迭代算法
int high = CurrentSize-1,low = 0,mid;
while ( low <= high ) {
mid = ( low + high ) / 2;
if ( Element[mid].key < x )
low = mid + 1; //右缩搜索区间
else if ( Element[mid].key ) > x )
high = mid - 1; //左缩搜索区间
else return mid; //搜索成功
}
return -1; //搜索失败
}
? 搜索成功时检测指针停留在树中某个结点。
? 搜索不成功时检测指针停留在某个外结点
（失败结点）。
35
15 45
502510
20 30
搜索 22
搜索 45
? 有序顺序表的折半搜索的判定树
( 10,20,30,40,50,60 )
10 50
=
=
==
=
=
30
<
<
<
<
<
<
>
>
> >
> >
20 40 60
(2*1+3*6)/7
折半搜索性能分析
? 若设 n = 2h-1,则描述折半搜索的判定树是
高度为 h-1 的满二叉树 。
2h = n+1,h = log2(n+1)。
? 第 0层结点有 1个,搜索第 0层结点要比较 1次 ;
第 1层结点有 2个,搜索第 1层结点要比较 2
次 ; …,第 i (0 ? i ? h) 层结点有 2i 个,搜索第
i 层结点要比较 i+1次, … 。
? 假定每个结点的搜索概率相等，即 pi = 1/n，
则搜索成功的平均搜索长度为
)221)(23
2211
11
122
1
1
0
1
??
?
?
?
?
????????
???????? ??
hh
n
i
i
n
0i
iis u c c
hh
(
n
C
n
CpA S L
?
121)(
221)( 232211 1221
????
???????????? ??
h
hh
h
hh?
11)(log11)(log
1
)1)(1 ) l o g((
1
1)21)((
1
22
2
?????
?
?
????????
nn
n
n
nnn
n
h
n
A S L
h
s u c c
可以用归纳法证明
这样
定义
二叉搜索树或者是一棵空树，或者是具有
下列性质的二叉树：
?每个结点都有一个作为搜索依据的关键
码 (key)，所有结点的关键码互不相同。
?左子树 (如果存在 )上 所有结点的关键码
都小于根结点的关键码 。
?右子树 (如果存在 )上 所有结点的关键码
都大于根结点的关键码 。
?左子树和右子树也是二叉搜索树。
二叉搜索树 ( Binary Search Tree )
35
15 45
50402510
20 30
二叉搜索树例
? 结点左子树上
所有关键码小
于结点关键码
? 右子树上所有
关键码大于结
点关键码
? 注意：若从根结点到某个叶结点有一条路
径，路径左边的结点的关键码不一定小于
路径上的结点的关键码。
n 个结点的二叉搜索树的数目
【例】 3 个结点的二叉搜索树
5
1*2*3
4*5*6*
4
1C
13
1 3
3*2 ???
1
2
2
1
3
3 1 3
2
1
2
3
1
2
3
{123} {132} {213} {231} {312} {321}
二叉搜索树的类定义
#include <iostream.h>
template <class Type> class BST;
template <class Type> Class BstNode <Type>,
public BinTreeNode {
friend class BST <Type>;
如果对一棵二叉搜索树进行中序遍历，可
以按从小到大的顺序，将各结点关键码排列
起来，所以也称二叉搜索树为二叉排序树。
protected:
Type data;
BstNode<Type> *leftChild,*rightChild;
};
public:
BstNode ( ), leftChild (NULL),
rightChild (NULL) { } //构造函数
BstNode ( const Type d ), data (d),
leftChild (NULL),rightChild (NULL) { }
BstNode ( const Type d = 0,BstNode<Type> *
L = NULL,BstNode<Type> *R = NULL)
,data (d),leftChild (L),rightChild (R) { }
Type GetData ( ) { return data; }
~BstNode ( ) { } //析构函数
};
template <class Type> class BST
,public BinaryTree<Type> {
private:
BstNode<Type> *root; //根指针
Type RefValue; //数据输入停止的标志
void MakeEmpty ( BstNode<Type> *& ptr );
void Insert ( Type& x,
BstNode<Type> *& ptr ); //插入
void Remove ( Type& x,
BstNode<Type> *& ptr ); //删除
void PrintTree ( BstNode<Type> * ptr ) const;
BstNode<Type> *Copy
( const BstNode<Type> * ptr ); //复制
BstNode<Type> *Find ( Type& x,
BstNode<Type> * ptr ); //搜索
BstNode<Type> *Min ( BstNode<Type> *
ptr ) const; //求最小
BstNode<Type> *Max ( BstNode<Type> *
ptr ) const; //求最大
public:
BST ( ), root (NULL) { } //构造函数
BST ( Type value ), RefValue (value),
root (NULL) { } //构造函数
~BST ( ); //析构函数
const BST& operator = ( const BST& Value );
void MakeEmpty ( )
{ MakeEmpty ( root ); root = NULL; }
void PrintTree ( ) const { PrintTree ( root ); }
int Find ( const Type& x ) //搜索元素
{ return Find ( x,root ) != NULL; }
Type Min ( return Min ( root )->data );
Type Max ( return Max ( root )->data );
void Insert ( const Type& x )
{ Insert ( x,root ); } //插入新元素
void Remove (const Type& x )
{ Remove ( x,root ); } //删除含 x的结点
}
在二叉搜索树上进行搜索,是一个从根结
点开始，沿某一个分支逐层向下进行比较判
等的过程 。它可以是一个递归的过程。
二叉搜索树上的搜索
? 假设想要在二叉搜索树中搜索关键码为 x
的元素, 搜索过程从根结点开始 。
? 如果根指针为 NULL,则搜索不成功；否
则用给定值 x与根结点的关键码进行比较：
? 如果给定值等于根结点的关键码, 则搜
索成功 。
? 如果给定值小于根结点的关键码, 则继
续递归搜索根结点的左子树；
? 否则 。 递归搜索根结点的右子树 。
35
15 45
50402510
20 30
搜索 45
搜索成功
搜索 28
搜索失败
template <class Type>
BstNode<Type> * BST<Type>,,Find ( const
Type& x,BstNode<Type> * ptr ) const {
//二叉搜索树的递归的搜索算法
if ( ptr == NULL ) return NULL; //搜索失败
else if ( x < ptr->data ) //在左子树搜索
return Find ( x,ptr->leftChild );
else if ( x > ptr->data ) //在右子树搜索
return Find ( x,ptr->rightChild );
else return ptr; //相等,搜索成功
}
template <class Type>
BstNode <Type> * BST <Type>,,Find (const
Type& x,BstNode<Type> * ptr ) const {
//二叉搜索树的迭代的搜索算法
if ( ptr != NULL ) {
BstNode<Type> * temp = ptr; //从根搜索
while ( temp != NULL ) {
if ( temp->data == x ) return temp;
if ( temp->data < x )
temp = temp->rightChild; //右子树
else temp = temp->leftChild; //左子树
}
}
return NULL; //搜索失败
}
二叉搜索树的插入 35
15 45
50402510
20 30
28
每次结点的插入，都
要从根结点出发搜索插
入位臵，然后把新结点
作为叶结点插入。
插入新结点 28
? 为了向二叉搜索树中插入一个新元素, 必
须先检查这个 元素是否在树中已经存在 。
? 在插入之前, 先使用搜索算法在树中检查
要插入元素有还是没有 。
? 搜索成功, 树中已有这个元素,不再插入 。
? 搜索不成功, 树中原来没有关键码等于
给定值的结点, 把新元素加到搜索操作
停止的地方 。
递归的二叉搜索树插入算法
template <class Type> void BST<Type>::
Insert ( const Type& x,
BstNode<Type> * & ptr) {
if ( ptr == NULL ) { //空二叉树
ptr = new BstNode<Type> (x); //创建结点
if ( ptr == NULL )
{ cout <<,存储不足 " << endl; exit (1); }
}
else if ( x < ptr->data ) //在左子树插入
Insert ( x,ptr->leftChild );
else if ( x > ptr->data ) //在右子树插入
Insert ( x,ptr->rightChild );
}
输入数据，建立二叉搜索树的过程
输入数据 { 53,78,65,17,87,09,81,15 }
53 53
78
53
78
65
53
78
65
17
53
78
65 87
17
53
78
6509
17
87
53
78
65
81
17
8709
53
78
65
15
17
8709
81
template <class Type>
BST<Type>,,BST ( Type value ) {
//输入数据,建立二叉搜索树 。 RefValue 是输入
//结束标志。这个值应取不可能在输入序列中
//出现的值,例如输入序列的值都是正整数时,
//取 RefValue为 0或负数。
Type &x;
root = NULL; RefValue = value;
cin >> x;
while ( x != RefValue )
{ Insert ( x,root ); cin >> x; }
}
同样 3 个数据 { 1,2,3 }，输入顺序不同，
建立起来的二叉搜索树的形态也不同。这直
接影响到二叉搜索树的搜索性能。
如果输入序列选得不好，会建立起一棵单
支树，使得二叉搜索树的高度达到最大。
{2,1,3}
{1,2,3} {1,3,2} {2,3,1} {3,1,2} {3,2,1}
1
2
3
1
1 1
1
3
2 2
2
3
3
2
3
二叉搜索树的删除
? 在二叉搜索树中删除一个结点时, 必须将
因删除结点而断开的二叉链表重新链接起
来, 同时确保二叉搜索树的性质不会失去 。
? 为保证在删除后树的搜索性能不至于降低,
还 需要防止重新链接后树的高度增加 。
? 删除叶结点, 只需将其双亲结点指向它
的指针清零, 再释放它即可 。
? 被删结点缺右子树, 可以拿它的左子女
结点顶替它的位臵, 再释放它 。
? 被删结点缺左子树, 可以拿它的右子女
结点顶替它的位臵, 再释放它 。
? 被删结点左, 右子树都存在, 可以在它
的右子树中寻找中序下的第一个结点 (关
键码最小 ),用它的值填补到被删结点中,
再来处理这个结点的删除问题 。
53
78
65
17
8709
23
45
删除 45
缺右子树,用
左子女顶替
53
78
65
17
8709 23
88
53
78
88
17
9409 23
删除 78
缺左子树,用
右子女顶替
53
94
88
17
09 23
53
78
81
17
9409 45
删除 78
在右子树上找
中序下第一个
结点填补23
65
53
81
88
17
9409 45
23
65
二叉搜索树的删除算法
template <class Type> void BST <Type>,:
Remove (const Type& x,
BstNode<Type> * & ptr) {
BstNode<Type> * temp;
if ( ptr != NULL )
if ( x < ptr->data ) //在左子树中删除
Remove ( x,ptr->leftChild );
else if ( x > ptr->data ) //在右子树中删除
Remove ( x,ptr->rightChild );
else if ( ptr->leftChild != NULL &&
ptr->rightChild != NULL ) {
temp = ptr->rightChild;
while ( temp->leftChild != NULL )
temp = temp->leftChild;
//找 ptr右子树中序下第一个结点
ptr->data = temp->data; //填补上
Remove ( ptr->data,temp );
//在 temp为根的子树中删除该结点
}
else { // ptr结点只有一个或零个子女
temp = ptr;
if ( ptr->leftChild == NULL )
ptr = ptr->rightChild;
else if ( ptr->rightChild == NULL )
ptr = ptr->leftChild; //只有左子女
delete temp;
}
}
二叉搜索树性能分析
? 对于有 n 个关键码的集合，其关键码有 n!
种不同排列，可构成不同二叉搜索树有
(棵 )
? 用树的搜索效率来评价这些二叉搜索树。
C n nn 21 1?
? 例，已知关键码集合 { a1,a2,a3 } = { do,if,
to }，对应搜索概率 p1,p2,p3,在各搜索不
成功间隔内搜索概率分别为 q0,q1,q2,q3。
可能的二叉搜索树如下所示。
do
if
to
do
if
to
q0 q1
p1 q2
p2 q3
p3
q0 q1 q2 q3
p1
p2
p3
(a) (b)
do
if
to
扩充二叉搜索树
q0
q1
p1
q2
p2
q3
p3
do
if
to
q0
q1
p1
q2
p2
q3
p3
(d)(c) do
if
to
q0
q1
p1
q2
p2 q3
p3
(e)
? 在扩充二叉搜索树中
? ○ 表示内部结点, 包含了关键码集合中
的某一个关键码；
? □ 表示外部结点, 代表各关键码间隔中
的不在关键码集合中的关键码 。
? 在每两个外部结点间必存在一个内部结点 。
? 设二叉树的 内部结点有 n 个, 外部结点有
n+1 个 。 如果定义每个结点的路径长度为
该结点的层次, 并用 I 表示所有 n 个内部
结点的路径长度之和, 用 E 表示 n+1 个外
部结点的路径长度之和, 可以用归纳法证
明, E = I+2n。
一棵扩充二叉搜索树的 搜索成功的平均搜
索长度 ASLsucc可以定义为 该树所有内部结点
上的权值 p[i]与搜索该结点时所需的 关键码
比较次数 c[i] (= l[i] + 1)乘积之和：
).][(*][ 1p
1
?? ?
?
i liAS L
n
i
s u c c
搜索不成功的平均搜索长度 ASLunsucc为树中
所有外部结点上权值 q[j]与到达外部结点所需
关键码比较次数 c'[j](= l'[j])乘积之和：
?
?
?
n
j
u n s u c c jljAS L
0
q ].[ *][
扩充二叉搜索树总的平均搜索长度为,
ASL = ASLsucc + ASLunsucc
所有内、外部结点上的权值关系为
? ?
? ?
??
n
i
n
j
ji
1 0
qp 1][][
(1) 相等搜索概率的情形
设树中所有内, 外部结点的搜索概率都相等：
p[i] = q[j] = 1/7,1? i ? 3,0 ? j ? 3
图 (a),ASLsucc = 1/7*3+1/7*2+1/7*1 = 6/7,
ASLunsucc = 1/7*3*2+1/7*2+1/7*1 = 9/7。
总平均搜索长度 ASL = 6/7 + 9/7 = 15/7。
图 (a),ASL = 15/7 图 (d),ASL = 15/7
图 (b),ASL = 13/7 图 (e),ASL = 15/7
图 (c),ASL = 15/7
图 (b)的情形所得的平均搜索长度最小。 一
般把平均搜索长度达到最小的扩充二叉搜索树
称作最优二叉搜索树。
在 相等搜索概率的情形 下，所有内部、外部
结点的搜索概率都相等，视它们的权值都为 1。
同时，第 k 层有 2k 个结点,k = 0,1,?。则有
n 个内部结点的扩充二叉搜索树的内部路径长
度 I 至少等于序列
0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,…
的 前 n 项 的和。
因此，最优二叉搜索树的搜索成功的平均搜
索长度和搜索不成功的平均搜索长度分别为,
? ?? ?.?
?
??
n
i
s u c c iA S L
1
2 1l o g
? ?,?
?
??
?
1n
ni
u n s u c c iAS L
2
1
2l o g
(2) 不相等搜索概率的情形
设树中所有内、外部结点的搜索概率互不
相等。
p[1] = 0.5,p[2] = 0.1,p[3] = 0.05
q[0] = 0.15,q[1] = 0.1,q[2] = 0.05,q[3] = 0.05
do
if
to
do
if
to
q0=0.15
q1=0.1
p1=0.5 q2=0.05
p2=0.1
q3=0.05p3=0.05
q0=0.15 q1=0.1 q2=0.05
q3=
0.05
p1=0.5
p2=0.1
p3=0.05
(a) (b)
图 (a),ASLsucc = 0.5*3+0.1*2+0.05*1 = 1.75，
ASLunsucc = 0.15*3+0.1*3+0.05*2+0.05*1= 0.9。
ASL = ASLsucc + ASLunsucc = 2.65。
do
if
to
q0=
0.15
q1=0.1
p1=0.5
q2=0.05
p2=0.1
q3=0.05
p3=0.05
do
if
to
q0=0.15
q1=0.1
p1=0.5
q2=0.05
p2=0.1
q3=0.05p3=0.05
(d)(c)
图 (c), ASLsucc = 0.5*1+0.1*2+0.05*3 = 0.85,
ASLunsucc = 0.15*1+0.1*2+0.05*3+0.05*3 = 0.75.
ASL = 0.85+0.75 = 1.6
图 (b), ASL = 1.9; 图 (d), ASL = 2.15;
do
if
to
q0=0.15
q1=0.1
p1=0.5
q2=0.05
p2=0.1 q3=0.05
p3=0.05
(e)
图 (e), ASLsucc = 0.5*1
+0.05*2+0.1*3 = 0.9;
ASLunsucc = 0.15*1+
0.1*3+0.05*3+0.05*2
= 0.55;
ASL = 0.9+0.7 = 1.6.
由此可知，图 (c)和图 (e)的情形下树的平均搜
索长度达到最小，因此，图 (c)和图 (e)的情形
是最优二叉搜索树。
AVL树 高度平衡的二叉搜索树
AVL树的定义
一棵 AVL树或者是空树，或者是具有下列
性质的二叉搜索树,它的左子树和右子树都
是 AVL树，且左子树和右子树的高度之差的
绝对值不超过 1。
高度不平衡 高度平衡A
B
C
A
B
C
D
ED E
结点的平衡因子 balance (balance factor)
? 每个结点附加一个数字,给出该结点 右子
树的高度减去左子树的高度 所得的 高度差,
这个数字即为结点的平衡因子 balance
? AVL树任一结点平衡因子只能取 -1,0,1
? 如果一个结点的平衡因子的绝对值大于 1,
则这棵二叉搜索树就失去了平衡,不再是
AVL树。
? 如果一棵二叉搜索树是高度平衡的,且有 n
个结点，其高度可保持在 O(log2n),平均搜
索长度也可保持在 O(log2n)。
AVL树的类定义
template <class Type> class AVLTree {
public:
struct AVLNode { //AVL树结点
Type data; int balance;
AVLNode<Type> * left,* right;
AVLNode ( ), left (NULL),right (NULL),
balance (0) { }
AVLNode ( Type d,AVLNode<Type> *
l = NULL,AVLNode<Type> *r = NULL)
,data (d),left (l),right (r),balance (0) { }
};
protected:
Type RefValue;
AVLNode *root;
int Insert (AVLNode<Type>*& Tree,Type x);
void RotateLeft (AVLNode<Type> * Tree,
AVLNode<Type> *& NewTree);
void RotateRight (AVLNode<Type> * Tree,
AVLNode<Type> *& NewTree);
void LeftBalance (AVLNode<Type> *& Tree);
void RightBalance (AVLNode<Type> *&Tree);
int Height (AVLNode<Type> * t) const;
public:
AVLTree ( ), root (NULL) { }
AVLNode (Type Ref ), RefValue (Ref),
root (NULL) { }
int Insert (Type x)
{ return Insert (root,x); }
friend istream& operator >> (istream& in,
AVLTree<Type>& Tree);
friend ostream& operator << (ostream& out,
const AVLTree<Type>& Tree);
int Height ( ) const;
}
平衡化旋转
? 如果在一棵平衡的二叉搜索树中插入一个
新结点，造成了不平衡。此时必须调整树
的结构，使之平衡化。
? 平衡化旋转有两类：
? 单旋转 (左旋和右旋 )
? 双旋转 (左平衡和右平衡 )
? 每插入一个新结点时,AVL 树中相关结点
的平衡状态会发生改变。因此,在插入一
个新结点后，需要 从插入位臵沿通向根的
路径回溯, 检查各结点的平衡因子 。
? 如果在某一结点发现高度不平衡，停止回
溯。从发生不平衡的结点起，沿刚才回溯
的路径取直接下两层的结点。
? 如果这三个结点处于一条直线上，则采用
单旋转进行平衡化 。 单旋转可按其方向分
为左单旋转和右单旋转,其中一个是另一
个的镜像，其方向与不平衡的形状相关。
? 如果这三个结点处于一条折线上，则采用
双旋转进行平衡化 。 双旋转分为先左后右
和先右后左两类。
右单旋转 左单旋转 左右双旋转 右左双旋转
左单旋转 (RotateLeft )
h
h h
A
C
E
B
D
h
h
h+
1
B
A
C
ED
h h
h+
1
C
EA
B D
+1 +2
0 +1 0
0
? 在子树 E中插入新结点, 该子树高度增 1导
致结点 A的平衡因子变成 +2,出现不平衡 。
? 沿插入路径检查三个结点 A,C和 E。 它们
处于方向为, \”的直线上, 需做左单旋转 。
? 以结点 C为旋转轴, 让结点 A反时针旋转 。
template <class Type>
void AVLTree<Type>,:
RotateLeft ( AVLNode<Type> * Tree,
AVLNode<Type> *& NewTree ) {
//左单旋转的算法
NewTree = Tree->right;
Tree->right = NewTree->left;
NewTree->left = Tree;
}
右单旋转 (RotateRight )
h
h h
A
C
E
B
D h
h+
1
B
A
C
ED
h h
h+
1
CE
A
B
D
? 在左子树 D上插入新结点使其高度增 1，导
致结点 A的平衡因子增到 -2，造成不平衡。
? 为使树恢复平衡，从 A沿插入路径连续取 3
个结点 A,B和 D，它们处于一条方向为,/”
的直线上，需要做右单旋转。
? 以结点 B为旋转轴，将结点 A顺时针旋转。
h
0
0
0
-1
-1
-2
template <class Type>
void AVLTree <Type>::
RotateRight ( AVLNode<Type> * Tree,
AVLNode<Type> *& NewTree) {
//右单旋转的算法
NewTree = Tree->left;
Tree->left = NewTree->right;
NewTree->right = Tree;
}
先左后右双旋转 (RotationLeftRight)
? 在子树 F或 G中插入新结点, 该子树的高度
增 1。 结点 A的平衡因子变为 -2,发生了不
平衡 。
? 从结点 A起沿插入路径选取 3个结点 A,B和
E,它们位于一条形如, ?” 的折线上, 因此
需要进行先左后右的双旋转 。
? 首先以结点 E为旋转轴, 将结点 B反时针旋
转, 以 E代替原来 B的位臵, 做左单旋转 。
? 再以结点 E为旋转轴, 将结点 A顺时针旋转,
做右单旋转 。 使之平衡化 。
插入
0
0
-1 -2
+1
-1
h
h
A
C
ED
0
h-1h-1
h
h
A
h-1h
B C
ED
B
左单
旋转
F G F G
0
0
-2 0
0 +1
h
h
A
CE
D
-2
h-1
h
hh
A
h-1h
B C
E
D
B
右单
旋转
F
G FG
先右后左双旋转 (RotationRightLeft)
? 右左双旋转是左右双旋转的镜像 。
? 在子树 F或 G中插入新结点, 该子树高度增 1。
结点 A的平衡因子变为 2,发生了不平衡 。
? 从 结点 A起沿插入路径选取 3个结点 A,C和
D,它们位于一条形如, ?” 的折线上, 需要
进行先右后左的双旋转 。
? 首先做右单旋转：以结点 D为旋转轴, 将结
点 C顺时针旋转, 以 D代替原来 C的位臵 。
? 再做左单旋转：以结点 D为旋转轴, 将结点
A反时针旋转, 恢复树的平衡 。
插入
右
单
旋
转
+1
0
0
0
-1
+1
0h
h
A
C
ED
h-1
B
F G
h-1
+2
0
0
0h
h
A
C
E
h
B
F G
h-1
D
00
+2 0
-1 0
h
h
A
C
E
+2
h-1
h
hh
A
h-1 h
B C
E
D
B
左单
旋转
F
G
FG
D
AVL树的插入
? 在向一棵本来是高度平衡的 AVL树中插入
一个新结点时, 如果树中某个结点的平衡
因子的绝对值 |balance| > 1,则出现了不平
衡, 需要做平衡化处理 。
? 在 AVL树上定义了重载操作,>>”和,<<”，
以及中序遍历的算法。利用这些操作可以
执行 AVL树的建立和结点数据的输出。
? 算法 从一棵空树开始,通过输入一系列对
象关键码,逐步建立 AVL树 。在插入新结
点时 使用平衡旋转方法进行平衡化处理 。
1616
例，输入关键码序列为 { 16,3,7,11,9,26,18,
14,15 },插入和调整过程如下。
0
3
16
3
-1
0
7
0
1
-2
左右双旋 7
3 16
0 0
0
7
3
11
0
-1
1
7
3 16
16
11
9
0
-1
-2
右单旋 3
7
169
0 0
0
1
3
7
11
26
9 16
11
0
1
1
22
18 18
0
3
16
3
-1
0
16
0
2 右左双旋
7
3 9
0
0
0
18
26
11
-1
7
3 26
16
11
9
-1
左单旋
9
7
16
14
0
0
1
7
11
26
269
1
1
11
15
18
2
3
18
16
-2
左右双旋
7
3
0
0
0
11
7
14
9
-1
16
15
0
1
11
26 26
141
-2
9
从空树开始的建树过程
AVL树的删除
(1) 如果 被删结点 x最多只有一个子女, 那么
问题比较简单,
? 将 结点 x从树中删去 。
? 因为结点 x最多有一个子女, 可以简单地
把 x的双亲结点中原来指向 x的指针改指
到这个子女结点 ；
? 如果结点 x没有子女, x双亲结点的相应
指针臵为 NULL。
? 将原来以结点 x为根的子树的高度减 1。
(2) 如果 被删结点 x有两个子女,
? 搜索 x 在 中序次序下的直接前驱 y (同样
可以找直接后继 )。
? 把 结点 y 的内容传送给 结点 x,现在问题
转移到删除 结点 y。 把 结点 y当作 被删结
点 x。
? 因为结点 y最多有一个子女, 我们可以简
单地用 (1)给出的方法进行删除 。
? 必须沿 x 通向根的路径反向追踪高度的变
化对路 径上各个结点的影响。
? 用一个布尔变量 shorter 来指明子树的高
度是否被缩短。在每个结点上要做的操作
取决于 shorter 的值和结点的 balance，有
时还要依赖子女的 balance 。
? 布尔变量 shorter 的值初始化为 True。然
后对于 从 x 的双亲到根的路径上的各个结
点 p，在 shorter 保持为 True 时执行下面
操作。如果 shorter 变成 False，算法终止。
? case 1, 当前结点 p 的 balance为 0。如果它
的左子树或右子树被缩短，则它的 balance
改为 1 或 -1，同时 shorter 臵为 False。
0
h hh-1
删除一个结点,
高度降低一层
不旋转
1
hh-1
p p
? case 2, 结点 p 的 balance不为 0，且较高的
子树被缩短，则 p 的 balance改为 0，同时
shorter 臵为 True。
-1
h+1 hh
删除一个结点,高度降低一层
不旋转
0
hh
p p
高度减 1
? case 3, 结点 p 的 balance不为 0，且较矮的
子树又被缩短，则在结点 p 发生不平衡。
需要进行平衡化旋转来恢复平衡。
? 令 p 的较高的子树的根为 q (该子树未被缩
短 ),根据 q 的 balance，有如下 3 种平衡化
操作。
? 在 case 3a,3b和 3c的情形中，旋转的方向取
决于是结点 p 的哪一棵子树被缩短。
? case 3a, 如果 q (较高的子树 ) 的 balance为
0,执行一个单旋转来恢复结点 p 的平衡，
臵 shorter为 False。
1
h
h
h-1
删除
结点
左单旋
p
h
0 q 1
hh-1
p
h
q-1
? case 3b, 如果 q 的 balance与 p 的 balance相
同，则执行一个单旋转来恢复平衡,结点 p
和 q 的 balance均改为 0,同时臵 shorter 为
True。
1
hh-1
删除结点
左单旋
p
h
1 q 0
h-1
p
h
q0
h-1 h-1
0
? case 3c, 如果 p 与 q 的 balance相反,则执行
一个双旋转来恢复平衡,先围绕 q 转再围绕
p 转。新根结点的 balance臵为 0，其它结点
的 balance相应处理,同时臵 shorter为 True。
1
hh-1
删除
结点
p
-1 q
h-1或
h-2
h-1或
h-2
h-1
r
h-1h-1h-1h-1
0 0p
q
r
右左双旋
高度减 1
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
0
0
0 0
0 0
0
-1
-1
-1-1
-1
-1
-1 1
1 1
11
树的初始状态
举例
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
0
0
0 0
0 0
0
-1
-1
-1-1
-1
-1
-1 1
1 1
11
删除结点 P
寻找结点 P在中序下的直接前驱 O,用 O顶
替 P,删除 O。
用 O取代 P
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
Q
R
S
T
0
0
0 0
0
0
-1
-1
-1-1
-1
-1
-1 1
1 1
11
删除结点 P 左单旋转
O与 R的平衡因子同号,以 R为旋转轴做左单
旋转,M的子树高度减 1。
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
Q
R
S
T
0
0
0 0
0 0
-1
-1
-1-1
-1
-1
-1 1
0
01
删除结点 P
M的子树高度减 1,M发生不平衡。 M与 E的
平衡因子反号,做左右双旋转。
0
向上继续调整
A
B
C
D
E
F
G
H
I
J
N
K
L
M
O
R
0 0
0
0
0 -1
0
0
-1
-1 -1
-1 01
00
删除结点 P
00
T
Q
0
S
AVL树的高度
? 设在新结点插入前 AVL树的高度为 h,结
点个数为 n,则插入一个新结点的时间是
O(h)。 对于 AVL树来说, h多大？
? 设 Nh 是高度为 h 的 AVL树的最小结点数 。
根的 一棵子树的高度为 h-1,另一棵子树
的高度为 h-2,这两棵子树也是高度平衡
的 。 因此有
? N-1 = 0 (空树 )
? N0 = 1 (仅有根结点 )
? Nh = Nh-1 + Nh-2 +1,h > 0
? 可以证明,对于 h ? 0,有 Nh = Fh+3 -1 成立。
? 有 n 个结点的 AVL树的高度不超过
1.44*log2(n+1)-1
? 在 AVL树删除一个结点并做平衡化旋转所
需时间为 O(log2n)。
? 二叉搜索树适合于组织在内存中的较小的
索引 (或目录 )。对于存放在外存中的较大的
文件系统，用二叉搜索树来组织索引不太
合适。
? 在文件检索系统中大量使用的是用 B树或
B+树做文件索引。
