构建一棵平衡二叉树

 · 2022-8-4 · 次阅读

本篇从代码和图形两部分，深层次理解平衡二叉树的构造。

基本概念

首先给出二叉树节点的定义，以下均使用该处定义的节点类型：

typedef struct avlnode {
	int data;					// 数据域
	int height;					// 以该节点为根的树的高度
	struct avlnode * parent;	 // 父节点指针
	struct avlnode * lchild;	 // 左孩子指针
	struct avlnode * rchild;	 // 右孩子指针
}Node, *AVLNode;

平衡二叉树是一种特殊的二叉排序树。既然是二叉排序树，就必须满足二叉排序树的性质：

所有左子树节点的值 < 根节点的值 < 所有右子树节点的值

对于一棵二叉排序树，我们在插入的时候只需要简单的寻找其插入位置，然后将其插入即可。代码表示如下：

AVLNode pt = AVLTree;
while(pt != NULL) {
    if (pt->data > val) {
        pt = pt->lchild;
    } else {
        pt = pt->rchild;
    }
}

image.png

根据此代码，pt最后停留的位置，就是新节点应该插入的位置。实际在写代码的时候肯定不会这样简单，因为单单有pt的位置还不能插入一个节点，需要有pt的父节点和插入节点相对于父节点的路径。这里不再赘述。

平衡二叉树和二叉树相比，引入了“平衡因子”这个概念，用来表示左右子树的高度之差。即：

平衡因子 = 左子树高度 - 右子树高度

// 计算平衡因子
int CalcBF(AVLNode node)
{
	if (node == NULL) {
		return 0;							// 空节点的平衡因子为0
	}
	int bf = 0;
	if (node->lchild != NULL) {
		bf = bf + node->lchild->height;
	}
	if (node->rchild != NULL) {
		bf = bf - node->rchild->height;
	}
    // bf = 0 + 左子树高度 - 右子树高度 = 左子树高度 - 右子树高度，这样做能尽量减少判断次数，
	return bf;
}

这里没加绝对值，表示平衡因子有正有负。事实上，平衡因子的正负反映了左右子树的高低关系：为正，表示左子树高于右子树；为负，表示右子树高于左子树。

基本操作–左旋和右旋

平衡二叉树规定，任意节点的平衡因子的绝对值不能超过1（即只能有0和1两种可能）。超过1就需要进行调整。调整只针对最小不平衡子树。以下介绍调整的两种方式：左旋，右旋。

左旋

左旋是使用右子树替代根的一种做法。如图所示：

image

在代码实现时，分为以下三步：

  1. 使用原根的右子树代替根的位置

    image

  2. 将新根的左子树（如果存在）挂在原根的右子树上

    image

  3. 将原根挂在新根的左子树上

    image

以上步骤不可颠倒。完成之后，即可在实现原来根的右子树替换根的同时，不破坏左子树小于根小于右子树的原则。

以下是代码实现，代码中有详细的注解。

// 左旋
void lRotate(AVLNode & node)
{
	AVLNode oldroot = node;
	AVLNode newroot = node->rchild;
	AVLNode parent = node->parent;
	
	// 使用newroot替代原来位置
	if (parent != NULL) {
		if (parent->lchild == oldroot) {
			parent->lchild = newroot;
		} else {
			parent->rchild = newroot;
		}
	}
	newroot->parent = parent;
	
	// 将newroot的左子树挂载到oldroot的右子树
	oldroot->rchild = newroot->lchild;
	if (newroot->lchild != NULL) {				// 一定要加以判断，否则可能会产生访问错误
		newroot->lchild->parent = oldroot;
	}

	// 将oldroot挂载到newroot的右子树上
	newroot->lchild = oldroot;
	oldroot->parent = newroot;
	// 这一步是防止传进来的参数本身就是根节点的情况
	// 如果传进来的参数是根节点，就修改根节点指针指向的值，因为根节点没有父节点，无法通过修改父子节点的关系进行修改。
	node = newroot;
}

右旋

右旋和左旋类似，是使用左子树替换根节点，同时保持二叉排序树特性不变的操作。直接上代码


// 右旋，这里使用了引用类型作为参数，方便修改
void rRotate(AVLNode & node)
{
	AVLNode oldroot = node;
	AVLNode newroot = node->lchild;
	AVLNode parent = node->parent;
	
	// 使用newroot替代原来位置
	if (parent != NULL) {
		if (parent->lchild == oldroot) {
			parent->lchild = newroot;
		} else {
			parent->rchild = newroot;
		}
	}
	newroot->parent = parent;
	
	// 将newroot的右子树挂载到oldroot的左子树
	oldroot->lchild = newroot->rchild;
	if (newroot->rchild != NULL) {
		newroot->rchild->parent = oldroot;
	}

	// 将oldroot挂载到newroot的右子树上
	newroot->rchild = oldroot;
	oldroot->parent = newroot;
	node = newroot;													
}

四种不平衡类型

有四种可能出现的导致不平衡的情形，分别是LL，RR，LR和RL（直接使用网图，懒得画了）：

image

这四种类型是根据新添加的节点相对于最小不平衡子树的位置而定的。例如，新添加的节点相对于最小不平衡子树的根节点，在左子树的右子树里，则为LR型。

LL型和RR型

LL型和RR型相对简单，只需要进行右旋和左旋即可，如图：

