文档介绍：第八章二叉搜索树
理解以有序集为基础的抽象数据类型字典。
理解用数组实现字典的方法。
理解二叉搜索树的概念和实现方法。
掌握用二叉搜索树实现字典的方法。
理解AVL树的定义和性质。
掌握二叉搜索树的结点旋转变换及实现方法。
掌握AVL树的插入重新平衡运算及实现方法。
掌握AVL树的删除重新平衡运算及实现方法。
11/11/2017
1
福州大学数学与计算机科学学院
字典的定义
字典是以有序集为基础的抽象数据类型。
它支持以下运算:
(1)Member(x),成员运算。
(2)Insert(x),插入运算:将元素x插入集合。
(3)Delete(x),删除运算:将元素x从当前集合中删去。
(4)Predecessor(x),前驱运算:返回集合中小于x的最大元素。
(5)essor(x),后继运算:返回集合中大于x的最小元素。
(6)Range(x,y),区间查询运算:返回集合中界于x和y之间,即x≤z≤y的所有元素z组成的集合。
(7)Min( ),最小元运算:返回当前集合中依线性序最小的元素。
8 二叉搜索树
11/11/2017
2
福州大学数学与计算机科学学院
8 二叉搜索树
用数组实现字典
用数组实现字典与用数组实现字典的不同之处:
可以利用线性序将字典中的元素从小到大依序存储在数组中,通过数组下标来反映字典元素之间的序关系。
优点:
可用二分法高效地实现与线性序有关的一些运算。如:Member(x) ,Predecessor(x)和 essor(x)可在时间O(logn)内实现。
缺点:
插入和删除运算的效率较低。
每执行一次Insert或Delete运算,需要移动部分数组元素,从而导致它们在最坏情况下的计算时间为O(n)。
考虑:能否用链表来实现字典???
Member运算需要O(n)时间,一旦找到元素在链表中插入或删除的位置后,只要用O(1)时间就可完成插入或删除操作。
两种实现方式均不可取!
11/11/2017
3
福州大学数学与计算机科学学院
8 二叉搜索树
用二叉搜索树实现字典
基本思想:
用二叉树来存储有序集,每一个结点存储一个元素。
满足:存储于每个结点中的元素x大于其左子树中任一结点中所存储的元素,小于其右子树中任一结点中所存储的元素。
11/11/2017
4
福州大学数学与计算机科学学院
运算Search(const T& x) 的实现:
template<class T>
BinaryTreeNode<T>* BSTree<T>::Search(const T& x) const
//找指向x所在的结点的指针
{
BinaryTreeNode<T> *p = root;
while (p) //*p中有元素
if (x < p->data)
p = p->LeftChild;
else if (x > p->data)
p = p->RightChild;
else
break; //找到x所在的结点*p
return p; //当x不在树中时p为空
}
11/11/2017
5
福州大学数学与计算机科学学院
例{10, 18, 3, 8, 12, 2, 7, 4}
10
10
18
10
18
3
10
18
3
8
10
18
3
8
12
2
10
18
3
8
12
7
10
18
3
8
12
2
4
7
10
18
3
8
12
2
二叉搜索树的建立过程:
11/11/2017
6
福州大学数学与计算机科学学院
运算Insert(const T& x)的实现:
template<class T>
BinaryTreeNode<T>* BSTree<T>::Insert(const T& x)
{
BinaryTreeNode<T> *p = root, *pp = 0;
//从根开始检测插入位置, *pp记录插入结点的父结点
while (p) //p非空,选择其左或右子树进行插入
{
pp = p;
if (x < p->data)
p = p->LeftChild;
else if (x > p->data)
p = p->RightChild;
else
return 0 ; //表明x在树中,无需插入
}
11/11/2017
7
福州大学数学与计算机科学学院
BinaryTreeNode<T> *r = new BinaryTreeNode<T> (x);
if (root) //当前树非空
{ //确定x