二叉搜索树、平衡二叉树
二叉搜索树
由查找问题：针对静态查找和动态查找，数据应如何组织
- 需要特定的数据读取、插入和删除方式
二叉搜索树的定义
二叉搜索树(BST,Binary Search Tree)，也称二叉排序树或二叉查找树
一棵二叉搜索树，可以为空；如果不为空，满足以下性质：
- 非空左子树的所有键值小于其根结点的键值
- 非空右子树的所有键值大于其根结点的键值
- 左、右子树都是二叉搜索树
二叉搜索树操作集中的特殊函数
Position Find(ElementType X,BinTree BST):从二叉搜索树BST中查找元素X，返回其所在结点的地址;
Position FindMin(BinTree BST):从二叉搜索树BST中查找返回最小元素所在结点的地址;
Position FindMax(BinTree BST):从二叉搜索树BST中查找返回最大元素所在结点的地址;
BinTree Insert(ElementType X,BinTree BST):向二叉搜索树BST中插入元素X;
BinTree Delete(ElementType X,BinTree BST):从二叉搜索树BST中删除元素X;二叉搜索树操作集
二叉搜索树的查找操作：Find
- 查找从根结点开始，如果树为空，返回NULL
- 若搜索树非空，则根结点关键字和X进行比较，并进行不同的操作
- 若X小于根结点的键值，只需在左子树中继续搜索
- 若X大于根结点的键值，在右子树中继续搜索
- 若两者比较结果相等，搜索完成，返回指向此结点的指针
- 查找的效率取决于树的深度
Find操作的递归算法
Position Find(ElementType X,BinTree BST) //尾递归：在程序要返回的时候递归，从遍历的角度上讲都可以用循环实现
{
if(!BST)return NULL;
if(X<BST->Data)return Find(X,BST->Left); //在左子树中继续查找
else if(X>BST->Data)return Find(X,BST->Right); //在右子树中继续查找
else return BST; //查找成功，返回找到结点的地址
} Find操作的非递归算法
Position Find(ElementType X,BinTree BST)
{
if(!BST)return NULL;
while(BST)
{
if(X<BST->Data)BST=BST->Left;
else if(X>BST->Data)BST=BST->Right;
else return BST;
}
return NULL;
}二叉搜索树查找最大和最小元素操作：FindMin，FindMax
- 最大元素一定是在数的最右分支的端结点上
- 最小元素一定是在数的最左分支的端结点上
FindMin操作的递归算法/FindMax操作的非递归算法(二者原理完全相同，可互相转化)
Position FindMin(BinTree BST)
{
if(!BST)return NULL; //空二叉搜索树，返回NULL
else if(!BST->Left)return BST; //找到最左叶结点并返回
else return FindMin(BST->Left); //沿左分支继续查找
}
Position FindMax(BinTree BST)
{
while(BST->Right)BST=BST->Right; //沿右分支继续查找，直到最右结点
return BST;
}二叉搜索树的插入操作：Insert
关键是要找到元素应该插入的位置，可以采用与Find类似的方法
Insert操作的递归算法(非递归算法同理)
BinTree Insert(ElementType X,BinTree BST)
{
if(!BST) //若结点为空，生成并返回一个结点的二叉搜索树
{ //此时存在一个问题：生成的新结点并没有与树连接起来
BST=(BinTree)malloc(sizeof(struct TreeNode));
BST->Data=X;
BST->Left=BST->Right=NULL;
}
else //开始找要插入元素的位置
{
if(X<BST->Data)BST->Left=Insert(X,BST->Left); //递归插入左子树
else if(X>BST->Data)BST->Right=Insert(X,BST->Right); //递归插入右子树
//else X已经存在，什么都不做 //注意要把插入操作后的子树根结点返回给相应的子树
}
return BST; //每次递归结果是返回BST，目的是在最后一次返回上一层的时候能够将插入结点与二叉搜索树连接起来
}二叉搜索树的删除操作：Delete
需要考虑三种情况：
- 要删除的是叶结点：直接删除，并修改其父结点指针–置为NULL
- 要删除的结点只有一个子树：将其父结点的指针指向要删除结点的孩子结点
- 要删除的结点有左、右两棵子树：另一结点替代被删除的结点：右子树的最小元素或者左子树的最大元素(这两种结点都不可能有两个孩子)
Delete操作的递归算法
BinTree Delete(ElementType X,BinTree BST)
{
Position Tmp;
if(!BST)printf("要删除的元素没有找到");
else if(X<BST->Data)BST->Left=Delete(X,BST->Left); //左子树递归删除
else if(X>BST->Data)BST->Right=Delete(X,BST->Right); //右子树递归删除
else{ //找到要删除的结点
if(BST->Left&&BST->Right){ //被删除结点有左右两个子结点
Tmp=FindMin(BST->Right); //在右子树中找最小元素填充删除结点
//此处也可以用左子树最大元素填充 Tmp=FindMax(BST->Left);
BST->Data=Tmp->Data;
BST->Right=Delete(BST->Data,BST->Right); //在删除结点的右子树中删除最小元素
//相应地需要在左子树中删除 BST->Left=Delete(BST->Data,BST->Left)
}else{ //被删除元素有一个或无子结点
Tmp=BST;
if(!BST->Left)BST=BST->Right; //有右孩子或无子结点
else if(!BST->Right)BST=BST->Left; //有左孩子或无子结点
free(Tmp);
}
}
return BST;
}二叉搜索树操作演示
/* 以下演示程序均来自浙江大学mooc数据结构 */
#include<cstdio>
#include<cstdlib>
typedef struct TreeNode *BinTree;
typedef int ElementType;
typedef BinTree Position;
struct TreeNode
{
ElementType Data;
BinTree Left;
BinTree Right;
};
Position FindMin( BinTree );
BinTree Insert( BinTree BST, ElementType X )
{
if( !BST ){ /* 若原树为空，生成并返回一个结点的二叉搜索树 */
BST = (BinTree)malloc(sizeof(struct TreeNode));
BST->Data = X;
BST->Left = BST->Right = NULL;
}
else { /* 开始找要插入元素的位置 */
if( X < BST->Data )
BST->Left = Insert( BST->Left, X ); /*递归插入左子树*/
else if( X > BST->Data )
BST->Right = Insert( BST->Right, X ); /*递归插入右子树*/
/* else X已经存在，什么都不做 */
}
return BST;
}
BinTree Delete( BinTree BST, ElementType X )
{
Position Tmp;
if( !BST )
printf("要删除的元素未找到");
else {
if( X < BST->Data )
BST->Left = Delete( BST->Left, X ); /* 从左子树递归删除 */
else if( X > BST->Data )
BST->Right = Delete( BST->Right, X ); /* 从右子树递归删除 */
else { /* BST就是要删除的结点 */
/* 如果被删除结点有左右两个子结点 */
if( BST->Left && BST->Right ) {
/* 从右子树中找最小的元素填充删除结点 */
Tmp = FindMin( BST->Right );
BST->Data = Tmp->Data;
/* 从右子树中删除最小元素 */
BST->Right = Delete( BST->Right, BST->Data );
}
else { /* 被删除结点有一个或无子结点 */
Tmp = BST;
if( !BST->Left ) /* 只有右孩子或无子结点 */
BST = BST->Right;
else /* 只有左孩子 */
BST = BST->Left;
free( Tmp );
}
}
}
return BST;
}平衡二叉树
问题：二叉搜索树结点的插入顺序不同，将导致不同的深度和平均查找长度(次数)ASL
- ASL每个结点的左右子树越均衡，查找效率越高(高度被压缩)
平衡二叉树的定义
平衡二叉树(Balanced Binary Tree)(AVL树)
- 空树，或者任一结点左、右子树高度差的绝对值不超过1，即
- 平衡二叉树通过对二叉树结构的约束，保证二叉搜索树的动态查找效率达到相当于二分查找法的效果
- “平衡因子”(Balance Factor，简称)：，其中和分别为T的左右子树的高度
平衡二叉树高度
平衡二叉树的高度是否能达到，证明过程:
-
设是给定高度为h的平衡二叉树的最少结点数，此时:
-
将平衡二叉树分为左子树、右子树和根三部分，此时满足，与斐波那契数列的递推式类似
-
斐波那契数列的规则：
-
对比最少结点数与斐波那契数列数列的规律
h 0 1 2 3 4 5 6 7 8 9 1 2 4 7 12 20 33 54 88 …… 1 1 2 3 5 8 13 21 34 …… -
可以发现从n=2开始
- 比大1，比大1，因此
- 由归纳法可知
- 由
-
因此，在给定结点数为n的情况下，AVL树的高度为 (n不同底的对数之间相差的一个常数)
- 注意以上给出的是最少结点，最多结点的情况是满二叉树
平衡二叉树的调整
平衡二叉树的调整：向二叉查找树中插入新结点时可能会使树不再平衡，此时需要进行调整
不平衡：平衡因子绝对值>1 (造成不平衡至少涉及到三层结点)
- 其中离插入结点最近且平衡因子绝对值超过1的祖先结点，以该结点为根的子树称为最小不平衡树
- 将重新平衡的范围局限于子树即可(将平衡被破坏的子树重新平衡，则整棵树都会平衡)
- 造成不平衡的结点插在子树的哪边都一样，关键是看插入子树的根结点相对其祖先结点所处的子树
- LL型：初始状态平衡因子=1，在左子树根结点的左子树上再插入结点(LL插入)，此时需要进行一次LL旋转(左单旋)操作
- 如：在A的左子树根结点B的左子树插入结点(LL插入)，旋转后B取代A成为整棵树根结点
- B的左子树不变，右子树根结点变为A
- A的右子树不变，左子树为原来B的右子树，
- LR型：初始状态平衡因子=1，在左子树根结点的右子树上再插入结点(LR插入)，此时需要进行LR二次旋转(左右双旋)操作
- 如：在A的左子树根结点B的右子树插入结点(LR插入)，经过两次单旋后B的原来右子树根结点C成为整棵树根结点
- 先对B和C进行一次右旋后，C成为A左子树根结点，B为C左子树的根结点，B的右子树根结点为C原来左子树的根结点
- 然后对A和C进行一次左旋，C成为整棵树的根结点，A为C右子树的根结点，A的左子树根结点为C原来右子树的根结点
- RR型：初始状态平衡因子=-1，在右子树根结点的右子树上再插入结点(RR插入)，此时需要进行一次RR旋转(右单旋)操作
- RL型：初始状态平衡因子=-1，在右子树根结点的左子树上再插入结点(RL插入)，此时需要进行RL二次旋转(右左双旋)操作
- 综上，LL型与RR型对称，LR型和RL型对称，可以由中序遍历所得关键字序列自小到大有序来证明平衡调整的正确
- 另外，平衡二叉树的高度在插入结点前和插入结点并平衡调整之后是相同的
- 注意，插入元素即便不需要调整结构也可能需要重新计算一些平衡因子
平衡二叉树的调整操作演示
#include<cstdlib>
typedef int ElementType;
typedef struct AVLNode *Position;
typedef Position AVLTree; /* AVL树类型 */
struct AVLNode{
ElementType Data; /* 结点数据 */
AVLTree Left; /* 指向左子树 */
AVLTree Right; /* 指向右子树 */
int Height; /* 树高 */
};
int Max ( int a, int b )
{
return a > b ? a : b;
}
int GetHeight( AVLTree A )
{
int lheight = 0,rheight = 0;
if( A )
{
lheight = GetHeight( A->Left );
rheight = GetHeight( A->Right );
return Max( lheight, rheight ) + 1;
}
return 0;
}
AVLTree SingleLeftRotation ( AVLTree A )
{ /* 注意：A必须有一个左子结点B */
/* 将A与B做左单旋，更新A与B的高度，返回新的根结点B */
AVLTree B = A->Left;
A->Left = B->Right;
B->Right = A;
A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;
B->Height = Max( GetHeight(B->Left), A->Height ) + 1;
return B;
}
AVLTree SingleRightRotation ( AVLTree A );
AVLTree DoubleLeftRightRotation ( AVLTree A )
{ /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C */
/* 将A、B与C做两次单旋，返回新的根结点C */
/* 将B与C做右单旋，C被返回 */
A->Left = SingleRightRotation(A->Left);
/* 将A与C做左单旋，C被返回 */
return SingleLeftRotation(A);
}
/*************************************/
/* 对称的右单旋与右-左双旋请自己实现 */
/*************************************/
AVLTree SingleRightRotation ( AVLTree A )
{
AVLTree B = A->Right;
A->Right = B->Left;
B->Left = A;
A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;
B->Height = Max( GetHeight(B->Right), A->Height ) + 1;
return B;
}
AVLTree DoubleRightLeftRotation ( AVLTree A )
{
A->Right = SingleLeftRotation(A->Right);
return SingleRightRotation(A);
}
AVLTree Insert( AVLTree T, ElementType X )
{ /* 将X插入AVL树T中，并且返回调整后的AVL树 */
if ( !T ) { /* 若插入空树，则新建包含一个结点的树 */
T = (AVLTree)malloc(sizeof(struct AVLNode));
T->Data = X;
T->Height = 0;
T->Left = T->Right = NULL;
} /* if (插入空树) 结束 */
else if ( X < T->Data ) {
/* 插入T的左子树 */
T->Left = Insert( T->Left, X);
/* 如果需要左旋 */
if ( GetHeight(T->Left)-GetHeight(T->Right) == 2 ) { //进入左子树后先搜索
if ( X < T->Left->Data )
T = SingleLeftRotation(T); /* 左单旋 */
else
T = DoubleLeftRightRotation(T); /* 左-右双旋 */
}
} /* else if (插入左子树) 结束 */
else if ( X > T->Data ) {
/* 插入T的右子树 */
T->Right = Insert( T->Right, X );
/* 如果需要右旋 */
if ( GetHeight(T->Left)-GetHeight(T->Right) == -2 ) { //同理，进入右子树后先搜索
if ( X > T->Right->Data )
T = SingleRightRotation(T); /* 右单旋 */
else
T = DoubleRightLeftRotation(T); /* 右-左双旋 */
}
} /* else if (插入右子树) 结束 */
/* else X == T->Data，无须插入 */
/* 别忘了更新树高 */
T->Height = Max( GetHeight(T->Left), GetHeight(T->Right) ) + 1;
return T;
}本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 hetumessi's Blog！
相关推荐
评论
ValineGitalk
