开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 动态查找表之二叉排序树和平衡二叉树（图解+代码详解） -> 正文阅读

[数据结构与算法]动态查找表之二叉排序树和平衡二叉树（图解+代码详解）

动态查找表：与静态查找表不同的是，动态查找表是在查找过程中动态生成的，即对于给定值key, 若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。

主要分为：二叉排序树、平衡二叉树、B-和B+树。

我们这里主要分析讨论前两种。

二叉排序树

定义

定义：二叉排序树，又称二叉查找树。或者是一颗空树，或者是满足以下性质的二叉树：

若其左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若其右子树不空，则右子树上所有结点的值均大于它的根结点的值
其左、右子树也分别为二叉排序树

特点：二叉排序树的中序遍历序列一定是递增有序的

注意二叉排序树和二叉判定树不要搞混了，这两个区别还是比较大的，二叉判定树是静态查找的折半查找时用到的，遍历了搜索的可能性，而且结点放置的是序号。

构造二叉排序树

我们对于给定序列，取其第一个点为根结点，然后依次选择后续节点边比较边插入。如果比当前结点小，往该节点左子树移动比较，如果比当前结点大，则往该节点右子树移动比较。直到到一个待比较位置为空的位置，就是该节点的最终位置。

文字过于生硬，图解说明一下：

设输入序列为：（30,11,18,4,55,19,15,70,58）

二叉排序树构造

如此便构造成功了一个二叉排序树。

这样一来我们也可以很方便的计算出其平均查找长度，每一层的高度就是查找所花费的次数，例如：

二叉排序树

基本操作代码解析

存储结构

首先我们选择使用二叉链表作为其存储结构：

