第 六 章 查找 6.1 静态查找技术 6.2 二叉排序树 6.3 平衡二叉排序树(AVL树) *6.4 红-黑树 *6.5 B-树和B+树

Presentation on theme: "第 六 章 查找 6.1 静态查找技术 6.2 二叉排序树 6.3 平衡二叉排序树(AVL树) *6.4 红-黑树 *6.5 B-树和B+树"— Presentation transcript:

1 第 六 章 查找 6.1 静态查找技术 6.2 二叉排序树 6.3 平衡二叉排序树(AVL树) *6.4 红-黑树 *6.5 B-树和B+树
6.1 静态查找技术 6.2 二叉排序树 6.3 平衡二叉排序树(AVL树) *6.4 红-黑树 *6.5 B-树和B+树 6.6 哈希(Hash)方法

2 静态查找技术 i Vector 8 100 10 ……………… 7 1 3 1 2 n-3 n-2 n-1 n 1、搜索：
在数据集合之中，搜索具有特定关键字的结点。 通常分为静态搜索表：集合中的结点总数是固定的或者很少发生变化。可以无序或组 织成有序表。 动态搜索表：集合中的结点总数是经常在发生变化。组织成树形结构。 在内存中进行的搜索：重点减少比较、或查找的次数。评价标准：平均搜索长度。 在外存中进行的搜索：重点在于减少访问外存的次数。评价标准：读盘次数。 2、静态搜索结构： 采用静态向量(或数组)，0号单元用作哨兵单元，1号单元到n号单元保存结点。 i 哨兵单元 Vector 8 100 10 ……………… 7 1 3 1 2 n-3 n-2 n-1 n

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 ); // 冻结使用构造函数复制另一向量的功能。 };