image

image-20220805140239384

LR型和RL型

这两种相对比较复杂，需要两步操作才能降低平衡因子。其核心思想是用最下面的节点，经过两次调整，替代原来的根节点，如图：

image

image

代码实现AVL树的生成

# include <stdio.h>
# include <stdlib.h>

typedef struct avlnode {
	int data;					// 数据域
	int height;					// 相对高度
	struct avlnode * parent;	// 父节点
	struct avlnode * lchild;	// 左孩子
	struct avlnode * rchild;	// 右孩子
}Node, *AVLNode;

// 计算相对高度，这里如果递归，必须使用后序递归，为什么？
void CalcHeight(AVLNode node)
{
	AVLNode pt = node;
	if (pt == NULL) {
		return;
	}
	CalcHeight(pt->lchild);
	CalcHeight(pt->rchild);
	
	int l = 1;
	int r = 1;
	if (node->lchild != NULL) {
		l = node->lchild->height + 1;
	}
	if (node->rchild != NULL) {
		r = node->rchild->height + 1;
	}
	node->height = l > r ? l : r;
}

// 计算平衡因子
int CalcBF(AVLNode node)
{
	if (node == NULL) {
		return 0;
	}
	int bf = 0;
	if (node->lchild != NULL) {
		bf = bf + node->lchild->height;
	}
	if (node->rchild != NULL) {
		bf = bf - node->rchild->height;
	}
	return bf;
}

// 右旋
void rRotate(AVLNode & node)
{
	AVLNode oldroot = node;
	AVLNode newroot = node->lchild;
	AVLNode parent = node->parent;
	
	// 使用newroot替代原来位置
	if (parent != NULL) {
		if (parent->lchild == oldroot) {
			parent->lchild = newroot;
		} else {
			parent->rchild = newroot;
		}
	}
	newroot->parent = parent;
	
	// 将newroot的右子树挂载到oldroot的左子树
	oldroot->lchild = newroot->rchild;
	if (newroot->rchild != NULL) {
		newroot->rchild->parent = oldroot;
	}

	// 将oldroot挂载到newroot的右子树上
	newroot->rchild = oldroot;
	oldroot->parent = newroot;
	node = newroot;													
}

// 左旋
void lRotate(AVLNode & node)
{
	AVLNode oldroot = node;
	AVLNode newroot = node->rchild;
	AVLNode parent = node->parent;
	
	// 使用newroot替代原来位置
	if (parent != NULL) {
		if (parent->lchild == oldroot) {
			parent->lchild = newroot;
		} else {
			parent->rchild = newroot;
		}
	}
	newroot->parent = parent;
	
	// 将newroot的左子树挂载到oldroot的右子树
	oldroot->rchild = newroot->lchild;
	if (newroot->lchild != NULL) {
		newroot->lchild->parent = oldroot;
	}

	// 将oldroot挂载到newroot的右子树上
	newroot->lchild = oldroot;
	oldroot->parent = newroot;
	node = newroot;
}

void InsertNode(AVLNode & AVLTree, int val)
{
	AVLNode pnew = (AVLNode)malloc(sizeof(Node));
	pnew->data = val;
	pnew->lchild = pnew->rchild = pnew->parent = NULL;
	// 如果是空树，将该节点设为根节点，结束
	if (AVLTree == NULL) {
		AVLTree = pnew;
		return;
	}

	// 非空树，先寻找插入的位置
	AVLNode pt = AVLTree;
	AVLNode pp;
	int way = 0;
	while(pt != NULL) {
		pp = pt;
		if (pt->data > val) {
			way = 0;
			pt = pt->lchild;
		} else {
			way = 1;
			pt = pt->rchild;
		}
	}
	pnew->parent = pp;
	if (way == 0) {
		pp->lchild = pnew;
	} else {
		pp->rchild = pnew;
	}
	CalcHeight(AVLTree);
	
	// 尝试找到最小的不平衡子树
	pt = pnew;
	while (pt->parent != NULL) {
		pt = pt->parent;
		if (CalcBF(pt) == 2) {
			if (CalcBF(pt->lchild) == -1) {
				lRotate(pt->lchild);
			}
			if (pt == AVLTree) {
				rRotate(AVLTree);
			} else {
				rRotate(pt);
			}
			break;
		}
		if (CalcBF(pt) == -2) {
			if (CalcBF(pt->rchild) == 1) {
				rRotate(pt->rchild);
			}
			if (pt == AVLTree) {
				lRotate(AVLTree);
			} else {
				lRotate(pt);
			}
			break;
		}
	}
	CalcHeight(AVLTree);

	return;
}


void PrintTree(AVLNode AVLTree)
{
	AVLNode pt = AVLTree;
	if (pt == NULL) {
		return;
	}
	PrintTree(pt->lchild);
	printf("%d %d\n", pt->data, pt->height);
	PrintTree(pt->rchild);
}


int main(void)
{
	AVLNode Tree = NULL;
	int n = 0;
	int i = 0;
	int t = 0;
	scanf("%d", &n);
	for (i=0; i<n; i++) {
		scanf("%d", &t);
		InsertNode(Tree, t);
	}
	PrintTree(Tree);

	return 0;
}

运行结果（上图为程序运行结果，下图为根据输入序列得到的二叉平衡树示意图）：

image-20220805141338110

image.png

赏