数据结构学习–AVL树

AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 “An algorithm for the organization of information” 中发表了它。

其中AVL树主要的操作包括：左旋、右旋、两种情况的双旋转。下面先给出旋转的示意图：

单旋：

两种情况的双旋：

 

下面，根据上述的旋转示意图编写递归的代码：

struct AvlNode{
	int val, height;
	AvlNode*l, *r;
	AvlNode() :val(-1), height(-1), l(NULL), r(NULL){};
	AvlNode(int x) :val(x), height(0), l(NULL), r(NULL){};
};
static int Height(AvlNode* T)
{//求高度
	if (T == NULL) return -1;
	else return T->height;
}
static AvlNode* SingleRotateLeft(AvlNode* k2)
{//左旋，把树顺时针旋转
	AvlNode*k1 = k2->l;
	k2->l = k1->r;
	k1->r = k2;
	//注意更新高度
	k2->height = max(Height(k2->l), Height(k2->r)) + 1;
	k1->height = max(Height(k1->l), k2->height) + 1;
	return k1;
}
static AvlNode* SingleRotateRight(AvlNode* k1)
{//右旋，把树逆时针旋转
	AvlNode*k2 = k1->r;
	k1->r = k2->l;
	k2->l = k1;
	//注意更新高度
	k1->height = max(Height(k1->l), Height(k1->r)) + 1;
	k2->height = max(Height(k2->r), k1->height) + 1;
	return k2;
}
static AvlNode* DoubleRotateLeft(AvlNode* k3)
{//先把k2（k3->l）逆时针旋转，再把k3顺时针旋转
	k3->l = SingleRotateRight(k3->l);
	return SingleRotateLeft(k3);
}

static AvlNode* DoubleRotateRight(AvlNode* k1)
{//先把k2（k1->r）逆时针旋转，再把k1顺时针旋转
	k1->r = SingleRotateLeft(k1->r);
	return SingleRotateRight(k1);
}

static AvlNode* Insert(int x, AvlNode*T)
{
	if (T == NULL)//如果节点为空，则新建一个节点
		T = new AvlNode(x);
	else if (x < T->val)
	{//x小于T的值，则插入左边
		T->l = Insert(x, T->l);
		if (Height(T->l) - Height(T->r) == 2)
		{//插入后，左边比右边高2，则需要调整
			if (x < T->l->val)//如果插入的值是在左子树的左边，则左旋即可
				T = SingleRotateLeft(T);
			else//如果插入的值是在左子树的右边，那么需要双旋转
				T = DoubleRotateLeft(T);
		}
	}
	else if (x > T->val)
	{//如果插入的值大于T的值，则插入T的右子树中
		T->r = Insert(x, T->r);
		if (Height(T->r) - Height(T->l) == 2)
		{//高度差为2，需要调整
			if (x>T->r->val)//如果在右子树的右边，单选即可
				T = SingleRotateRight(T);
			else//在右子树的左边，需要双旋
				T = DoubleRotateRight(T);
		}
	}
	//注意更新高度
	T->height = max(Height(T->l), Height(T->r)) + 1;
	return T;
}