当前位置：服务支持 > 软件文章 > 深入解析：AVL树的插入与删除操作

深入解析：AVL树的插入与删除操作

阅读数 1812

概念：平衡二叉树（AVL树）要求任意节点的左右子树高度差不超过1。

插入前的关键认知：插入前整棵树一定是平衡的；插入后若失衡，只需调整最小失衡子树；最小失衡子树在插入前高度差必为1，插入后才变为大于1。

核心操作逻辑：从插入点向上回溯，记录最后一个高度差不为0的节点A，只有A的子树可能失衡。回溯路径上其余节点高度差均为0，说明它们未受影响。

四种插入情况：

左子树的左子树插入（LL）：A的左孩子高度差从0变为1，执行右旋即可恢复平衡。
左子树的右子树插入（LR）：A的左孩子高度差从0变为1，需先对左孩子左旋，再对A右旋（双旋）。
右子树的右子树插入（RR）：A的右孩子高度差从0变为1，执行左旋即可恢复平衡。
右子树的左子树插入（RL）：A的右孩子高度差从0变为1，需先对右孩子右旋，再对A左旋（双旋）。

本质：单侧插入用单旋，跨侧插入用双旋，四种情况覆盖所有场景。

a. LL情况

由于A是最后一个高度差为1的节点，然后在A左孩子的左子树上插入，它只能是这种情况(未插入):

B的左右子树高度一定相同. (因为A是最后一个高度差为一的节点) ,在插入之后导致了这颗子树不平衡:

(其中两个红色任意一个都可以是新插入的节点)

一次右旋即可调整为平衡树：

Untitled

注意观察，在插入之前这个子树的高度是H + 2，此时整颗树是平衡二叉树。

在插入并重新调整之后，这颗子树的高度仍然是H + 2，所以并不会影响整颗树的平衡状态，此时整棵树仍然是平衡二叉树。

b.LR情况

这个就是a情况中往b的右子树上插入，只不过这里我们还需要考虑一下B的右孩子的情况(插入之前):

还是同样的原因，由于A是最后一个左右子树高度差为1的节点，所以B的左右子树高度相同，C的左右子树高度相同。在插入一个新的节点之后变成了这样:

Untitled

(图中新插入的节点为两个红色节点中的任意一个)。此时需要先左旋，转换为1 中的情况:

接着右旋：

Untitled

此时这颗子树就被调整为了平衡二叉树，且它的高度是H+2，与插入之前这颗子树的高度一样。所以在插入之前整棵树是平衡状态，在插入并且调整之后整棵树仍然是平衡状态。

RL与RR情况与上面两种情况类似，这里就不详细说明了。

为什么只需要调整最小失衡子树就行？

在a,与b两种情况中应该容易看出，我们调整的都是最小的那颗失去平衡的树。在插入之前与调整之后这颗子树的高度不变，不会影响整颗树的平衡状态。

删除操作:

如果要删除的节点不是叶子节点，我们找一个叶子节点与要删除的节点交换位置。

现在我们只需要考虑删除叶子节点即可。

删除叶子节点可能会导致某一棵子树平衡状态破坏，注意如果某棵子树的平衡状态破坏，那么调整之后，这颗子树的高度会减1，那么之后还可能会破坏其他子树的平衡状态。所以需要调整以 ”从叶子到根路径上所有节点为根“ 的子树的平衡状态。但是即使破坏了平衡状态，高度差最大不会超过2。

插入操作的一种实现方式：

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>

#define max(a,b) ((a)>(b) ? (a) : (b))

struct AVLTreeNode{
	int m_height;
	int m_val;
	AVLTreeNode*m_left;
	AVLTreeNode*m_right;
	AVLTreeNode*m_parent;
};

int GetTreeHeight(AVLTreeNode* node){
	if (node){
		return node->m_height;
	}
	return 0;
}

void LeftRotate(AVLTreeNode* node){
	assert(node);
	AVLTreeNode*parent = node->m_parent;
	parent->m_right = node->m_left;
	if (parent->m_right)
		parent->m_right->m_parent = parent;
	node->m_left = parent;
	node->m_parent = parent->m_parent;

	if (node->m_parent)
		if (node->m_parent->m_left == parent)
			node->m_parent->m_left = node;
		else
			node->m_parent->m_right = node;

	parent->m_parent = node;
	//
	parent->m_height = 1 + max(GetTreeHeight(parent->m_left), GetTreeHeight(parent->m_right));
	node->m_height = 1 + max(GetTreeHeight(node->m_left), GetTreeHeight(node->m_right));

	if (node->m_parent)
		node->m_parent->m_height = 1 + max(GetTreeHeight(node->m_parent->m_left), GetTreeHeight(node->m_parent->m_right));
}