4 静态查找表(ADT) template <class Type>
部分操作的实现： template <class Type> const Type & Vector<Type> :: operator [ ] ( int index ) const { Exception( index ≤0 || index > ArraySize, “Out of boundary!”); return Array[index]; } const Vector<Type> & Vector<Type> :: operator = ( const Vector<Type> R ){ if ( this != &R ) { Exception( ArraySize != R.ArraySize, “Size is not same!”); for(int k = 1; k <= ArraySize; k++ ) Array[k] = R.Array[k]; return *this;

5 静态查找表(ADT) template <class Type>
部分操作的实现： 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; } void Vector<Type> :: GetArray( ){ Array = new Type[ArraySize+1]; Vector<Type> :: Vector( int Size){ ArraySize = Size; GetArray( );

6 顺序查找 e.g: 查找 x = 8 的结点所在的数组元素的下标。 i key 8 100 10 ……………… 7 1 3 1 2 n-3
应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。 template <class Type> int SeqSearch( const Vector<Type> & A, const Type key,int N ){ A[0] = key; // 将待查 key 置于哨兵单元，可省掉越界检查。 for ( int k = N; A[k] != key; --k ) return k; // 返回0，查找失败。否则，找到关键字为 key 的结点的下标 } 设置哨兵的好处： 在顺序表中总可以找到待查结点。否则，必须将 判断条件 i >= 0 加进 for 语句。 e.g: 查找 x = 8 的结点所在的数组元素的下标。 i key 8 100 10 ……………… 7 1 3 向量 Vector 1 2 n-3 n-2 n-1 n

7 顺序查找 e.g: 查找 x = 8 的结点所在的数组元素的下标。 i key 8 100 10 ……………… 7 1 3 1 2 n-3
应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。 template <class Type> int SeqSearch( const Vector<Type> & A, const Type key,int N ){ A[0] = key; // 将待查 key 置于哨兵单元，可省掉越界检查。 for ( int k = N; A[k] != key; --k ) return k; // 返回0，查找失败。否则，找到关键字为 key 的结点的下标 } 设置哨兵的好处： 在顺序表中总可以找到待查结点。否则，必须将 判断条件 i >= 0 加进 for 语句。 e.g: 查找 x = 8 的结点所在的数组元素的下标。 i key 8 100 10 ……………… 7 1 3 向量 Vector 1 2 n-3 n-2 n-1 n

8 顺序查找 e.g: 查找 x = 8 的结点所在的数组元素的下标。 i key 8 100 10 ……………… 7 1 3 1 2 n-3
应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。 template <class Type> int SeqSearch( const Vector<Type> & A, const Type key,int N ){ A[0] = key; // 将待查 key 置于哨兵单元，可省掉越界检查。 for ( int k = N; A[k] != key; --k ) return k; // 返回0，查找失败。否则，找到关键字为 key 的结点的下标 } 设置哨兵的好处： 在顺序表中总可以找到待查结点。否则，必须将 判断条件 i >= 0 加进 for 语句。 e.g: 查找 x = 8 的结点所在的数组元素的下标。 i key 8 100 10 ……………… 7 1 3 向量 Vector 1 2 n-3 n-2 n-1 n

9 顺序查找 e.g: 查找 x = 8 的结点所在的数组元素的下标。 i key 8 100 10 ……………… 7 1 3 1 2 n-3
应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。 template <class Type> int SeqSearch( const Vector<Type> & A, const Type key,int N ){ A[0] = key; // 将待查 key 置于哨兵单元，可省掉越界检查。 for ( int k = N; A[k] != key; --k ) return k; // 返回0，查找失败。否则，找到关键字为 key 的结点的下标 } 设置哨兵的好处： 在顺序表中总可以找到待查结点。否则，必须将 判断条件 i >= 0 加进 for 语句。 e.g: 查找 x = 8 的结点所在的数组元素的下标。 i key 8 100 10 ……………… 7 1 3 向量 Vector 1 2 n-3 n-2 n-1 n

10 顺序查找 e.g: 查找 x = 8 的结点所在的数组元素的下标。 i key 8 100 10 ……………… 7 1 3 1 2 n-3
应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。 template <class Type> int SeqSearch( const Vector<Type> & A, const Type key,int N ){ A[0] = key; // 将待查 key 置于哨兵单元，可省掉越界检查。 for ( int k = N; A[k] != key; --k ) return k; // 返回0，查找失败。否则，找到关键字为 key 的结点的下标 } 设置哨兵的好处： 在顺序表中总可以找到待查结点。否则，必须将 判断条件 i >= 0 加进 for 语句。 e.g: 查找 x = 8 的结点所在的数组元素的下标。 i key 8 100 10 ……………… 7 1 3 向量 Vector 1 2 n-3 n-2 n-1 n

11 顺序查找 e.g: 查找 x = 8 的结点所在的数组元素的下标。 i key 8 100 10 ……………… 7 1 3 1 2 n-3
应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。 template <class Type> int SeqSearch( const Vector<Type> & A, const Type key,int N ){ A[0] = key; // 将待查 key 置于哨兵单元，可省掉越界检查。 for ( int k = N; A[k] != key; --k ) return k; // 返回0，查找失败。否则，找到关键字为 key 的结点的下标 } 设置哨兵的好处： 在顺序表中总可以找到待查结点。否则，必须将 判断条件 i >= 0 加进 for 语句。 e.g: 查找 x = 8 的结点所在的数组元素的下标。 i key 8 100 10 ……………… 7 1 3 向量 Vector 1 2 n-3 n-2 n-1 n

12 顺序查找 e.g: 查找 x = 8 的结点所在的数组元素的下标。 i key 8 100 10 ……………… 7 1 3 1 2 n-3
应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。 template <class Type> int SeqSearch( const Vector<Type> & A, const Type key,int N ){ A[0] = key; // 将待查 key 置于哨兵单元，可省掉越界检查。 for ( int k = N; A[k] != key; --k ) return k; // 返回0，查找失败。否则，找到关键字为 key 的结点的下标 } 设置哨兵的好处： 在顺序表中总可以找到待查结点。否则，必须将 判断条件 i >= 0 加进 for 语句。 e.g: 查找 x = 8 的结点所在的数组元素的下标。 i key 8 100 10 ……………… 7 1 3 向量 Vector 1 2 n-3 n-2 n-1 n

13 顺序查找 e.g: 查找 x = 7 的结点所在的数组元素的下标。 i key 7 100 10 ……………… 7 1 3 1 2 n-3
应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。 template <class Type> int SeqSearch( const Vector<Type> & A, const Type key,int N ){ A[0] = key; // 将待查 key 置于哨兵单元，可省掉越界检查。 for ( int k = N; A[k] != key; --k ) return k; // 返回0，查找失败。否则，找到关键字为 key 的结点的下标 } 设置哨兵的好处： 在顺序表中总可以找到待查结点。否则，必须将 判断条件 i >= 0 加进 for 语句。 e.g: 查找 x = 7 的结点所在的数组元素的下标。 i key 7 100 10 ……………… 7 1 3 向量 Vector 1 2 n-3 n-2 n-1 n

14 顺序查找 e.g: 查找 x = 7 的结点所在的数组元素的下标。 i key 7 100 10 ……………… 7 1 3 1 2 n-3
应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。 template <class Type> int SeqSearch( const Vector<Type> & A, const Type key,int N ){ A[0] = key; // 将待查 key 置于哨兵单元，可省掉越界检查。 for ( int k = N; A[k] != key; --k ) return k; // 返回0，查找失败。否则，找到关键字为 key 的结点的下标 } 设置哨兵的好处： 在顺序表中总可以找到待查结点。否则，必须将 判断条件 i >= 0 加进 for 语句。 e.g: 查找 x = 7 的结点所在的数组元素的下标。 i key 7 100 10 ……………… 7 1 3 向量 Vector 1 2 n-3 n-2 n-1 n

15 顺序查找 e.g: 查找 x = 7 的结点所在的数组元素的下标。 i key 7 100 10 ……………… 7 1 3 1 2 n-3
应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。 template <class Type> int SeqSearch( const Vector<Type> & A, const Type key,int N ){ A[0] = key; // 将待查 key 置于哨兵单元，可省掉越界检查。 for ( int k = N; A[k] != key; --k ) return k; // 返回0，查找失败。否则，找到关键字为 key 的结点的下标 } 设置哨兵的好处： 在顺序表中总可以找到待查结点。否则，必须将 判断条件 i >= 0 加进 for 语句。 e.g: 查找 x = 7 的结点所在的数组元素的下标。 i key 7 100 10 ……………… 7 1 3 向量 Vector 1 2 n-3 n-2 n-1 n

16 顺序查找的性能 n 设 n 为结点的总数。 1 平均查找长度AVL（Average Search Length ）
成功查找情况下：设每个结点的查找概率相等 1 ASL＝ ∑(( n-i+1) ) i=n ＝ （n+1）/ 2 1 n

17 顺序查找的性能 一般查找情况下（包括成功、不成功两种情况）：设成功与不成功两种情况 可能性相等，每个结点的查找概率也相等。 1 ASL＝∑(( n-i+1) ) +∑((n+1) ) ＝ 3(n+1)/4 1 1 1 2n 2(n+1) i=n i=n+1 1 3 8 10 100 100 10 8 1 3 1 2 3 4 5 6 共有n+1=7种不成功的查找情况

18 折半查找（二分查找） e.g: 查找 key = 9 的结点所在的数组元素的下标地址。 key 4 8 9 10 11 13 19 1 2
应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 e.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 mid=4 但 key=9 < 10, 向左 key 4 8 9 10 11 13 19 1 2 3 4 5 6 7 high=7 low=1

19 折半查找 e.g: 查找 key = 9 的结点所在的数组元素的下标地址。 key 4 8 9 10 11 13 19 1 2 3 4 5
应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 e.g: 查找 key = 9 的结点所在的数组元素的下标地址。 查找成功的情况：数组 Vector 如下图所示有序 数组 Vector ：递增序 Vector[i]. Key <= Vector[I+1]. Key; i= 1,2,……n 查找范围 ：low（低下标）= 1; high（高下标）= 3 mid=4 key 4 8 9 10 11 13 19 1 2 3 4 5 6 7 high=3 (mid -1) low=1

20 折半查找 e.g: 查找 key = 9 的结点所在的数组元素的下标地址。 key 4 8 9 10 11 13 19 1 2 3 4 5
应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 e.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 mid=2 key 4 8 9 10 11 13 19 1 2 3 4 5 6 7 high=3 (mid -1) low=1

21 折半查找 e.g: 查找 key = 9 的结点所在的数组元素的下标地址。 key 4 8 9 10 11 13 19 1 2 3 4 5
应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 e.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 mid=2;但 key=9 > 8, 向右 key 4 8 9 10 11 13 19 1 2 3 4 5 6 7 high=3 (mid -1) low=1

22 折半查找 e.g: 查找 key = 9 的结点所在的数组元素的下标地址。 key 4 8 9 10 11 13 19 1 2 3 4 5
应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 e.g: 查找 key = 9 的结点所在的数组元素的下标地址。 查找成功的情况：数组 Vector 如下图所示有序 数组 Vector ：递增序 Vector[i]. Key <= Vector[I+1]. Key; i= 1,2,……n 查找范围 ：low（低下标）= 3; high（高下标）= 3 mid=2 key 4 8 9 10 11 13 19 1 2 3 4 5 6 7 high=3 (mid -1) low=3 (mid +1)

23 折半查找 e.g: 查找 key = 9 的结点所在的数组元素的下标地址。 key 4 8 9 10 11 13 19 1 2 3 4 5
应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 e.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 mid=3 key 4 8 9 10 11 13 19 1 2 3 4 5 6 7 high=3 low=3

24 折半查找 e.g: 查找 key = 9 的结点所在的数组元素的下标地址。 key 4 8 9 10 11 13 19 1 2 3 4 5
应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 e.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 mid=3; key=9 且中点值也为 9 ，找到 key 4 8 9 10 11 13 19 1 2 3 4 5 6 7 high=3 low=3

25 折半查找 e.g: 查找 key = 5 的结点所在的数组元素的下标地址。 key 4 8 9 10 11 13 19 1 2 3 4 5
查找不成功的情况：数组 Vector 如下图所示有序 数组 Vector ：递增序 Vector[i]. Key <= Vector[I+1]. Key; i= 1,2,……n 查找范围 ：low（低下标）= 1; high（高下标）= 7 （初始时为最大下标 n ）; 比较对象：中点元素，其下标地址为 mid = （low+high）/ 2 mid=4 但 key=5 < 10, 向左 key 4 8 9 10 11 13 19 1 2 3 4 5 6 7 high=7 low=1

26 折半查找 e.g: 查找 key = 5 的结点所在的数组元素的下标地址。 key 4 8 9 10 11 13 19 1 2 3 4 5
查找不成功的情况：数组 Vector 如下图所示有序 数组 Vector ：递增序 Vector[i]. Key <= Vector[I+1]. Key; i= 1,2,……n 查找范围 ：low（低下标）= 1; high（高下标）= 3 ; mid=4 key 4 8 9 10 11 13 19 1 2 3 4 5 6 7 low=1 high=3（mid-1）

27 折半查找 e.g: 查找 key = 5 的结点所在的数组元素的下标地址。 key 4 8 9 10 11 13 19 1 2 3 4 5
查找不成功的情况：数组 Vector 如下图所示有序 数组 Vector ：递增序 Vector[i]. Key <= Vector[I+1]. Key; i= 1,2,……n 查找范围 ：low（低下标）= 1; high（高下标）= 3 ; 比较对象：中点元素，其下标地址为 mid = （low+high）/ 2 =2 mid=2 key 4 8 9 10 11 13 19 1 2 3 4 5 6 7 low=1 high=3（mid-1）

28 折半查找 e.g: 查找 key = 5 的结点所在的数组元素的下标地址。 key 4 8 9 10 11 13 19 1 2 3 4 5
查找不成功的情况：数组 Vector 如下图所示有序 数组 Vector ：递增序 Vector[i]. Key <= Vector[I+1]. Key; i= 1,2,……n 查找范围 ：low（低下标）= 1; high（高下标）= 3 ; 比较对象：中点元素，其下标地址为 mid = （low+high）/ 2 =2 mid=2 ; 但 key=5 < 8, 向左 key 4 8 9 10 11 13 19 1 2 3 4 5 6 7 low=1 high=3（mid-1）

29 折半查找 e.g: 查找 key = 5 的结点所在的数组元素的下标地址。 key 4 8 9 10 11 13 19 1 2 3 4 5
查找不成功的情况：数组 Vector 如下图所示有序 数组 Vector ：递增序 Vector[i]. Key <= Vector[I+1]. Key; i= 1,2,……n 查找范围 ：low（低下标）= 1; high（高下标）= 1 mid=2 key 4 8 9 10 11 13 19 1 2 3 4 5 6 7 low=1 high=1（mid-1）

30 折半查找 e.g: 查找 key = 5 的结点所在的数组元素的下标地址。 key 4 8 9 10 11 13 19 1 2 3 4 5
查找不成功的情况：数组 Vector 如下图所示有序 数组 Vector ：递增序 Vector[i]. Key <= Vector[I+1]. Key; i= 1,2,……n 查找范围 ：low（低下标）= 1; high（高下标）= 1 比较对象：中点元素，其下标地址为 mid = （low+high）/ 2 = 1 mid=1 key 4 8 9 10 11 13 19 1 2 3 4 5 6 7 low=1 high=1

31 折半查找 e.g: 查找 key = 5 的结点所在的数组元素的下标地址。 key 4 8 9 10 11 13 19 1 2 3 4 5
查找不成功的情况：数组 Vector 如下图所示有序 数组 Vector ：递增序 Vector[i]. Key <= Vector[I+1]. Key; i= 1,2,……n 查找范围 ：low（低下标）= 1; high（高下标）= 1 比较对象：中点元素，其下标地址为 mid = （low+high）/ 2 = 1 mid=1 ; 但 key=5 > 4, 向右 key 4 8 9 10 11 13 19 1 2 3 4 5 6 7 low=1 high=1

32 折半查找 e.g: 查找 key = 5 的结点所在的数组元素的下标地址。 key 4 8 9 10 11 13 19 1 2 3 4 5
查找不成功的情况：数组 Vector 如下图所示有序 数组 Vector ：递增序 Vector[i]. Key <= Vector[I+1]. Key; i= 1,2,……n 查找范围 ：low（低下标）= 1; high（高下标）= 1 比较对象：中点元素，其下标地址为 mid = （low+high）/ 2 = 1 失败条件：low > high; 处于间隙中的键值导致这种情况！ mid=1 ; 但 key=5 > 4, 向右 key 4 8 9 10 11 13 19 1 2 3 4 5 6 7 low=2 high=1

33 折半查找 template <class Type>
int BinarySearch( const Vector<Type> & A, const Type key,int N ){ int low = 1, // 所查找的那一段的下界结点的下标。 high = N, // 所查找的那一段的上界结点的下标。 mid; // 所查找的那一段的中间结点的下标。 while( low <= high ) { mid = (low + high ) /2; if ( A[mid] = = key) return mid; else if (key < A[mid]) high = mid –1; else low = mid +1; } return 0; } // 返回0，查找失败.。否则，找到值为 key 的结点的索引或下标。

34 折半查找的性能 如果 n 是偶数，中点元素的左段有 n/2-1 个元素；右段有 n/2 个元素
最坏情况分析：设 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）= S（ n/2 ） = S（ n/22 ） = S（ n/23 ） = ……… S（ n/2k ） 注意：n/2 = n/2 总共 K 个 1 当 1 <= n/2k< 2 时；则 n/2k = 1 此时： 2k <= n < 2k 即 k <= log2n < k+1 注意：k 不可为小数，它是正整数。 ∴ k = log2n 故： S（n）= log2n

35 折半查找的性能 1 2 mid= 4 4 8 9 10 11 13 19 3 5 6 7 high=7 low=1 1 2 mid= 4 4 8 9 10 11 13 19 3 5 6 7 low=1 20 high=8

36 折半查找的性能 ? 最坏情况分析： 定理：在最坏情况下，二分查找法的查找有序表的最大的比较次数为
1+ log2n ，大体上和 log2n 成正比。 也可用判定树的方法进行推导。 如： ? key = k4 4 < > 1 2 3 4 5 6 7 8 6 2 4 8 9 10 11 13 19 29 < > < 当寻找 key = 8 及小于、大 于 8 的键值的相应结点时， 查找次数最大。达到了判定 树的深度或高度。 1 3 5 7 < > < > < > < > 1 2 3 4 5 6 8 < > 注意：当判定树为 n = 2t -1 （ t=1,2,3 …… ）时，为满二叉树。 否则，除最下一层外，余为满二叉树。 7 8

37 折半查找的性能 平均情况分析（在成功查找的情况下）：
设每个 结点的查找概率相同都为 1/n。为了简单起见，设结点个数为 n = 2t -1 （t = 1,2,3 …… ）。 ∴ 经过 1 次比较确定的结点个数为 1 = 20 个 ，红色标识的结点。 经过 2 次比较确定的结点个数为 2 = 21 个 ，绿色标识的结点。 经过 3 次比较确定的结点个数为 4 = 22 个 ，蓝色标识的结点。 . 经过 t 次比较确定的结点个数为 t-1 个 ，黑色标识的结点。 注意：∵ … + 2t-1 = 2t -1 ∴ 最多经过 t 次比较可以找到有序表中的任何一个结点 e.g: 当 t = 4 时的例子：最多经过 t=4 次比较找到任何一个结点 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4 8 9 10 11 13 19 29 32 47 65 77 81 93 99

38 折半查找的性能 平均情况分析（在成功查找的情况下）：
ASL = ( 20× ×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 结论：在成功查找的情况下，平均查找的代价约为 ASL = log2(n + 1) 或者简单地记为：ASL = log2n - 1

39 折半查找的性能 平均情况分析（考虑成功、非成功查找两种的情况下）:为了简单起见，设结点个数为 n = 2t -1 （t = 1,2,3 …… ）。 这样，成功查找的情况共有 n 种情况，非成功查找的情况共有 n + 1 情况。 设每种情况出现的概率相同，即都为 1/(2n+1) 。 t ASL = ( ∑ (i × 2i-1 )＋ t × ( n + 1 )) / (2n+1) i=1 = log2n + 1/2 1 6 7 3 5 2 4 < > e.g: 当 t = 3 时的例子： 成功：最多经过 t=3 次比较 失败：都必须经过 t = 3 次比较 4 8 9 10 11 13 19 1 2 3 5 6 7

40 差值查找 1、除中点下标的选择和二分查找不同外，其余类似。用于关键字值 均匀的情况，平均特性更好。 2、实现
1、除中点下标的选择和二分查找不同外，其余类似。用于关键字值 均匀的情况，平均特性更好。 2、实现 设 mid 为中点的下标。low 为具有最小关键字值结点的下标， high 为具有最大关键字值结点的下标。 (x-Element[low].key) mid = low + (high-low-1)× (Eelement[high].key-Element[low].key）

41 Fibonacci查找 ？ ? ? 1、Fibonacci 数 2、实现 ＝ 3、注意： 定义： 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 的结点 首先比较 key ST[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 数

42 Fibonacci查找 4、e.g: n = F7- 1 = 13 - 1 = 12个结点的查找过程
如：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, 4、e.g: n = F7- 1 = = 12个结点的查找过程 Fu－1 = 8 Fu－3 = 3 Fu－4 = 2 Fu－5 = 1 注意：Fu－2 = 5 ST[Fu－1].key 8 差为 Fu－3 = 3 > < 11 5 > 差为 Fu－5 = 1 差为 Fu－4 = 2 < > < 3 7 10 12 注意：本示意图从1开始编号，书上是从0开始进行编号。 < > < < 2 4 6 9 共 Fu－2 －1 ＝5－1＝4个结点 < 共 Fu－1 －1 ＝8－1＝7个结点 1 5、优点：只用 ＋、－法，不用除法。平均查找速度更快。O（log2n）级。 缺点：最坏情况下比二分查找法差。必须先给出 Fibonacci 数。

43 二叉排序树 特点：用于频繁进行插入、删除、查找的所谓动态查找表。
二叉排序树(二叉查找树)：空或有一个根，根的左子树若非空，则左子树上的所有结点的关键 字值均小于根结点的值。根的右子树若非空，则右子树上的所有结点的关键字值 均大于根结点的值。根结点的左右子树同样是二叉排序树。 e、g：二叉排序树(二叉查找树)，确定结点的大小，可根据结点类型进行定义。 L 122 N 250 C 99 P 300 M 200 E 110 Y 105 230 216

44 二叉排序树(ADT) template <class Type> class BST { // 二叉排序树的 ADT
public: BST ( ) { } // 二叉排序树的构造函数。 ~BST ( ) { } // 二叉排序树的析构函数。 virtual int Insert( const Type & x) = 0; // 插入 x。 virtual int Remove( const Type & x ) = 0; // 删除 x。 virtual const Type & Find(const Type & x) = 0;// 查找值为 x 的结点。 virtual int IsFound( const Type & x )= 0;// 若 x 找到，则返回 1。 virtual const Type & FindMin( ) = 0; // 返回最小值。 virtual const Type & FindMax( ) = 0; //返回最大值。 virtual int IsEmpty( ) const = 0;// 二叉排序树为空，返回 1，否则为0。 virtual int IsFull( )const = 0;// 二叉排序树为满，返回 1，否则为0。 virtual void MakeEmpty( ) = 0; //清除二叉排序树中的所有结点。 };

45 二叉排序树的结点类 二叉排序树中的结点类的实现，为了表示简单，没有采用继承的方式，采用结构。 二叉排序树BST的结点表示。
template <class Type> struct BSTNode { // 二叉排序树的结点的表示。 Type data; // 结点的数据场。 BSTNode * left; // 给出结点的左儿子的地址。 BSTNode * right; // 给出结点的右儿子的地址。 int BalanceFactor; // 结点的平衡度，用于 AVL 树。 int Size; // 以本结点为根的子树的所有结点的个数，用于顺序统计。 BSTNode ( ): left(NULL), right(NULL), Size(1), BalanceFactor(1) { } BSTNode ( const Type x ) : data(x), left(NULL), right(NULL), Size(1), BalanceFactor(1) { } BSTNode (const Type x, BSTNode * L, BSTNode * R ): data(x), left(L), right(R), Size(1), BalanceFactor(1) { } ~BSTNode( ) { } };

46 二叉排序树类 template <class Type>
class BinarySearchTree ： public BST<Type> { public: BinarySearchTree ( ) : LastFind(NULL), Root(NULL) { } ~BinarySearchTree ( ) { FreeTree(Root); } int Insert( const Type & x) { return Insert(x,Root);} //插入 x 到以 Root 为根的二叉排序树。成功则返回 1。 const Type & Find( const Type & x ) { return ( LastFind = Find(x,Root)) ? LastFind->data:ItemNotFound } // 若查找 x 成功，则返回二叉排序树中的相应数据项。否则，返回ItemNotFound。 const Type & FindMin( )const { const BSTNode * p = FindMin(Root); return p ? p->data:ItemNotFound; } //返回二叉排序树中的最小的数据项。若树为空，返回 ItemNotFound。 const Type & FindMax( ) const { const BSTNode * p = FindMax(Root); } //返回二叉排序树中的最大的数据项。若树为空，返回 ItemNotFound。

47 二叉排序树类 int IsFound (const Type & x) { return Find(x,Root)!= NULL;} //若 x找到，则返回 True。 int WasFound ( ) const { return LastFind != NULL;}//最近一次查找成功，则返回 True。 int Remove( const Type & x ) { return Remove(x, Root);} // 从二叉排序树中删除值为 x 的结点，删除成功返回 True。 int RemoveMin( ) { return RemoveMin(Root);} // 从二叉排序树中删除最小结点，删除成功返回 True。 int IsEmpty( ) const { return Root == NULL; } //二叉排序树为空，返回 True，否则为 False。 void MakeEmpty ( ){ FreeTree(Root); Root = NULL;} //清除二叉排序树中的所有结点。 protected: BSTNode<Type> * Root; const BSTNode<Type> * LastFind; Type ItemNotFound; // 用于查找失败时返回。 const BSTNode<Type> * Find ( const Type & x，const BSTNode<Type> * T) const; const BSTNode<Type> * FindMin ( const BSTNode<Type> * T) const; const BSTNode<Type> * FindMax ( const BSTNode<Type> * T) const; int Insert( const Type & x，BSTNode<Type> * & T); int RemoveMin( BSTNode<Type> * & T); int Remove( const Type & x，BSTNode<Type> * & T); };

48 二叉排序树的查找 122 template <class Type>
分割式查找法： 查找步骤：若根结点的关键字值等于查找的关键字，成功。 否则，若小于根结点的关键字值，查其左子树。大于根结点的关键 字值，查其右子树。在左右子树上的操作类似。 122 template <class Type> BSTNode<Type > * BinarySearchTree<Type>:: Find(const Type & x, const BSTNode<Type > * T) const { while ( T != NULL ) if ( X < T->data ) T = T->left else if ( X > T->data ) T = T->right; else return T; return NULL； } // 查找失败，返回空。查找成功，返回指向相应结点的指针。 250 99 200 300 110 105 230 216

49 二叉排序树的查找分析 15 50 20 20 60 30 15 30 70 ASL=(1+2+2+3+3+3)/6=14/6 50 60
平均情况分析（在成功查找两种的情况下） e.g: 下述两种情况下的成功的平均查找长度 ASL 15 50 20 20 60 30 15 30 70 ASL=( )/6=14/6 50 60 70 AVL=( )/6=21/6

50 二叉排序树的查找分析 平均情况分析（在成功查找两种的情况下） 在一般情况下，设 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/3 P(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) 50 20 60 15 30 70 左子树0到n-1个结点 右子树n-1到0个结点

51 插入操作 插入算法： 首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。 若二叉树为空。则首先单独生成根结点。 注意：新插入的结点总是叶子结点。 e、g：将数的序列：122、99、250、110、300、280 作为二叉排序树的结 点的关键字值，生成二叉排序树。 122 250 300 110 280 99 122 250 300 110 99 122 250 99 122 122 250 110 99 122 99

52 插入操作 template <class Type>
插入算法：输入一系列数据，分别置为结点的数据场之值。至特定的数据时结束。 template <class Type> int BinarySearchTree<Type> :: Insert (const Type & x, BSTNode<Type > * & T ) { if ( T = = NULL ) { T = new BSTNode<Type> (x); return 1; } // 新结点插入。 else if ( x < T->data ) return Insert( x, T->left ) // 转向左子树。 else if ( x > T->data ) return Insert( x, T->right ) // 转向右子树。 return 0；// 若结点已经存在，返回不必重复插入标志。 } // 插入结点到以 T 为根的二叉排序树中去。插入成功返回 1，插入失败返回 0。 122 思考：设计一个非递归的插入程序时，应注意的问题？ 250 99 300 110 280

53 删除操作 叶子结点：直接删除，更改它的父亲结点的相应指针场为空。如：删除数据场为 15、70 的结点。 50 50 20 60 20 60 15 30 70 30 子树的根结点：若被删结点的左儿子为空或者右儿子为空。如何处理呢？

54 删除操作 子树的根结点：若被删结点的左儿子为空。 如下图所示，删除结点的数据场的关键字值为为 99 的结点。 400 400 99 删除 450 450 122 122 被删结点 500 500 110 250 250 99 105 200 300 200 300 110 230 105 230 216 216

55 删除操作 子树的根结点：若被删结点的右儿子为空。 如下图所示，删除结点的数据场的关键字值为为 330 的结点。 400 400 330 删除 450 450 122 122 500 500 250 250 99 99 230 300 200 300 110 110 216 316 330 105 105 316 被删结点

56 删除操作 子树的根结点：若被删结点的左儿子为空或者右儿子为空。 如下图所示，删除结点的数据场的关键字值为为 99 、330 的结点。 400 450 122 被删结点 结论：·将被删结点的另一儿子作为它的父 亲结点的儿子，究竟是作为左儿子 还是右儿子依原被删结点和其父亲 结点的关系而定。 ·释放被删结点的空间。 这样，就同被删结点是叶子的情况统一起来了。 500 250 99 200 300 110 105 330 被删结点 316

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

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

59 删除操作 子树的根结点：若被删结点的左、右子树皆不空，则： 通常的做法：选取“替身”取代被删结点。有资格充当该替身的是谁哪？ 左子树中最大的结点(被删结点的左子树中的最右的结点，其右儿子指针场为空) 或 右子树中最小的 结点(被删结点的右子树中的最左的结点，其左儿子指针场为空) ，参看下图。 要点：维持二叉排序树的特性不变。在中序周游中紧靠着被删 结点的结点才有资格作为“替身”。 被删结点 400 450 122 结论：·先将替身的数据场复制到被删结点 ·将原替身的另一儿子作为它的父亲 结点的儿子，究竟是作为左儿子还 是右儿子依原被删结点和其父亲结 点的关系而定。 ·释放原替身结点的空间。 500 250 99 替身 200 300 110 替身 230 105 216

60 删除操作的实现 template <class Type>
int BinarySearchTree<Type>:: Remove( const Type & x, BSTNode<Type > * & T ) { BSTNode<Type > * p; if ( T == NULL ) return 0; // 删除失败，返回 0。 else if ( x < T->data ) return Remove( x, T->left ); // 转向左子树。 else if ( x > T->data ) return Remove( x, T->right ); // 转向右子树。 else if ( T->left != NULL && T->right != NULL ) { // 被删结点的左右儿子非空。 p=( BSTNode<Type> * )FindMin(T->right); T->data=p->data; //复制右子树最小结点数据值。 return RemoveMin( T->right ); //删除被删结点的右子树的最小结点。 } p = T; // 处理被删结点的至少一个儿子结点为空的情况。 T = ( T->left == NULL ) ? T->right : T->left; delete p; return 1； } // 删除成功，返回1。删除失败，返回 0。 122 250 300 110 200 99 105 400 450 500 被删结点 替身

61 删除操作的实现 template <class Type>
int BinarySearchTree<Type> :: RemoveMin( BSTNode<Type > * & T ) { if ( T == NULL ) return 0; else if ( T->left != NULL ) return RemoveMin( T->left ); BSTNode<Type > * p; p = T; T = T->right; delete p; return 1； } // 删除 T 的最左方的左后代，删除成功，返回1。删除失败，返回 0。 400 122 450 99 250 500 110 200 300 105

62 顺序统计 求出序列中的第 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 (1) K < SL (2) K > SL (3) K == SL+1 (转左) (转右) (找到)

63 顺序统计 实现方法：建立类 OrderStatisticsTree 。 template <class Type>
class OrderStatisticsTree : public BinarySearchTree<Type> { public: OrderStatisticsTree ( ) { } const Type & FindKth ( int K ) const { if ( Root = = NULL ) return ItemNotFound; else return ( FindKth( K, Root))->data; } // 查找第 K 个最小的结点。 成功，则返回的相应数据值。否则，返回ItemNotFound。 int Insert( const Type & x) { return Insert(x,Root);} //插入 x 到以 Root 为根的二叉排序树中。成功则返回 1。 int Remove( const Type & x ) { return Remove(x, Root);} // 删除数据值为 x 的结点，删除成功返回 1。 int RemoveMin( ) { return RemoveMin(Root);} // 删除最小结点，删除成功返回 True。 private: int Insert( const Type & x，BSTNode<Type> * & T); int RemoveMin( BSTNode<Type> * & T); int Remove( const Type & x，BSTNode<Type> * & T); const BSTNode<Type> * FindKth ( int K, const BSTNode<Type> * T ) const; int Treesize( ) const { return Root ? Root->Size : 0; } };

64 顺序统计 顺序统计及其实现：求出序列中的第 k 个大的或小的结点。主要操作的实现。
template <class Type> const BSTNode<Type> * OrderStatisticsTree<Type> :: FindKth ( int K, const BSTNode<Type > * T ) const { if ( T == NULL ) return NULL; // 错，返回。 int LeftSize = T->left ? T->left->Size :0; // 求得左子树的结点数。 if ( K == LeftSize + 1 ) return T; // 求得第 K 个结点。 if ( K < LeftSize + 1 ) return FindKth( K, T->left ) // 转向左子树。 return FindKth( K - LeftSize –1, T->right ); // 转向右子树。 } // 求第K个最小的结点。失败，返回NULL，否则返回第K个最小结点的地址。 template <class Type> int OrderStatisticsTree<Type> :: Insert (const Type & x, BSTNode<Type > * & T ) { if ( T == NULL ) return ( T = new BSTNode<Type> (x) ) != NULL; //新结点插入。 else if ( x < T->data ) return Insert( x, T->left ) ? ++T->Size : 0; //转向左子树。 else if ( x>T->data ) return Insert( x, T->right ) ? ++T->Size : 0; //转向右子树。 else return 0； // 若结点已经存在，返回不必重复插入标志。 } // 成功插入时，其祖先结点的 Size值加 1。

65 平衡二叉排序树（AVL树） A E B F C C D G B D E A F G 起因：提高查找速度，避免最坏情况出现。如右图情况的出现。
虽然满二叉树的树型最好，但构造困难。常使用平衡树。 A E B F C C D G B D E A F G 平衡因子（平衡度）：结点的平衡度是结点的左子树的高度－右子树的高度。 平衡二叉树：每个结点的平衡因子都为 ＋1、－1、0 的二叉树。或者说每个 结点的左右子树的高度最多差一的二叉树。 苏联数学家G.M. Adelson-Velskii和E.M. Landis, 1962.

66 平衡二叉排序树 注意：满二叉树必为平衡树，平衡树不一定是满二叉树。 -1 -1 14 14 +2 -1 +1 -1 9 28 9 28 +1 +1 -1 +1 -1 5 18 50 5 12 18 50 30 60 30 60 3 17 3 7 17 53 63 53 63 不是平衡树 是平衡树不是满二叉树

67 平衡二叉排序树 平衡树的 Adelson 算法的本质特点： 以插入为例： 在左图所示的平衡树中插入数据场为 2 的结点。 插入之后仍应保持平衡二叉排序树的性质不变。 危机结点 -1 14 -1 +1 -1 14 9 28 +2 +1 -1 9 28 +1 -1 5 12 18 50 +1 +1 -1 原平衡度为 0 5 12 18 50 30 60 3 7 17 +1 30 60 3 7 17 53 63 53 63 2 平衡树 如何用最简单、最有效的办法保持平衡二叉排序树的性质不变？

68 平衡二叉排序树 平衡树的 Adelson 算法的本质特点： 以插入为例： 在左图所示的平衡树中插入数据场为 2 的结点。 插入之后仍应保持平衡二叉排序树的性质不变。 危机结点 解决方案： 不涉及到危机结点的父亲结点，即以危机结点为根的子树被新的子树取代后的高度应保持不变（左图为 3 ）。 新结点插入后，找到第一个平衡度不为 0 的结点（如左图结点 ）即可。新插入的结点和 第一个平衡度不为 0 的结点(也可能是危机结点，也可能不是)之间的结点，其平衡度原来皆为 0 在调整中，仅调整那些在平衡度变化的路径上的结点（如： ），其它结点不予调整。新子树的根应从它们之中选取。 仍应保持二叉排序树的性质不变。 -1 14 +2 +1 -1 9 28 9 +1 +1 -1 原平衡度为 0 5 12 18 50 +1 30 60 3 7 17 53 63 3 5 9 2 危机结点和新插入的结点之间的平衡度原为 0 ，这一点，可以通过反证法加以证明。如在 LL 情况下，危机结点的平衡度力图从 ＋1 改变为 ＋2。假定：危机结点和新插入的结点之 间的平衡度原不为 0 ，如设图中的结点 5 的平衡度原为 ＋1，那么结点 5 将为危机结点。如 设图中的结点 5 的平衡度原为 －1，那么结点 5 的平衡度将改变为 0，不会导致结点结点 9 力图成为危机结点（因为结点 9 的左子树的树高在新结点插入前后没有变化）。所以，结 点 5 的平衡度原为 ＋1 或 －1 都是和结点 9 是危机结点相矛盾。 如何用最简单、最有效的办法保持平衡二叉排序树的性质不变？

69 平衡二叉排序树 平衡树的 Adelson 算法的本质特点： 以插入为例： 在左图所示的平衡树中插入数据场为 2 的结点。 插入之后仍应保持平衡二叉排序树的性质不变。 危机结点 -1 14 2 3 5 7 9 12 +2 +1 -1 9 28 5 +1 +1 -1 原平衡度为 0 5 12 18 50 3 9 +1 30 60 3 7 17 2 7 12 53 63 2 7 如何用最简单、最有效的办法保持平衡二叉排序树的性质不变？ 不可以以结点 为子树的根结点！！虽然，对本例来说是可以行得通的。

70 平衡二叉排序树 平衡树的 Adelson 算法的本质特点： 以插入为例： 在左图所示的平衡树中插入数据场为 2 的结点。 插入之后仍应保持平衡二叉排序树的性质不变。 危机结点 -1 -1 14 14 +2 +1 -1 -1 9 28 28 5 +1 +1 -1 原平衡度为 0 +1 -1 5 12 18 50 +1 18 50 3 9 +1 30 60 3 7 17 30 60 17 2 7 12 53 63 2 53 63 关键：将导致出现危机结点的情况全部分析清楚！！

71 平衡二叉排序树的插入 LL 改组 A B B A B A B A B A 左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：
1、LL 情况：（LL：表示新插入结点在危机结点的左子树的左子树上） 危机结点 +2 +1 A B +1 B A LL 改组 AR h-1 BL h BR AR h-1 BL BR h-1 h h-1 h-1 改组前：高度为 h + 1 中序序列： 改组后：高度为 h + 1 中序序列： B A B A BL BR AR BL BR AR B A 注意：改组后 平衡度为 0

72 平衡二叉排序树的插入 LR 改组 A C B A B C B C A B C A B C A
左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析： 2、LR 情况：（LR：表示新插入结点在危机结点的左子树的右子树上） 情况A： 危机结点 +2 +1 A C -1 -1 B LR 改组 A B AR h-1 +1 C h-1 BL h-2 h-1 BL h-1 CL CR AR h-1 h-2 h-2 h-1 CL CR 改组后： 高度为 h + 1 中序序列： 改组前： 高度为 h + 1 中序序列： B C CR A BL CL AR B C CR A BL CL AR 注意：改组后 平衡度为 0,0,-1 B C A

73 平衡二叉排序树的插入 LR 改组 A C B A B C B C A B C A B C A
左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析： 2、LR 情况：（LR：表示新插入结点在危机结点的左子树的右子树上） 情况B： 危机结点 +2 +1 A C -1 +1 B LR 改组 A B AR h-1 -1 C h-1 BL h-2 h-1 h-1 BL CL CR AR h-1 h-2 h-2 CL CR h-1 改组后： 高度为 h + 1 中序序列： 改组前： 高度为 h + 1 中序序列： B CL C BL CR A AR B CL C CR A BL AR 注意：改组后 平衡度为 +1,0,0 B C A

74 平衡二叉排序树的插入 LR 改组 A C B B A C B C A B C A B C A B C
左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析： 2、LR 情况：（LR：表示新插入结点在危机结点的左子树的右子树上） 情况C： 危机结点 +2 +1 A C -1 B B A LR 改组 C 新插入结点 注意：改组后 平衡度为 0,0,0 改组前： 高度为 2 中序序列： 改组后： 高度为 2 中序序列： B C A B C A B C A 四种情况的区分： 如果 的平衡度为＋1 则为 LL型改组； 否则为 LR型改组：若 的平衡度为＋1、－1 、0 ；则分别为 LRA、LRB、LRC型改组。 B C

75 平衡二叉排序树的插入 注意：本书有一个实现插入的程序，请自己仔细阅读，不再详细解释。
右改组（新插入结点出现在危机结点的右子树上进行的调整）的情况分析： 1、RR 情况：（RR：表示新插入结点在危机结点的右子树的右子树上） 处理图形和 LL 镜象相似；见下图的处理方法。 2、RL 情况：（RL：表示新插入结点在危机结点的右子树的左子树上） A、处理图形和 LRA 镜象相似 B、处理图形和 LRB 镜象相似 C、处理图形和 LRC 镜象相似 注意：本书有一个实现插入的程序，请自己仔细阅读，不再详细解释。

76 平衡二叉排序树的插入 LL 改组 A B B A A A B B 左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：
LL 情况：（LL：表示新插入结点在危机结点的左子树的左子树上） 危机结点 +2 +1 A B +1 B A LL 改组 AR h-1 BL h BR AR h-1 BL BR h-1 h h-1 h-1 右改组（新插入结点出现在危机结点的右子树上进行的调整）的情况分析： RR 情况：（RR：表示新插入结点在危机结点的右子树的右子树上） 危机结点 危机结点 +2 +1 -1 -2 A A +1 B B -1 h-1 AL AR h-1 BL BR h-1 h-1 BL BR h-1 h h-1 h

77 平衡二叉排序树的查找分析 定理：具有 N 个结点的平衡树，高度 h 满足：log2(N+1) <= h <= 1.44log2(N+1) ; 最大高度通常可认为是： loga((N+1)× sqr(5)) - 2；这里 α＝ (1＋sqr(5))/2。 证明：1、高度为 h 的二叉树最多有 2h - 1个结点，平衡树的结点个数不会超过 2h - 1 个。 即： N <= 2h - 1 ；N + 1 <= 2h ， 所以： log2(N+1) <= h 注意：sqr(5) 表示 5 的平方根 2、为了证第二步，构造一系列平衡树， T1 、 T2 、 T3 、……. TH；这种树的高度分别为 1、2、3、 ……H。且是具有高度为1、2、3、……H的平衡树中结点个数最少的二叉树，或者是用同样的 结点构造的尽可能高的二叉树。即 h <= H。 T1 高度 H = 1 结点个 数最少 T2 高度 H = 2 结点个 数最少 对 照

78 平衡二叉排序树的查找分析 TH-1 TH-2 T3 高度 H = 3 结点个 数最少 对 照 对 照 T4 高度 H = 4 结点个 数最少
TH 高度 H 结点个数最少的平衡树 左子树为 TH－1 右子树为TH－2 TH-1 TH-2

79 平衡二叉排序树的查找分析 定理：具有 N 个结点的平衡树，高度 h 满足：log2(N+1) <= h <= 1.44log2(N+1) ; 最大高度通常可认为是： loga((N+1)× sqr(5)) - 2；这里 α＝ (1＋sqr(5))/2。 证明：2、设 t(H) 是高度 H 的平衡树 TH 的结点个数，可以得出： t(1) = 1; t(2) = 2; t(3) = 4; t(4) = 7; . t(H) = t(H-1) + t(H-2) + 1 for H >= 3 该数的序列为 1、2、4、7、12、20、33、54、 … 而 Fibonacci 数列为：0、1、1、2、3、5、8、13、21、34、55、89…… 所以： t(H) = f(H+2) - 1；于是转化为求 Fibonacci 数的问题。 由于： f(H+2) ＝ (αH+2 - βH+2 )/ sqr(5); 这里 α＝ (1＋sqr(5))/2; β＝ (1－sqr(5))/2 在一般情况下：N >= f(H+2) - 1 而 f(H+2) > αH+2 / sqr(5) －1 所以，N > αH+2 / sqr(5) － 2 所以，N >＝ αH+2 / sqr(5) － 1 根据上式可求出：h <= 1.44log2(N+1) * 注意： f(H+2)-1最少结点数 * 可以证明得到。 在一般情况下：N >= f(h+2) - 1 而 f(h+2) > αh+2 / sqr(5) － 1 所以，N > αh+2 / sqr(5) － 2 根据上式可求出：h <= 1.44log2(N+1) 注意： f(h+2) - 1 是构造高为 h 的平衡树最少的结点数。所以，N > αh+2 / sqr(5) － 2。

80 平衡二叉排序树的删除 · 1. 删除具有给定关键字的结点： 操作：删除左子树中最大的结点，按照在二叉排序树中的 规则进行删除。 若删除右子树中的最小结点，方法类似。参见下图，删除KEY=122的结点。 被删结点 400 400 450 122 450 200 500 250 500 99 250 99 200 200 替身 删除替身 注意：替身被删除之后，它的父亲结点的右子树的高度将减少 1。

81 平衡二叉排序树的删除 -1 调整后 +1 调整后 P P P P 2、调整
操作：沿着替身结点到根结点的路径，进行调整。在最坏情况下，调整动作可能进行到根结点为止。 另外，有可能导致整个二叉排序树的高度降低一层。 下面以删除操作发生在左侧时为例，来分析在调整过程中遇到的各种情况。 情况A：调整后，不需继续调整了。因子树调整前后的高度都为 h+1。 -1 调整后 P P h h h-1 h 情况B：调整后，必需继续调整。因子树调整后的高度减少 1。 +1 调整后 P P h h-1 h-1 h-1

82 平衡二叉排序树的删除 -1 +1 调整后 -1 -1 调整后 -1 P Q Q P P Q Q P
情况C.1：调整后，不需继续调整。因子树调整前后的高度都为 h+1。 -1 +1 调整后 P Q -1 Q P h-1 h-1 h-1 h-1 h-2 h-1 情况C.2：调整后，必须继续调整。因子树调整后的高度减少了 1。 -1 调整后 P Q -1 Q P h-1 h-1 h-2 h-1 h-2 h-2

83 平衡二叉排序树的删除 -1 调整后 +1 +1 -1 P R Q P Q R
情况C.3a：调整后，必须继续调整。因子树调整后的高度减少了 1 。 -1 调整后 P R +1 +1 Q P Q h-1 -1 R h-2 h-3 h-2 h-2 h-2 h-3 h-2

84 平衡二叉排序树的删除 -1 调整后 +1 P R Q P Q R 情况C.3b：调整后，必须继续调整。因子树调整后的高度减少了 1。 h-1
调整后 P R +1 Q P Q h-1 R h-2 h-2 h-2 h-2 h-2 h-2 h-2

85 平衡二叉排序树的删除 -1 调整后 +1 -1 +1 P R Q P Q R
情况C.3c：调整后，必须继续调整。因子树调整后的高度减少了 1。 -1 调整后 P R +1 -1 Q P Q h-1 +1 R h-2 h-2 h-2 h-3 h-2 h-2 h-3

86 红黑树 起因：它是平衡二叉排序树最好的替代数据结构，程序实现相对简单。 查找、插入、删除等基本操作同样是O（logn）级的。 红-黑树定义：
14 起因：它是平衡二叉排序树最好的替代数据结构，程序实现相对简单。 查找、插入、删除等基本操作同样是O（logn）级的。 9 28 红-黑树定义： 1、 每个结点被染成红色或黑色。 2、 根结点是黑色的。 3、 如果一个结点是红色的，那末它的儿子结点必须是黑色的。 4、空结点通常认为是黑色的。 5、从任何一个结点出发（或从根结点出发）到空结点或叶子 结点的路径上，必须包含相同数目的黑色结点。 5 12 25 50 60 3 20 26 30 15 23 注意： 意味着是黑色结点，下同。 14

87 红黑树的层数 红-黑树层数最小、最大分析： 最小：从根开始，连续跟随父结点的子结点都是黑色的。 设为 K。
14 9 28 5 12 25 50 60 3 20 26 30 红-黑树层数最小、最大分析： 最小：从根开始，连续跟随父结点的子结点都是黑色的。 设为 K。 最大：从根开始，“插入”尽可能多的红结点，由于红结点不能连 续存在，所以将为：黑、红、黑、红……黑、红的情况， 这时的层数将不超过 2K。 设该红黑树的高度(即层数)为 H，则 K ≤ H ≤ 2K ， 又：2K - 1≤ n; ∴ K ≤ log(n + 1) 故： 2K ≤ 2log(n + 1) 是 O(logn)的。 15 23

88 红黑树的插入 插入：新结点插入后，令其为红色结点，因若令它为黑色结点将违反性质5。 插入要点：
1、 新插入的红结点X，如其父结点为黑结点则插入结束。 2、 新的红结点X，其父结点P是红色的。则： 父结点P的兄弟结点S是红色的（空结点认为是黑结点），P 的父结点G（结点X的祖父结点），肯定是黑色的。可分二种 情况：主要矛盾解决不可以有连续的红结点存在，当然不可 违反二叉排序树的性质 A、结点X是结点G的外侧孙结点：P 成为新的根结点，注意P 为红结点。 G 调整为 注意：红结点可能向上波及，引起新的调整。 P P S X G X C D E A B C S A B D E

89 红黑树的插入 插入要点： 2、 新的红结点X，其父结点P是红色的。则： 父结点P的兄弟结点S是红色的（空结点认为是黑结点），P
的父结点G（结点X的祖父结点），肯定是黑色的。可分二种 情况： B、结点X是结点G的内侧孙结点：G仍是根结点，但G变为红结 点，而其子结点变为黑结点；仅仅改变颜色而已。 G 调整为 G P S P S A A X D E X D E B C B C

90 红黑树的插入 插入要点： 3、 新的红结点X，其父结点P是红色的。则： 父结点P的兄弟结点S是黑色的（空结点认为是黑结点），P
的父结点G（结点X的祖父结点），肯定是黑色的。可分二种 情况： A、结点X是结点G的外侧孙结点：P成为根结点 G P 调整为 P S X G X C D E A B C S A B D E

91 红黑树的插入 插入要点： 3、 新的红结点X，其父结点P是红色的。则： 父结点P的兄弟结点S是黑色的（空结点认为是黑结点），P
的父结点G（结点X的祖父结点），肯定是黑色的。可分二种 情况： B、结点X是结点G的内侧孙结点：X 成为新的根结点。 G X 调整为 注意：结点P如果是结点G的右儿子，调整方法类似。 P S P G A X D E A B C S B C D E

92 红黑树的插入 新的插入法：上述插入法中可能引起子树的根结点为红结点， 从而向上波及，最坏情况下，波及到根结点。使得结点S不会是红结点，可避免这种情况。使算法更简单、有效。 新法要点：从根结点开始，自上而下的插入法。 1、遇到结点X的二个儿子结点是红结点时，就将结点X着色为红色 ，而将它的二个儿子着色为黑色结点。 2、如果结点X的父结点是红色的，就会导致二个连续的红色结点 。但是，即使在这种情况下，算法要进行的调整变换也可能仅 仅是老插入法的第 3 种情况。如：下图可能出现，X 的父结点 的兄弟结点为黑结点。 调整为 X X D C D C B D E C A G S X P 调整为 右图调整方式 P P X X C D C D

93 红黑树的插入 如：下图不可能出现，X 的父结点 P 的兄弟结点不可能为红结点,若为红色，早就进行了调整，但那样将会导致结点 P 不是红色，是黑色，这是不可能的。 如下面右图所示。 调整为 X X C D C D 这二层上，除X外，只可能为黑结点。 G G P X X C D C D

94 例：红黑树的插入 插入调整实例，以在下图的红黑树中插入结点 18 为例。           14 14 9 28 G
P 9 28 P S X G 5 12 25 X S 50 5 12 25 50 30 60 60 3 20 26 3 20 26 30 15 23 15 23 14 14    9 25 9 25 5 12 20 28 5 12 20 28 26 50 26 50 3 15 23 3 15 23 30 60 18 30 60       

95 红黑树的删除 删除：若自上而下删除的是红结点，将使算法得到简化。 删除要点： 1、采用自顶(根)向下的方式进行，在二叉排序树中删除一个结点可
以归纳为删除一个儿子为空时的结点的情况进行处理。若被删结 点是红色的，删除操作结束，因为并未引起红-黑树性质的改变 。但是，若被删结点是黑色的，那末将会引起黑结点数量的减少 ，如果我们能够保证被删结点是红色的，就可以简化删除操作。 2、自根出发进行自上而下的“寻找”。设结点X是所遇到的当前结点，T是它的兄弟结点，而结点P 是它们的父结点。我们可以从第一个着色为红色的“哨兵”结点开始，向下搜索。在搜索时，保证当前结点是红色的。这样，当搜索到一个新结点X (即将成为当前结点)时，可以确信其父结点P是红色的，而结点X和T是黑色的。 注意：为了处理方便，通常开始时将根结点涂成“红色”（其儿子结点都为黑色时），因这样作每条路径上的黑结点的总数仍相等。调整结束，若根结点仍是红色，改成黑色即可；因自根结点出发的每条路径上的黑结点数目，同样相等。 分以下几种情况，进行讨论： “哨兵”释疑： 1、若根结点和其儿子结点皆“黑” 将根结点染“红”，根为哨兵。 2、若二个儿子结点皆红，则其中之 一将为“哨兵”（依谁在到达被删 结点的路径上而定）。 3、若二个儿子一红一黑，则 1、红儿子可能为哨兵，若它在 到达被删 结点的路径上。 2、否则见 97 页的处理方法。

96 红黑树的删除 C.结点X有二个黑色儿子，T 有一个内侧的红色儿子，必须进行换调整。 删除： 分以下几种情况，进行讨论：情况一
A、结点X有二个黑色儿子，T 有二个黑色儿子，调整颜色。 P P 调整为 X T X T 调整为 P T X R 黑 黑 黑 黑 黑 黑 B.结点X有二个黑色儿子，T 有一个外侧的红色儿子，必须进行 变换调整。 P 调整为 T X T P R 黑 黑 R X 黑 黑 黑 黑 注意：调整之前结点 P 为红色结点，调整之后结点X（当前结点）为红结点。 空儿子为黑结点，若结点 X 是叶子结点，它的二个儿子都为黑色。 若结点 T 的二个儿子都为红色，则情况 B、C 都可处理。

97 红黑树的删除 删除： 仍沿着到达被删结点的路径，自当前结点(染成红色，见下图A中的最上面一个红结点)到结点X。 情况二：结点X有一个儿子是红色的(若二个儿子都为红的,“前进”一层之后,当前结点必为红,继续处理) 继续前进到下一层，就可以得到新的X、P、T。如果幸运的话，“前进”一层之后，当前结点正好就是红 色结点，这大概有一半的可能性。这满足了当前结点染红的要求。 否则的话，将得到如图B所示的情况：调整到图C的情况，使得结点X’的父结点P是红色的。和在第一种情况中 进行调整的情形一样，进行了调整。注意：以后可继续从图C中结点P(已为红色，即图A中的当前结点X)出发进行调整。反复地进行这样二种情况对应的变换调整操作。一旦到达被删结点本身就是红色结点，删除即可进行；或者该被删结点为黑，其一个儿子为空（空儿子亦为黑），另一个儿子为空或非空。问题同样可以得到解决。因此时，被删结点 X 的最终状态必为下列二种状态之一： 1、X 是叶结点。由于 X 的二个空儿子结点都作为黑色结点处理的，因此总是可以归纳到第一种情况（见 前一页的情况一的 A、B、C 三种具体情况 ）加以处理。将结点 X 着色为红色后删除。 2、X 有一个非空儿子。该儿子肯定是红色的，可将结点 X 删除，并将该儿子结点着色黑色即可。 注意：此时该非空儿子不会是黑色的（若是黑色虽然可用第一种情况中的A、B、C 三种具体情况处理， 将结点 X 染红后删除）；否则将违反红黑树性质 5。 T X P X’ T P C B C B C X’ B A） B） C）

98 例：红黑树的删除 删除：采用自上而下删除算法的实例。如：右方的红黑树删除结点9。 由于根结点的二个儿子黑结点，先将根结点改为红色。 14
12 5 3 9 28 26 15 60 50 20 25 30 23 14 12 5 3 28 26 15 60 50 20 25 30 23

99 例：红黑树的删除 删除：采用自上而下删除算法的实例。如：右方的红黑树删除结点9。 由于根结点的二个儿子黑结点，先将根结点改为红色。 黑
情况一C 变换 调整为 P T X R 黑 删除：采用自上而下删除算法的实例。如：右方的红黑树删除结点9。 由于根结点的二个儿子黑结点，先将根结点改为红色。 14 12 5 3 9 28 26 15 60 50 20 25 30 23 14 12 5 3 28 26 15 60 50 20 25 30 23 执行情况一 C 变换 25 14 28 12 20 26 50 5 15 23 30 60 12 3

100 例：红黑树的删除 · 红黑树 删除：采用自上而下删除算法的实例。如：右方的红黑树删除结点9。
· 红黑树 调整为 P T X R 黑 删除：采用自上而下删除算法的实例。如：右方的红黑树删除结点9。 由于根结点的二个儿子黑结点，先将根结点改为红色。 14 12 5 3 9 28 26 15 60 50 20 25 30 23 14 12 5 3 28 26 15 60 50 20 25 30 23 情况一B变换 P T T X R P R 黑 黑 X 情况一B的镜像对称变换 黑 黑 执行情况一 C 变换 执行情况一B的镜像对称变换 28 26 15 60 50 20 30 23 12 5 3 14 25

101 例：红黑树的删除 删除：采用自上而下删除算法的实例。如：右方的红黑树删除结点9。 由于根结点的二个儿子黑结点，先将根结点改为红色。
14 12 5 3 9 28 26 15 60 50 20 25 30 23 14 12 5 3 28 26 15 60 50 20 25 30 23 28 26 15 60 50 20 30 23 12 3 5 14 25 执行情况一 C 变换 执行情况一B的镜像对称变换 28 26 15 60 50 20 30 23 12 5 3 14 25

102 例：红黑树的删除 · 红黑树 删除：采用自上而下删除算法的实例。如：右方的红黑树删除结点9。
· 红黑树 删除：采用自上而下删除算法的实例。如：右方的红黑树删除结点9。 由于根结点的二个儿子黑结点，先将根结点改为红色。 14 12 5 3 9 28 26 15 60 50 20 25 30 23 14 12 5 3 28 26 15 60 50 20 25 30 23 28 26 15 60 50 20 30 23 12 3 5 14 25 执行情况一 C 变换 执行情况一B的镜像对称变换 28 26 15 60 50 20 30 23 12 5 3 14 25 问题：1、若根结点的二个儿子结点都为红结点或一红一黑？ 2、若删除操作结束，根结点仍为红色，如何处理？

103 B-树和B+树 内存 50 75 25 15 35 60 90 · 为什么采用B_ 树和 B+ 树？
大量数据存放在外存(如硬盘)中。由于是海量数据，不可能一次调入内存。因此，要多次 访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以，主要矛盾变为减少访外存次数。 在 1970 年由 R·Bayer 和 E· Macreight 提出用B_ 树作为索引组织文件。提高访问速度、减少时间。 例: 用二叉树组织文件，当文件的记录个数为 100，000时，要找到给定关键字的记录，需访问外存17次（log2100,000), 太长了！ 文件头，可常驻内存 50 索引文件 75 25 15 35 60 90 数据文件 95 10 20 30 40 55 70 80 内存 文件访问示意图：索引文件、数据文件存在盘上

104 B-树 B_ 树是一种多分支树，首先介绍 m 阶 B_ 树： 定义： m 阶 B_ 树满足或空，或：
A、根结点要么是叶子，要么至少有两个儿子 B、除根结点和叶子结点之外，每个结点的儿子个数s 为: m/2 <= s <= m C、有 s 个儿子的非叶结点具有 n = s － 1 个关键字，即: s = n + 1 这些结点的数据信息为： （n, A0, K1, R1, A1, K2, R2, A2, ……… Kn, Rn, An） 这里：n: 关键字的个数 A0：< K1 的结点的地址（指在该 B_ 树中） K1：关键字 R1：关键字 = K1 的数据记录在硬盘中的地址 A2：> K1 且 < K2 的结点的地址（指在该 B_ 树中） 其余类推 ……… An：> Kn 的结点的地址（指在该 B_ 树中） 注意：K1 <=K2 <= …... <= Kn D、所有的叶子结点都出现在同一层上，不带信息（可认为外部结点或失败结点）。

105 例：B-树 例：m = 4 阶 B_ 树。除根结点和叶子结点之外，每个结点的儿子个数
叶子结点都在第 4 层上。 1，35 第 1 层 1，18 2，43，78 第 2 层 第 3 层(L层) 1，11 1，27 1，39 3，47，58，64 1，99 F F F F F F F F F F F F 第 4 层(L＋1层)

106 B-树的查找 查找过程，类似于二叉树的查找。如查找关键字为 KEY 的记录。
从根开始查找，如果 Ki = KEY 则查找成功，Ri 为关键字为 KEY 的记录的地址。 若 Ki < KEY < Ki+1; 查找 Ai 指向的结点 若 KEY < K1; 查找 A0 指向的结点 若 KEY > Kn; 查找 An指向的结点 若 找到叶子，则查找失败。 注意：每次查找将去掉 （s-1）个分支，比仅仅丢掉一半分支还要快。

107 B-树的查找 设关键字的总数为 N ，求 m 阶 B_ 树的最大层次 L。 层次 结点数（最少） 关键字的个数（最少） 1 1 1
层次 结点数（最少） 关键字的个数（最少） 1 1 1 2 2 2（ m/2 -1） 3 2（ m/2 ） 2（ m/2 ） （ m/2 -1） 4 2（ m/2 ） 2 2（ m/2 ）2 （ m/2 -1） L 2（ m/2 ）L-2 2（ m/2 ）L-2 （ m/2 -1） L+1 2（ m/2 ）L-1 所以，N=1＋ 2（ m/2 -1） +……...+ 2（ m/2 ）L-2 （ m/2 -1） = 2 m/2 L-1 -1 故：L＝log m/2 （N+1）/2）+ 1 设 N ＝1000，000 且 m＝256 ，则 L <= 3；最多 3 次访问外存可找到所有的记录。

108 B-树的插入 1、确定插入位置，将结点插入到第 L 层（注意：第 L+1 层为叶子结点） 2、找到插入位置，将关键字和其它信息按序插入。
3、若被插入结点的关键字个数 >m-1, 则该结点满。必须分裂成两个结点。否则不满结束。 如结点原为： （m-1, A0, (K1, A1), (K2, A2), ……… (Km-1, Am-1)） 插入一个关键字之后变为： （m, A0, (K1, A1), (K2, A2), ……… (Km, Am)） 该结点将进行分裂：

109 B-树的插入 分裂之前： ………(Ki, Ai), (K i+1, Ai+1) ……
（m-1, A0, (K1, A1), …… (Km-1, Am-1)） 分裂之后：生成新结点 p’,将原结点的后半部分复制过去。若分裂一直进行到根，树可能长高一层。 p 力图变成： ………(Ki, Ai), (K i+1, Ai+1) …… （m, A0, (K1, A1), …… (Km, Am)） p (K m/2 , p‘ ) 数据项插入上层结点之中 ……(Ki, Ai), (K m/2 , p‘ ) , (K i+1, Ai+1) …… （m/2 -1, A0, (K1, A1), …… (K m/ , A m/ )） （m- m/2 , A m/2 , ……… (Km, Am)） p’ p

110 例：B-树的插入 例： 3 阶 B_ 树的插入操作。m=3, m/2 - 1 = 1; 至少 1 个关键字，二个儿子结点。 45，70
24，30 53 90 53 90 3，12 26 39 50 61 85 100 3 12 26 39 50 61 85 100 45 7插入 24 70 7 30 53 90 7 30 53 90 3 12 26 39 50 61 85 100 3 12 26 39 50 61 85 100

111 B-树的删除 1、查找具有给定键值的关键字 Ki 2、如果 在第 L 层，可直接删除（注意：第 L+1 层为叶子结点），转 4 。
A、不动：若删除关键字值的那个结点的关键字的个数仍处于 m/2 -1和 m-1之间。则结束。 B、借：若删除关键字值的那个结点的关键字的个数原为 m/ 。而它们的左或右邻居结 点的关键字的个数 > m/ ; 则借一个关键字过来。处理结束。 C、并：若该结点的左或右邻居结点的关键字的个数为 m/ ; 则执行合并结点的操作。 如结点原为： （ …………. (Ki, Ai), (Ki+1, Ai+1), …………. ） （ A0’, (K1’, A1’ ) ……… ） （ A0’‘, (K1’‘, A1’‘ ) ……… ） …… K1L ……… 第 L 层：找到了被删结点的替身。

112 例：B-树的删除 例：3 阶 B_ 树的删除操作。m=3, m/2 - 1 = 1; 至少 1 个关键字，二个儿子结点。 45 45 24
借：通过相应的父亲结点 向被删结点方向旋转 3 3 37 53 70 100 37 50 61，70 100 假定再删除该关键字 被删关键字 并 并 45 45 并 24 90 90 3 37 61，70 100 3，24 61，70 100 3，24 61，70 100 并：和父结点的一个关键字、及邻居合并。有可能进行到根，使B_ 树的深度降低一层！ 假定再删除该关键字

113 B＋树 A、根结点要么是叶子，要么至少有两个儿子 B、除根结点和叶子结点之外，每个结点的儿子个数为: m/2 <= s <= m
定义： m 阶 B+ 树满足或空，或： A、根结点要么是叶子，要么至少有两个儿子 B、除根结点和叶子结点之外，每个结点的儿子个数为: m/2 <= s <= m C、有 k 个儿子的非叶结点具有 k 个关键字 D、外部结点，保存信息。而叶结点可以认为是索引部分，结点中含其子树中的最大或最小结点关键字。 E、叶子结点包含关键字信息和指向相应记录的指针，且按关键字顺序相链结。

114 例：B＋树 至少为 m/2 = 2 个；结点的关键字个数至少为 2 。该 B+ 树的高为 4。 叶子结点都在第 3 层上。
27， 99 第 1 层 11，27 39，64，99 第 2 层 第 3 层(L层) 2 5 8 9 11 12 15 20 27 32 35 37 38 39 42 45 47 50 55 58 61 64 80 81 85 86 94 99 第 4 层(L＋1层)

115 B＋树的应用：VSAM · B＋树的应用：VSAM（Virtual Storage Access Method ） 文件
索引 B+树 索引 集合 顺序索引 集合起点 顺序索 引集合 数据 集合 控制区间 控制面(控制区域)

116 B＋树的应用：VSAM · B＋树的应用：VSAM（Virtual Storage Access Method ） 文件
控制区间：数据集合中的一个结点，是 VSAM 中的基本单位（like 磁道 in ISAM）。 控制面：多个控制区间和它们的顺序索引集合中的结点形成控制面（like 柱面 in ISAM） 记录信息的控制：记录可以不定长。 记录1 记录 记录n 记录n控制信息 记录n控制信息 控制区间的控制信息 溢出区的处理：取消溢出区。控制区间留有空间。控制面留有全空的控制区间。

117 B＋树的插入 新记录进入控制区间，必须保证有序。 插入流程图： 查找新记录应插入的控制区间 NO 新记录应插入后会导致该控制区间溢出吗？
新记录应插入到该控制区间 YES 有空闲的控制区间可用吗？ NO 取得新的控制面，进行控制面的分裂。将大约一半数据记录移入新的控制面；同时进行顺序索引集合中的相应的结点的分裂。必要时，修改索引集合中的信息。 将新记录插入到相应的控制区间。 取得新的控制区间。进行控制区间的分裂。将大约一半数据记录移入新的控制区间。修改顺序索引集合中相应的结点。将新记录插入到相应的控制区间。

118 B＋树的应用：VSAM 删除： 后面的结点向前移动把空间留给新插入的记录。控制区间变空，修改相应的顺序索 引集合中的索引项。
删除： 后面的结点向前移动把空间留给新插入的记录。控制区间变空，修改相应的顺序索 引集合中的索引项。 优缺点： 动态分配和释放存储，无需对文件进行重组，插入、查找快。空间利用率低，通 常只有 50％ ～ 70％。 加速的考虑：设置多个副本的顺序集合索引。 控制面的多个顺序索引集合 1 道 顺序集合索引 副本 副本 副本 控制区间 控制区间 控制区间 控制区间 2 道 3 道 控制面 控制区间 控制区间 控制区间 控制区间 磁道 >>----<< 控制区间

119 B＋树的应用：VSAM 为什么称之为 VSAM 文件：虚拟存储，同机器、设备无关。 分页格式化磁盘组 外部页面映射表 页面号 指针 1 2
3 分页：把内外存按同样的大小进行分页。使文件技术不依赖于具体的外部设备。更换外设时，不必改变整个程序，只需改变外部页面映射表中的相对地址到绝对地址的计算程序即可。 控制区间 ＝ 若干页面。控制面 ＝ 若干控制区间。外存是内存的延伸，虚拟 存储器。VSAM 可脱离具体的外存组织文件，所以称之为 VSAM 文件。

120 哈希（Hash）方法 特点：不用比较的办法，直接根据所求结点的关键字值 KEY 找到这个结点。
追求更快的速度 O(1)，优于任何其它的查找算法。 哈希表：设存储区M由 m 个单元构成，它的第一个单元的地址为 0。设表具有 n 个结点 a1, a2, a3, ………... an； 这些结点相应的关键字值分别为： k1, k2, k3, ……… kn。又设 f 函数是一个确定的函数，它能将关键字 值 ki 映射为 M 中的地址：即， f( ki ) -> 0 ~ m-1 （注意：是一个确定的地址） 该地址就是结点 ai 的存放地址。 f 函数通常称之为 hash 函数，而 M 存区称之为 hash 表。 负载系数：α ＝ n/m 哈希表 1 39 40

121 Hash方法 例：将 31 个常用的英文单词，映射到 M 存区。设 m = 41 , 映射是等可能性的。哈希函数的值在 0～40之间。
哈希表 例：将 31 个常用的英文单词，映射到 M 存区。设 m = 41 , 映射是等可能性的。哈希函数的值在 0～40之间。 1 A、AND、……YOU: 总的可能分布为 4131，不冲突的分布为 C41 ； 不 冲突的可能性为 1/10,000,000 冲突：若 ki != kk ; 但 f( ki ) = f( kk ) 31 39 40 简短的结论：选取好的 hashing 函数非常困难，不冲突的可能性 非常小 减少冲突的方法：好的 hashing 函数 减少负载系数 A的可能性 ，1…… 40 AND的可能性 0，1…… 40 其余类推

122 常用Hash函数 1. 直接地址法： 2. 除留余数法： 例：选取 p 为质数的理由：
H(key) = key 或 H(key) = a ×key ＋ b 如：k1, k2 分别有值 10 、1000；选10 、1000 作为存放地址。简单、不经济。 2. 除留余数法： H(key) = key MOD p 或 H(key) = key MOD p + c 这里 p < m 最常用，余数总在 0 ～ p-1 之间。通常选 < m 的最大质数。如：m = 1024, 则 p = 1019 例：选取 p 为质数的理由： 设 key 值都为奇数，选 p 为偶数；则 H(key) = key MOD p ，结果为奇数， 一半单元被浪费掉。 设 key 值都为 5 的倍数，选 p 为 95；则 H(key) = key MOD p ，结果为：0、 5、10、15、…… 90 。4/5 的单元被浪费掉。

123 常用Hash函数 3. 折叠法及位移法： 4. 基数转换法： 5.平方取中法： 381 412 214 key = 381，412，975
1 768 214 1 570 ＋ 3. 折叠法及位移法： key = 381，412，975 选取 768 或 570 作为散列地 址（在 m ＝1000 情况下）。 4. 基数转换法： e.g: key = 基数为10，看成是 13 进制的。 则：（236075）13 ＝ ；选取 作为散列地址（在 m ＝10000 情况下）。 5.平方取中法： e.g: （4731）2 ＝ ；选取 82 （在 m ＝100 情况下）。

124 解决冲突：线性探测 A、将溢出结点存放到散列表中未使用的单元中去：“封闭式”。 a、线性探测法：
例: 假定采用的 hash 函数为：H(key) = key MOD 11 假定的关键字序列为： 17、60、29、38 …… ；它们的散列过程为： H( 17 ) = 6 H( 60 ) = 5 H( 29 ) = 7 H( 38 ) = 5 当散列 38 时发生冲突， 同 60 争夺第 5 个单元 解决办法 ：探测下一个 空单元 步长：1 H(key) = ( key+di) MOD 11 其中： di 为 1、2……10 注意：可取其它步长，如 3 1 2 3 4 5 6 7 8 9 10 Hashing 表 60 38 17 29 38 冲突： 初级冲突：不同关键字值的结点得到同一个散列地址。 二次聚集：同不同散列地址的结点争夺同一个单元。 结果：冲突加剧，最坏时可能达到 O（n）级代价。

125 线性探测 解决办法： 改变步长：选和 m 互质的数作为步长，如 3、5、7……
如选步长为 5，用 H(key) = ( key+5) MOD 11 H(key) = ( key+ 5×2) MOD 11 H(key) = ( key+ 5×3) MOD 11 等进入下一个空的单元，直到找到为止。 随机地改变步长，如取步长序列：2，7，4，3，6，1，5 如用 H(key) = ( key+2) MOD 11 H(key) = ( key+7) MOD 11 H(key) = ( key+ 4) MOD 11 等进行探测下一个空的单元，直至 到找到为止。

126 解决冲突：二次探测 b、二次探测法： c. 再 hash 方法： 出现冲突时：H(key) = ( key+di) MOD p
其中： di 为 、 22…… k2（k<=m/2）； 称之为二次探测再散列 若取为伪随机数；称之为随机探测再散列；还有再Hash方法。 + _ c. 再 hash 方法： 出现冲突时，采用H1(key) = key MOD 11，多个 hashing 函数计算散列地址，直到找到空单元为止。 或者用另一个 hashing 函数作为步长进行探测，找到下一个空单元。 如：H1(key ) = key MOD 11 H2(key) = ( key MOD 9 )＋ 1 注意：此处 m = 11, 散列表的地址为 0～ 10 。 设 key = 42 ,则 H1(42) = 9 ，H2( 42) = 7。首先探测 9 号单元，如空则结束。否则，以 7作为步长探测下一个空单元，直到找到下一个空单元为止。

127 解决冲突 B、将溢出结点存放到散列表以外的各自的线性表中去。 将具有同一散列地址的结点保存于 M 存区的各自的链表之中。有的书称之为
外链法，通常用于组织存在于外存设备上的数据文件。 1 2 3 4 5 6 7 8 9 ∧ K1 K2 K3 K4 K5 K6 同义链，同一散列地址。

128 解决冲突 C、将溢出结点存放到散列表以外的一个线性表中去。 将发生冲突的结点都存放在一个公共溢出区内。通常用于组织存在于外存设
备上的数据文件。M 存区只存放一个记录。发生冲突的记录都存放在公共溢 出区内。M 存区和公共溢出区都可以分配几个磁道或柱面作为存储空间。 1 2 3 4 5 6 7 8 9 10 ∧ K1 K2 K3 K4 K5 K6 基本区（M 存区） 公共溢出区 K7

129 Hash表查找分析 查找方法同 hash 函数的产生办法。 其中：q i = 经过 i 次探测确定某结点不在 hashing 表中的概率。
设 hash 函数是均匀的、处理冲突后产生的地址也是均匀的。Hash 表的长度为 m。 n+1 i=1 其中：q i = 经过 i 次探测确定某结点不在 hashing 表中的概率。 = 第一到第 i-1 次探测，由于冲突而失败的概率及第 i 次探测找到空单元的概率。 = × …... 1 m n-1 m-1 m-2 n-2 n-i+2 m-i+2 n-(i-1) m-(i-1) 1- 其中：1 <= n <= n+1 可推出： Un = ∑ i × qi ＝ 1－α α = n/m n 查找不成功的平均查找长度 Un = ∑ i × qi

130 Hash表查找分析 . 查找成功的平均查找长度:
成功地找到某一个 key 所需要的探测次数恰等于将这个 key 插入到散列表中所需要的探测次数。 将 n 个key 插入到散列表中所需要的探测次数 ＝ 表空时进行插入时的探测次数 ＋ 表中有一个结点时进行插入时的探测次数 ＋ 表中有二个结点时进行插入时的探测次数 ＋ 表中有三个结点时进行插入时的探测次数 ＋ 表中有 n-1 个结点时进行插入时的探测次数 n m 1-x 1 α -1 所以： Sn = (1/n) ∑ Ui = (1/n) ∑ 1/(1- i/m)) = di = dx = ln(1-α) n-1 i=0 1-i/m .

131 Hash表的实现 template <class Type> class HashTable { public:
enum KindofCell { Active, Empty, Deleted }; // 标志 Hash表中单元的状态。Active：保存结点。Empty：单元为空。 // Deleted: 保存的结点已被删除。 HashTable ( ); ~HashTable ( ) { delete[ ] arr; } const HashTable & operator = ( const HashTable & R ); int Insert( const Type & x); //插入 x。 int Remove( const Type & x); //删除 x。 const Type & Find( const Type & x); // 查找成功，返回结点数据值。可用函数 WasFound 确定查找是否成功。 int IsFound ( const Type & x) const; //测试 x 是否存在，存在返回 1，否则为 0。 int WasFound( ) const; //最近一次查找成功，则返回 1。 int IsEmpty( ) const; // Hash 表为空，返回 1，否则为 0。 void MakeEmpty( ); // 清空 Hash 表。

132 Hash表的实现 private: struct HashCell { Type Element; // 保存结点数据值。
KindofCell info; HashCell( ): info(HashTable<Type> :: Empty ) { } HashCell( const Type & E, KindofCell i=Empty ):Element(E),info(i) { } }; enum { DefaultSize = 11 } ; int ArrSize; // 散列表用的所在的单元个数。 int CurrentSize; // 散列表中当前保存的结点个数。 int LastFindOk; // 最后一次查找成功则为 1。 HashCell * Arr; // 保存散列表用的数组。 void AllocateArr( ); // 创建一个数组。 unsigned int FindPos( const Type & x ) const; // 查找值为 x 的结点在散列表中的单元地址。

133 Hash表的实现 template <class Type >
void HashTable<Type> :: AllocateArr( ) { Arr = new HashCell[ ArrSize ]; } // 创建散列表用的数组。 template <class Type> HashTable<Type> :: HashTable ( ): ArrSize(DefaultSize ) { AllocateArr( ); CurrentSize = 0; } // 构造函数。 void HashTable<Type> :: MakeEmpty( ) { CurrentSize = 0; for ( int k = 0; k< ArrSize; k++) Arr[k].info = Empty; } // 清空散列表用的数组。 Element info 1 2 3 4 5 6 7 8 9 10 Hash 表 info 用以标志 Hash表中单元的状态。Active：已保存结点；Empty：单元为空而 Deleted: 表示保存的结点已被删除。

134 Hash表的实现 template <class Type >
unsigned int HashTable<Type> :: FindPos( const Type & x ) const { unsigned int k = 0; // 用于记录探测失败的次数。 unsigned int CurrentPos = Hash(x, ArrSize); while( Arr[ CurrentPos ].info != Empty && Arr[ CurrentPos ].Element != x ) { CurrentPos += 2 * ++k –1; while ( CurrentPos >= ArrSize ) CurrentPos -= ArrSize; } return CurrentPos; } // 探测包含 x 的单元地址。 const Type & HashTable<Type> :: Find( const Type & x ) { unsight int CurrentPos = FindPos(x); LastFindOk = Arr[ CurrentPos ] .info = = Active; return Arr[CurrentPos].Element; } // 查找成功，返回结点数据值。可用函数 WasFound 确定查找是否成功。 1 2 3 4 5 6 7 8 9 10 Hash 表 Element info

135 Hash表的实现 template < class Type >
int HashTable<Type> :: IsFound(const Type & x ) const { int CurrentPos = FindPos(x); return Arr[CurrentPos].Info == Active; } // .测试 x 是否被保存在散列表之中。    int HashTable<Type> :: Remove(const Type & x ) { unsigned int CurrentPos = FindPos(x); if ( Arr[CurrentPos].info != Active ) return 0; Arr[CurrentPos].Info = Deleted return 1; } // 删除包含 x 的单元返回 1，否则返回 0。 int HashTable<Type> :: Insert(const Type & x ) { unsigned int CurrentPos = FindPos(x); if ( Arr[CurrentPos].info = = Active ) return 0; // 已经存在，插入失败。 Arr[CurrentPos] = HashCell(x, Active); return 1; } // 将值 x 插入，返回 1。若散列表中已经存在值为 x 的单元，则插入失败，返回 0。 1 2 3 4 5 6 7 8 9 10 Hash 表 Element info