6静态查找技术62二叉排序树6平衡二叉排序树（AVL.ppt

静态查找技术
二叉排序树
平衡二叉排序树(AVL树)
* 红-黑树
* B-树和B+树
哈希(Hash)方法
第六章查找
静态查找技术
1、搜索:
在数据集合之中,搜索具有特定关键字的结点。
通常分为静态搜索表:集合中的结点总数是固定的或者很少发生变化。可以无序或组织成有序表。
动态搜索表:集合中的结点总数是经常在发生变化。组织成树形结构。
在内存中进行的搜索:重点减少比较、或查找的次数。评价标准:平均搜索长度。
在外存中进行的搜索:重点在于减少访问外存的次数。评价标准:读盘次数。
2、静态搜索结构:
………………
0
1
2
n-3
n-2
n-1
n
i
Vector
哨兵单元
采用静态向量(或数组),0号单元用作哨兵单元,1号单元到n号单元保存结点。
8
100
10
0
7
1
3
静态查找表(ADT)
template <class Type>
class Vector {
public:
Vector ( int size); // 构造函数,静态查找表的结点个数为 size.
~ Vector ( ) { delete [ ]Array; }
const Type & operator [ ] ( int index ) const; //具有越界检查的下标操作。
const Vector & operator = ( const Vector & R); //大小相等的向量的复制。
int Length( ) const { return ArraySize; }
void Double( ) { Resize( ArraySize * 2 );} // 在向量的单元用完时,容量加倍。
void Resize( int Newsize); // 修改向量的大小。
void Sentinel( const Type key ){ Array[0] = key; } //置0号单元的内容为待查 key。
protected:
Type * Array; // 保存结点的数组
int ArraySize; // 大小。
void GetArray( );
Vector(const Vector & R ); // 冻结使用构造函数复制另一向量的功能。
};
静态查找表(ADT)
部分操作的实现:
template <class Type>
const Type & Vector<Type> :: operator [ ] ( int index ) const {
Exception( index ≤0 || index > ArraySize, “Out of boundary!”);
return Array[index];
}
template <class Type>
const Vector<Type> & Vector<Type> :: operator = ( const Vector<Type> R ){
if ( this != &R ) {
Exception( ArraySize != , “Size is not same!”);
for(int k = 1; k <= ArraySize; k++ ) Array[k] = [k];
}
return *this;
}
静态查找表(ADT)
部分操作的实现:
template <class Type>
void Vector<Type> :: Resize( int NewSize ){
Type * oldArray = Array;
const int minsize = Min(ArraySize, NewSize); // 取二者小者。
ArraySize = NewSize;
GetArray( );
for(int k = 1; k <= minsize; k++ ) Array[k] = oldArray[k];
delete [ ]oldArray;
}
template <class Type>
void Vector<Type> :: GetArray( ){
Array = new Type[ArraySize+1];
}
template <class Type>
Vector<Type> :: Vector( int Size){
ArraySize = Size; GetArray( );
}
顺序查找
应用范围:顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。
………………
0
1
2