void RightRotate(AVLTreeNode* node){
	assert(node);
	AVLTreeNode*parent = node->m_parent;
	parent->m_left = node->m_right;
	if (parent->m_left){
		parent->m_left->m_parent = parent;
	}

	node->m_right = parent;
	node->m_parent = parent->m_parent;
	if (node->m_parent)
		if (node->m_parent->m_left == parent)
			node->m_parent->m_left = node;
		else
			node->m_parent->m_right = node;


	parent->m_parent = node;

	//
	parent->m_height = 1 + max(GetTreeHeight(parent->m_left), GetTreeHeight(parent->m_right));
	node->m_height = 1 + max(GetTreeHeight(node->m_left), GetTreeHeight(node->m_right));

	if (node->m_parent)
		node->m_parent->m_height = 1 + max(GetTreeHeight(node->m_parent->m_left), GetTreeHeight(node->m_parent->m_right));
}


AVLTreeNode* insert(int val, AVLTreeNode*root){

	AVLTreeNode * NewNode = new AVLTreeNode;
	NewNode->m_height = 1;
	NewNode->m_val = val;
	NewNode->m_parent = 0;
	NewNode->m_left = 0;
	NewNode->m_right = 0;

	if (root == NULL){
		return NewNode;
	}
	//
	AVLTreeNode * subTree = NULL;				//可能的最小失衡子树.
	AVLTreeNode ** node = &root;
	AVLTreeNode * parent = NULL;

	while (*node){
		if (
			abs(GetTreeHeight((*node)->m_left) -
			GetTreeHeight((*node)->m_right)) == 1){
			subTree = *node;
		}
		parent = *node;
		if (val < (*node)->m_val){
			node = &(*node)->m_left;
		}
		else{
			node = &(*node)->m_right;
		}
	}
	//现在node 是要插入的位置.
	NewNode->m_parent = parent;
	*node = NewNode;

	//调整路径上的树高度.
	node = &NewNode->m_parent;
	while (*node && *node != subTree){
		(*node)->m_height = 1 + max(GetTreeHeight((*node)->m_left),
			GetTreeHeight((*node)->m_right));
		node = &(*node)->m_parent;
	}

	if (subTree){
		//平衡破坏.
		if (abs(GetTreeHeight(subTree->m_left) -
			GetTreeHeight(subTree->m_right)) == 2){

			if (val < subTree->m_val){
				if (val < subTree->m_left->m_val){
					if (subTree == root)
						root = subTree->m_left;

					RightRotate(subTree->m_left);			//LL.
				}
				else{
					LeftRotate(subTree->m_left->m_right);	//LR.

					if (subTree == root)
						root = subTree->m_left;
					RightRotate(subTree->m_left);
				}
			}
			else{
				if (val >= subTree->m_right->m_val){
					if (subTree == root)
						root = subTree->m_right;
					LeftRotate(subTree->m_right);			//RR
				}
				else{
					RightRotate(subTree->m_right->m_left);	//RL

					if (subTree == root)
						root = subTree->m_right;

					LeftRotate(subTree->m_right);
				}
			}
		}
	}
	return root;
}


int CheckGetTreeHeight(AVLTreeNode* root){
	if (!root)
		return 0;
	return 1 + max(CheckGetTreeHeight(root->m_left), CheckGetTreeHeight(root->m_right));
}

bool ValidAVL(AVLTreeNode* root){
	if (!root)
		return true;
	//检查子树是否为平衡二叉树.
	if (!ValidAVL(root->m_left))
		return false;
	if (!ValidAVL(root->m_right))
		return false;

	if (abs(CheckGetTreeHeight(root->m_left) - CheckGetTreeHeight(root->m_right)) > 1){
		return false;
	}
	return true;
}

int main(){
	AVLTreeNode* root = NULL;
	srand(time(0));
	for (int i = 0; i < 10000; i++){
		root = insert(rand(), root);
	}
	if (!ValidAVL(root)){
		printf("error ,Invalid AVL Tree");
	}
	else{
		printf("Valid AVL Tree");
	}
	return 0;
}

武汉格发信息技术有限公司，格发许可优化管理系统可以帮你评估贵公司软件许可的真实需求，再低成本合规性管理软件许可,帮助贵司提高软件投资回报率，为软件采购、使用提供科学决策依据。支持的软件有: CAD,CAE,PDM,PLM,Catia,Ugnx, AutoCAD, Pro/E, Solidworks 等。

返回上级列表