typedef struct BiTNode {
// 结点结构
	TElemType data; // 包含key
	struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;

查找操作

递归算法

思路很简单，仅需要从根节点开始比较就可以，比当前结点大就找左子树，小就找右子树直到找到为止

BiTree SearchBST (BiTree T，KeyType key){
//在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素
	//若查找成功，则返回指向该数据元素结点的指针，否则返回空指针
	if( (!T)||EQ(key，T->data.key)) 
        return (T)； //查找结束
	else if LT(key，T->data.key)
		return(SearchBST(T->lchild，key))；
	//在左子树中继续查找
	else 
        return(SearchBST(T->rchild，key))；
	// 在右子树中继续查找
} //SearchBST

非递归算法

由于我们这个不需要回溯，实际上也就是使用一个while循环代替递归的工作栈，思路和递归算法差不多。

struct BiTNode *search_tree(struct BiTNode *T, keytype key)
//返回值
失败：NULL 成功：非NULL，结点指针
{
    while (T!=NULL)
    {
        if (key==T->data.key)
		return T；
		//查找成功
	else if (key<T->data.key)
		T=T->lchild； //查左子树
	else
		T=T->rchild； //查右子树
    }
    return T；
	//查找失败
}

插入

插入的思路相对而言也比较简单，主要借助查找，把新节点作为叶子插入。代码如下：

Status InsertBST(BiTree &T, ElemType e) {
//当二叉排序树中不存在关键字等于e.key的数据元素时，
//插入元素e并返回true，否则返回false
	p = T; father = NULL;
	while (p && p->data.key!=e.key) {
		father = p;
		if (e.key>p->data.key) p = p->rchild;
		else p = p->lchild;
	}//while
    if (p) return false; //键值为e.key的结点已经存在
	s = new BiTnode; s->data = e; s->lchild = s->rchild = null;
	if (father==NULL) T = s; //空树插入
	else if (e.key>father->data.key) father->rchild = s;
	else father->lchild = s;
}//InsertBST

删除

删除操作相对于前面的查找与插入就复杂一些了。删除某元素需要维护二叉排序树的形状。这里假设*p表示待删除结点的指针， $P_L$ 和 $P_R$ 代表p的左右孩子指针，f是p的父节点，并假设p是f的左孩子。那么有三种情况需要我们考虑，一种情况是p没有左右孩子，那只需我们更改一下f的左孩子指针指向，指向空指针即可；第二种情况便是p只有一个孩子，那么这样也只需将f的左孩子指针指向 $P_L$ 或 $P_R$ ；第三种情况就是p有两个孩子，这样就需要我们分析一下了：

设删除前的中序遍历序列为： …. $P_L$ s p $P_R$ f ….
//p的直接前驱是s
//s是p左子树最右下方的结点
删除p后，使其它元素的相对位置不变。有两种解决方法：
法1：令p的左子树为 f的左子树，p的右子树接为s的右子树；即 $f_L$ = $P_L$ ; $S_R$ = $P_R$ ;
法2：直接令s代替*p即 s为p左子树最右下方的结点

图解如下：

假设删除P点。

删除结点

删除各个结点：

删除结点

代码按以上思想编写：

void Delete_BST (BSTNode *T , KeyType key )
/* 在以T为根结点的BST树中删除关键字为key的结点 */
{ BSTNode *p=T , *f=NULL , *q , *s ; //q指向删除结点的孩子
while ( p!=NULL&&!EQ(p->key, key) ) // 查找删除结点
{ f=p ;
if (LT(key, p->key) ) p=p->Lchild ;
// 搜索左子树
else p=p->Rchild ;
//搜索右子树
}
if (p==NULL) return ;
//没有要删除的结点
 s=p ;
//找到了要删除的结点为p ，先找其替代结点s
if (p->Lchild!=NULL&& p->Rchild!=NULL) // 左、右子树都不空
{ f=p ; s=p->Lchild ; // 从左子树开始找
while (s->Rchild!=NULL)
{ f=s ; s=s->Rchild ; } // 找左子树中最右边的结点
p->key=s->key ; p->otherinfo=s->otherinfo ;
//用s替换p
} //第3种情况用方案2处理
if (s->Lchild!=NULL) q=s->Lchild ; //若s,即p只有左子树
else q=s->Rchild ;
//第2,3种情况归一处理
if (f==NULL) T=q ; //p为根结点
else if (f->Lchild==s) f->Lchild=q ; //p为左孩子
else f->Rchild=q ;
//p为右孩子
free(s) ;
//删除p
}

时空复杂度分析

若查找成功，则走了一条从根结点到某结点的路径，若查找失败，则走到一棵空的子树时为止。

最坏情况下，其平均查找长度不会超过树的高度。

具有n个结点的二叉树的高度取决于其形态。
由关键字序列 1，2，3，4，5构造而得的二叉排序树，ASL =（1+2+3+4+5）/ 5 = 3
由关键字序列 3，1，2，5，4构造而得的二叉排序树，ASL =（1+2+3+2+3）/ 5 = 2.2

最好情况(为满二叉树）
n+1
ASL=—log2(n+1)-1 = O(log2 n)
n
最坏情况(为单枝树):
ASL=(1+2+…+n)/n=(n+1)/2
平均值:
ASL≈O(log2 n)

平衡二叉排序树

定义

平衡二叉树：平衡二叉树，又称AVL树。它或者是一颗空树，或者是具有以下性质的二叉树：它的左子树和右子树都是平衡树，且左子树和右子树的深度之差的绝对值不超过1.

平衡因子:又称BF，定义为该节点的左子树的深度减去它的右子树深度。则平衡二叉树的所有节点的平衡因子只可能是-1、0、1.

只要二叉树上有一个结点的平衡因子BF绝对值大于1，那么二叉树就是不平衡的

如下便是几个二叉树中各结点的平衡因子：

平衡二叉树

我们希望由任何初始序列构成的二叉排序树都是AVL树。因为AVL树上任何结点的左右子树的深度之差都不超过1.则可以证明如此的话他的平均查找长度和 $log{n}$ 同数量级。

以下再放一张图对比一下平衡二叉树、二叉排序树、平衡二叉排序树的区别：

三种树区别

构造平衡二叉排序树

基本原理就是按照二叉排序树的思路进行排序构造，遇到某个结点的平衡因子绝对值大于1的情况的时候，就进行一定的操作将二叉树变为平衡的，一步一步按照这样的方法最后构造成功。

构造过程中调整二叉树的操作可以归纳为以下4种情况：

我们先假设整个二叉树在插入新结点之后所得到的不平衡的最小子树的根节点指针为a，a平衡因子绝对值此时大于1.此时a是离结点最近的平衡因子绝对值大于1的祖先节点

LL型（单向右旋平衡处理）

此时向a结点的左子树根节点的左子树上插入结点，使得左子树的高度过高，这样一来我们需要将a左子树的根节点替代a的位置，原a左子树根节点的右子树变为a结点的左子树。这样一来就有重新回到平衡相当于向右做了一次顺时针旋转操作。图例如下：

LL型

LR型（双向旋转先右后左）

此时由于a结点的左子树根节点（这里暂称b)的右子树（假设根节点为c）插入了新节点，使得整体出现了不平衡，我们此时需要用c取代a的位置，然后c的原左子树作为b的右子树，c的现左子树变为b为根的树，c的原右子树变为a的左子树，c的现右子树变为a为根的树。相当于先左旋处理一次然后右旋处理了一次。图解如下：

LR型

RR型（单向左旋平衡处理）

与LL型比较类似，这次是a结点的右子树的的根节点的右子树上插入了新节点后发生了不平衡的情况。此时解决方法是使用a的右子树根节点移到a的位置，并且将a的原右子树的左子树变为a的右子树。相当于进行了一次向左的逆时针旋转操作。图解如下：

RR型

RL型（双向先左旋后右旋）

这个和LR型比较类似，实际上这四种类型是两两对称的。这个指的是a的右子树根节点（设为b）的左子树（设其根节点为c）插入了新节点导致了不平衡现象。此时我们需要将c代替a的位置，c的原左子树作为a的现右子树，c的现左子树为a为根节点的树，c的原右子树为b的现左子树，c的现右子树为b为根节点的树。图解同样如下：

RL型

以下举例子说明一下：

以序列（13，24，37，90，53）为例，首先空树是一个平衡的，然后把13加进去，同样平衡，再将24加进去同样平衡。接下来加进去37，此时就变为RR型，我们需要左旋，由于24没有左子树，所以只需让13为根的树作为24的左子树，不需要往13右孩子加东西。接下来90，保持平衡。直到53，变为RR型，此时37的平衡因子绝对值为-2，左旋后得到最终的平衡二叉排序树。如下：

平衡二叉排序树最终构造