当前位置：文档之家 › 动态查找树之平衡二叉树(Balanced Binary Tree,AVL树)

动态查找树之平衡二叉树(Balanced Binary Tree,AVL树)

  • 格式：docx
  • 大小：743.75 KB
  • 文档页数：35

动态查找树之平衡二叉树（Balanced Binary Tree，AVL树） 一、平衡二叉树的概念 平衡二叉树(Balanced binary tree)是由阿德尔森-维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又称为AVL树。

定义：平衡二叉树或为空树,或为如下性质的二叉排序树: （1）左右子树深度之差的绝对值不超过1; （2）左右子树仍然为平衡二叉树. 平衡因子BF=左子树深度－右子树深度. 平衡二叉树每个结点的平衡因子只能是1，0，-1。若其绝对值超过1，则该二叉排序树就是不平衡的。 如图所示为平衡树和非平衡树示意图： 二、平衡二叉树算法思想 若 向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的 链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树。

失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于1的结点作为根的子树。假设用A表示失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列四种情况。

（1）LL型平衡旋转法 由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行一次顺时针旋转操作。 即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。 （2）RR型平衡旋转法 由于在A的右孩子C 的右子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行一次逆时针旋转操作。即将A的右孩子C向左上旋转代替A作为根结点，A向左下旋转成为C的左子树的根结点。而原来C的左子树则变成A的右子树。 （3）LR型平衡旋转法

由于在A的左孩子B的右子数上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行两次旋转操作（先逆时针，后顺时针）。即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。即先使之成为LL型，再按LL型处理。 如图中所示，即先将圆圈部分先调整为平衡树，然后将其以根结点接到A的左子树上，此时成为LL型，再按LL型处理成平

衡型。

（4）RL型平衡旋转法 由于在A的右孩子C的左子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行两次旋转操作（先顺时针，后逆时针），即先将A结点的右孩子C的左子树的根结点D向右上旋转提升到C结点的位置，然后再把该D结点向左上旋转提升到A结点的位置。即先使之成为RR型，再按RR型处理。 如图中所示，即先将圆圈部分先调整为平衡树，然后将其以根结点接到A的左子树上，此时成为RR型，再按RR型处理成平衡型。 平衡化靠的是旋转。参与旋转的是3个节点（其中一个可能是外部节点NULL），旋转就是把这3个节点转个位置。注意的是，左旋的时候p->right一定不为空，右旋的时候p->left一定不为空，这是显而易见的。

如果从空树开始建立，并时刻保持平衡，那么不平衡只会发生在插入删除操作上，而不平衡的标志就是出现bf == 2或者 bf == -2的节点。 三、二叉排序数的操作及C语言描述 插入删除是互为镜像的操作。我们可以采用前面对二叉排序树的删除操作来进行。然后，在删除掉结点后，再对平衡树进行平衡化处理。删除之所以删除操作需要的平衡化可能比插入时次数多，就是因为平衡化不会增加子树的高度，但是可能会减少子树的高度，在有有可能使树增高的插入操作中，一次平衡化能抵消掉增高；在有可能使树减低的删除操作中，平衡化可能会带来祖先节点的不平衡。

四、二叉排序数的C语言实现 #include "stdio.h" #include "stdlib.h" #include "string.h" #define LH +1 //左高 #define EH 0 //等高 #define RH -1 //右高 #define TRUE 1 #define FALSE 1 #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)< (b)) #define LQ(a,b) ((a)<=(b)) #define BT(a,b) ((a)> (b)) typedef int KeyType; typedef int info; typedef int Boolean; typedef struct ElemType { KeyType key; //info otherinfo; }; typedef struct BSTNode { ElemType data; int bf; BSTNode *lchild,*rchild; // 左右孩子指针 }BSTNode,*BSTree;

