第四节:二叉搜索树

4.1 二叉搜索树

二叉搜索树(BST),也称二叉排序树和二叉查找树。一棵这个树,可以为空。如果不为空,满足以下性质:

(1)非空左子树的所有键值小于其根结点的键值。

(2)非空右子树的所有键值大于其根结点的键值。

(3)左、右子树都是二叉搜索树。

1.二叉搜索树操作的函数:

Position Find(ElementType X, BinTree BST):从二叉搜索树BST中查找元素X,并返回其结点地址;

Position FindMin(ElementType X, BinTree BST):从二叉搜索树BST中查找最小元素X,并返回其结点地址;

Position FindMax(ElementType X, BinTree BST):从二叉搜索树BST中查找最大元素X,并返回其结点地址;

BinTree Insert(ElementType X, BinTree BST)

BinTree Delete(ElementType X, BinTree BST)

2.二叉搜索树的查找操作:Find

查找从根结点开始,如果树为空,返回NULL

若树非空,则根结点关键字与X进行比较,并进行以下处理:

(1)若X小于根结点键值,则在左子树中继续搜索;

(2)若X大于根节点键值,则在右子树中搜索;

(3)若两者相等,搜索完成,返回指向此结点的指针。

代码如下:

由于非递归函数的执行效率高,可将尾递归函数修改为迭代函数:

3.查找最大和最小元素

最大元素一定在树的最右分支的端结点上;最小元素在最左分支的端结点上。

4.二叉搜索树的插入

分析:关键是要找到元素应该插入的位置,可以采用与Find类型的方法。

4.二叉搜索树的删除

我们需要考虑三种情况:

(1)要删除的是叶结点:直接删除,并再修改其父结点指针为NULL。

(2)要删除的结点只有一个孩子结点:要将其父结点的指针指向要删除结点的孩子结点

(3)要删除的结点有左、右两棵子树:用另一结点代替被删除的结点:右子树的最小元素或者左子树的最大元素。如图2所示。

 1524539102126072.jpg

图1

代码如下所示:

4.2 平衡二叉树

1.平衡二叉树基本介绍

查找二叉搜索树(BST)的时间复杂度(最坏情况下)用查找过程中的比较次数来衡量,它取决于树的深度。

对于二叉树中任一结点T,其“平衡因子(Balance Factor,简称BF)”定义为BF(T)=hL-hR。(其中hL和hR分别为T的左、右子树的高度。)

“平衡二叉树(Balanced Binary Tree)”又称为“AVL树” 。 AVL树或者是一棵空树,或者是具有下列性质的非空二叉搜索树:任一结点左、右子树高度差的绝对值不超过1。”即|BF(T) |≤ 1

平衡二叉树的高度能达到logn吗?

设nh高度为h的平衡二叉树的最少结点树。结点数最少时:

nh=n(h-1)+n(h-2)+1

具体见图2.

1524539126857172.jpg 

图2

1.平衡二叉树的调整

(1)右单旋

如图3所示,当只将Mar加上May的时候,其平衡因子为-1,但是当增加了一个Nov的时候,其平衡引子变成了-2,不符合平衡二叉树的要求,因此很显然我们会想到将其调整到图3右侧的结构,这样其三个结点的平衡因子都是0了。

1524539140516138.jpg 

图3

首个不平衡的“发现者”是Mar(未必是根结点),它是调整起点位置。而“麻烦结点”Nov 在发现者右子树的右边,因而叫RR插入,需要RR旋转(右单旋);一般情况(设A是首个发现者)的调整方式如下:

 1524539153680093.jpg

图4

(2)左单旋

 1524539165635453.jpg

图5

(3)左-右双旋

 1524539179564828.jpg

图6

(4)右-左双旋

1524539192123126.jpg 

图7