void R_Rotate(BSTree &p) {//右旋 BSTree lc; lc=p->lchild; p->lchild=lc->rchild; lc->rchild=p; p=lc; //p指向新的根结点 }//R_Rotate

void L_Rotate(BSTree &p) {//左旋 BSTree rc; rc=p->rchild; p->rchild=rc->lchild; rc->lchild=p; p=rc; //p指向新的根结点 }//L_Rotate

void LeftBalance(BSTree &T) {//作平衡旋转处理 BSTree lc,rd; lc=T->lchild; switch(lc->bf) { case LH: T->bf=lc->bf=EH; R_Rotate(T); break; case RH: rd=lc->rchild; switch(rd->bf) { case LH:T->bf=RH;lc->bf=EH;break; case EH:T->bf=lc->bf=EH; break; case RH:T->bf=EH;lc->bf=LH;break; }//switch rd->bf=EH; L_Rotate(T->lchild); R_Rotate(T); }//switch }//LeftBalance

void RightBalance(BSTree &T) {//作平衡旋转处理 BSTree rc,ld; rc=T->rchild; switch(rc->bf) { case RH: T->bf=rc->bf=EH; L_Rotate(T); break; case LH: ld=rc->lchild; switch(ld->bf) { case LH:T->bf=LH;rc->bf=EH;break; case EH:T->bf=rc->bf=EH; break; case RH:T->bf=EH;rc->bf=RH;break; }//switch ld->bf=EH; R_Rotate(T->rchild); L_Rotate(T); }//switch }//RightBalance

int InsertAVL(BSTree &T,ElemType e,int &taller) { // 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 // 数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树 // 失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否 if(!T) { // 插入新结点，树“长高”，置taller为TRUE T=(BSTree)malloc(sizeof(BSTNode)); T->data=e; T->lchild=T->rchild=NULL; T->bf=EH; taller=TRUE; } else { if EQ(e.key,T->data.key) { // 树中已存在和e有相同关键字的结点则不再插入 taller=FALSE; return FALSE; } if LT(e.key,T->data.key) { // 应继续在*T的左子树中进行搜索 if(!InsertAVL(T->lchild,e,taller)) // 未插入 return FALSE; if(taller) // 已插入到*T的左子树中且左子树“长高” switch(T->bf) // 检查*T的平衡度 { case LH: // 原本左子树比右子树高，需要作左平衡处理 LeftBalance(T); taller=FALSE; break; case EH: // 原本左、右子树等高，现因左子树增高而使树增高 T->bf=LH; taller=TRUE; break; case RH: T->bf=EH; // 原本右子树比左子树高，现左、右子树等高 taller=FALSE; } } else { // 应继续在*T的右子树中进行搜索 if(!InsertAVL(T->rchild,e,taller)) // 未插入 return FALSE; if(taller) // 已插入到T的右子树且右子树“长高” switch(T->bf) // 检查T的平衡度 { case LH: T->bf=EH; // 原本左子树比右子树高，现左、右子树等高 taller=FALSE; break; case EH: // 原本左、右子树等高，现因右子树增高而使树增高 T->bf=RH; taller=TRUE; break; case RH: // 原本右子树比左子树高，需要作右平衡处理 RightBalance(T); taller=FALSE; }

合集下载

平衡二叉树 平衡因子

平衡二叉树 平衡因子

平衡二叉树平衡因子
平衡二叉树，又称AVL树，是一种自平衡二叉搜索树。

它具有以下特点：任意节点的左右子树高度差不超过1。

为了实现这个特点，需要在插入和删除节点时进行相关操作，以保持树的平衡。

平衡因子是平衡二叉树中每个节点的一个属性，它表示该节点的左右子树高度差。

平衡因子可以为-1、0和1。

如果平衡因子为-1，表示该节点的左子树高度比右子树高1；如果平衡因子为0，表示该节点的左右子树高度相等；如果平衡因子为1，表示该节点的右子树高度比左子树高1。

在平衡二叉树中，任意节点的平衡因子必须在-1到1之间，否则该节点就不符合平衡条件，需要进行相应的平衡操作。

平衡因子的计算方法是该节点的右子树高度减去左子树高度。

例如，在下面这棵平衡二叉树中，节点7的平衡因子为1，节点6的平衡因子为-1。

```
5
/
3 7
/ /
1 4 6 8
```
在插入和删除节点时，需要根据节点的平衡因子来判断树是否需要进行平衡操作。

如果某个节点的平衡因子不符合要求，需要进行旋
转操作来调整节点的位置，以保持树的平衡。

具体的旋转操作包括左旋、右旋、左右旋和右左旋，可以根据节点的平衡因子和子节点的平衡因子来确定需要进行的操作。

维护平衡二叉树需要付出一定的时间和空间代价，但它的优点是可以保证树的查找、插入和删除操作的时间复杂度都是O(log n)，比普通的二叉搜索树更加高效。

因此，在需要频繁进行这些操作的场景下，平衡二叉树是一种非常有用的数据结构。

平衡二叉树

平衡二叉树

1 1 0 0 0 1 0 0 (a) 平衡二叉树 -1 -1 1
2 -1 0 0 0
-1
-2 0 0 1
0 0
1
(b) 不平衡二叉树 图9.6 平衡与不平衡二叉树及结点的平衡因子
平衡二叉树是二叉排序树的另一种形式. 平衡二叉树 我们希望由任何初始序列构成的二叉排序 树都是平衡二叉树 平衡二叉树.因为平衡二叉树 平衡二叉树上任 平衡二叉树 平衡二叉树 1 何结点的左右子树的深度之差都不超过1, 则可以证明它的深度和logN是同数量级的 (其中N是结点的个数).由此,它的平 均查找长度也和logN同数量级.
typedef structBSTNode { ElemType data; int bf; //结点的平衡因子 结点的平衡因子 struct BSTNode *lchild, *rchild; //左,右孩子指针 左 } BSTNode, * BSTree;
算法9.7如下: 算法 如下: 如下 void R_Rotate (BSTree &p) { //对以 为根的二叉排序树作右旋处理,处理之后p指向新的树根结点, 对以*p为根的二叉排序树作右旋处理,处理之后 指向新的树根结点, 对以 为根的二叉排序树作右旋处理 指向新的树根结点 //即旋转处理之前的左子树的根结点 即旋转处理之前的左子树的根结点 lc = p->lchild; //lc指向的 的左子树根结点 指向的*p的左子树根结点 - 指向的 p->lchild = lc->rchild; //lc的右子树挂接为 的左子树 的右子树挂接为*p的左子树 - - 的右子树挂接为 lc->rchild = p; - p = lc; //p指向新的根结点 指向新的根结点 } // R_Rotate
java数据结构与算法之平衡二叉树(AVL树)的设计与实现分析

java数据结构与算法之平衡二叉树(AVL树)的设计与实现分析

java数据结构与算法之平衡二叉树(A VL树)的设计与实现普通二叉查找树的问题在开篇，我们提到过，普通二叉树（二叉查找树）在操作的时间复杂度上不一定遵循O(㏒n)，也有可能是O(n)，这是为什么呢？在上一篇中，我们明明插入都按照一定规则比较的呀，其实那是因为我们在上篇测试时执行了随机插入的操作，如果此时利用上篇实现的二叉搜索树将一段已排序好的数据一个个插入后，就会发现如下情况了：从图中我们可以发现，把已排序的1-9数据进行正序和倒序插入后，树的结构已变成单向左子树或者右子树了，如果我们在往里插入已排序的数据，那么单向左子树或者右子树越来越长，此时已跟单链表没有什么区别了，因此对此结构的操作时间复杂度自然就由O(㏒n)变成O(n)了，这也就是普通二叉查找树不是严格意义上O(㏒n)的原因。

那么该如何解决这个问题呢？事实上一种解决的办法就是要有一个称为平衡的附加结构条件即：任何结点的深度不得过深，而这种数据结构就是我们本篇要分析的平衡二叉树（AVL），它本身也是一种二叉查找树，只不过不会出现前面我们分析的情形罢了，接下来我们就来分析一下这棵平衡二叉树。

平衡二叉树的定义通过上面的分析，我们明白的普通二叉查找树的不足，也知道了如何去解决这个缺点，即构建树时要求任何结点的深度不得过深（子树高度相差不超过1），而最终这棵树就是平衡二叉树（BalancedBinaryTree），它是G.M.Adelson-Velsky和ndis在1962年在论文中发表的，因此又叫AVL树。

这里我们还需要明确一个概念，AVL树只是实现平衡二叉树的一种方法，它还有很多的其他实现方法如红黑树、替罪羊树、Treap、伸展树等，后面我们还会分析其他树的实现。

ok~，接着来了解一下AVL树的特性：一棵AVL树是其每个结点的左子树和右子树的高度最多相差1的二叉查找树(空树的高度为-1)，这个差值也称为平衡因子（其取值可以是1，0，-1，平衡因子是某个结点左右子树层数的差值，有的书上定义是左边减去右边，有的书上定义是右边减去左边，这样可能会有正负的区别，但是这个并不影响我们对平衡二叉树的讨论）。

二叉树

二叉树

平衡树——特点：所有结点左右子树深度差≤1排序树——特点：所有结点―左小右大字典树——由字符串构成的二叉排序树判定树——特点：分支查找树（例如12个球如何只称3次便分出轻重）带权树——特点：路径带权值（例如长度）最优树——是带权路径长度最短的树，又称Huffman树，用途之一是通信中的压缩编码。

1.1 二叉排序树：或是一棵空树；或者是具有如下性质的非空二叉树：（1）若左子树不为空，左子树的所有结点的值均小于根的值；（2）若右子树不为空，右子树的所有结点均大于根的值；（3）它的左右子树也分别为二叉排序树。

例：二叉排序树如图9.7：二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。

中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。

每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。

搜索,插入,删除的复杂度等于树高，期望O(logn),最坏O(n)(数列有序,树退化成线性表).虽然二叉排序树的最坏效率是O(n),但它支持动态查询,且有很多改进版的二叉排序树可以使树高为O(logn),如SBT,AVL,红黑树等.故不失为一种好的动态排序方法.2.2 二叉排序树b中查找在二叉排序树b中查找x的过程为：1. 若b是空树，则搜索失败，否则：2. 若x等于b的根节点的数据域之值，则查找成功；否则：3. 若x小于b的根节点的数据域之值，则搜索左子树；否则：4. 查找右子树。

[cpp]view plaincopyprint?1.Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p){2. //在根指针T所指二叉排序樹中递归地查找其关键字等于key的数据元素，若查找成功，3. //则指针p指向该数据元素节点，并返回TRUE，否则指针P指向查找路径上访问的4. //最好一个节点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL5. if(!T){ p=f; return FALSE;} //查找不成功6. else if EQ(key, T->data.key) {P=T; return TRUE;} //查找成功7. else if LT(key,T->data.key)8. return SearchBST(T->lchild, key, T, p); //在左子树继续查找9. else return SearchBST(T->rchild, key, T, p); //在右子树继续查找10.}2.3 在二叉排序树插入结点的算法向一个二叉排序树b中插入一个结点s的算法，过程为：1. 若b是空树，则将s所指结点作为根结点插入，否则：2. 若s->data等于b的根结点的数据域之值，则返回，否则：3. 若s->data小于b的根结点的数据域之值，则把s所指结点插入到左子树中，否则：4. 把s所指结点插入到右子树中。