2019-05-28

AVL

缘起

【1】中介绍了BST，但是BST在数据倾斜的厉害的时候，树结构这种半线性数据结构蜕化为线性数据结构导致查询效率由理论的O(logn)降低为最坏的 O(n). 根本原因是在插入节点的时候, 没有动态维护树的结构, 导致树的高度不断变深. 所以需要引入一种平衡查找树——不论你插入的数据倾斜有多严重，树的深度一直维持在 O(logn). 这种查找树就是 AVL. AVL亦是BST. 只是高度维护的好.

分析

显然, AVL相比BST 的代价就是插入的时候要不停的维护树的节点. 让其高度维持在logn.

#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996)
//#define LOCAL
using namespace std;

typedef struct AVLNode
{
	int data, bf; // data是数据, bf是balance factor，即平衡因子，一个节点的bf=左子树深度-右子树的深度.AVL要求所有节点的bf值的绝对值<=1
	AVLNode *lc, *rc;
	AVLNode(int data):data(data),bf(0),lc(NULL),rc(NULL){}
} AVLNode, *AVLTree; // 定义AVL树的节点

// 基础操作之左旋——根节点找到右孩子,根节点的右孩子=右孩子的左孩子, 右孩子的左孩子=根节点, 右孩子作为新的根节点
void leftrotate(AVLTree &root) // 对AVL树（root根节点）进行左旋操作(即根节点绕着它的右孩子进行逆时针旋转)
{
	AVLTree r = root->rc;
	root->rc = r->lc;
	r->lc = root; // 原先的根节点变成了r(原先根节点的右节点)的左节点
	root = r; // 根节点易主
} // 所谓左旋的意思就是根节点R绕着它的右孩子RC逆时针旋转, 然后R变成RC的左孩子, RC的左孩子变成R的右孩子, 最后将原本的R设置成RC, 则树根易主了.

// 基础操作之右旋——根节点找到左孩子, 根节点的左孩子=左孩子的右孩子, 左孩子的右孩子=根节点, 左孩子作为新的根节点
void rightrotate(AVLTree &root) // 对AVL树(root根节点)进行右旋操作(即根节点绕着它的左孩子顺时针旋转)
{
	AVLTree r = root->lc;
	root->lc = r->rc;
	r->rc = root; // 原先的根节点变成了r（原先根节点的左节点）的右节点
	root = r; // 根节点易主
}

// 复合操作之左平衡(当root的bf为2的时候要做这个操作)
void leftbalance(AVLTree &root)
{
	AVLTree lc = root->lc; // lc指向root的左孩子
	switch(lc->bf) // 1和0是一次自旋搞定, -1是两次自旋搞定
	{
	case 1: // 左孩子的bf是1， 则只需要对root做一次右旋即可  参见图1、2、3
		lc->bf = root->bf = 0; // 先改bf
		rightrotate(root); // 则root变成它的左孩子
		break;
	case 0: // 左孩子的bf是0, 注意, 这种情况不可能出现在insert的时候，只可能是delete的时候, 此时也只需要进行一次右旋即可 参见图4
		lc->bf = -1; // 左孩子的bf变成-1
		root->bf = 1; // 原先根节点的bf变成1
		rightrotate(root);
		break;    
	case -1: // root的bf为2，但是左孩子的bf是-1, 则这种情况需要两次旋转才行——先左旋, 再右旋
		AVLTree lr= lc->rc; // 考察左孩子的右孩子
		switch(lr->bf) // 因为对于除去 lr、lc、root三个顶点的bf而言，其他点的bf是不会变化的. 而这三个顶点的bf的变化又和lr的bf初值有关, 所以需要switch
		{
		case 1: // 只需要关注 root、lc、lr三个顶点的bf值的变化 参见图5
			root->bf = -1;
			lc->bf = 0;
			break;
		case 0:
			lc->bf = root->bf = 0;			// 参见 图6
			break;
		case -1:						// 参见图7
			lc->bf = 1;
			root->bf =0;
			break;
		}
		lr->bf = 0;
		leftrotate(lc); // 先绕着lc左旋, 再绕着root右旋. 不论lr的bf初始值是什么都是这样.
		rightrotate(root);
		break;
	}
}

// 复合操作之右平衡（当root->bf为-2的时候要做这个）
void rightbalance(AVLTree &root)
{
	AVLTree rc = root->rc;
	switch(rc->bf) // -1和0是一次左旋搞定的
	{
	case -1:   // 参见 图8、9、10
		rc->bf = root->bf = 0; 
		leftrotate(root);
		break;
	case 0:  // insert不可能出现, 只可能是delete时出现， 参见 图11
		rc->bf = 1; 
		root->bf = -1;
		leftrotate(root);
		break;    
	case 1:
		AVLTree lc= rc->lc; // 考察右孩子的左孩子
		switch(lc->bf) 
		{
		case 1:    // 参见 图12
			root->bf = 0;
			rc->bf = -1;
			break;
		case 0:  // 参见 图13
			root->bf = rc->bf = 0;
			break;
		case -1:   // 参见 图14
			rc->bf = 0;
			root->bf = 1;
			break;
		}
		lc->bf = 0;
		rightbalance(rc);
		leftrotate(root);
		break;
	}
}

bool insert(AVLTree &root, int key, bool &taller) // 插入节点, root是AVL树的根. key 是准备插入的数值, taller是插入完成之后整棵AVL（以root为根节点）的高度有没有提高, 返回true表示插入成功, 返回false表示插入失败
{
	if (!root)
	{
		root = new AVLNode(key);
		taller = true; // 以root为根节点的树长高了
		return true;
	}
	if (root->data == key) return false; // 已经有了, 则返回false，插入失败
	if (key < root->data) // 则需要在左子树上插入
	{
		if (!insert(root->lc, key, taller)) return false; // 如果在左子树上插入失败， 则返回false（表明该值已经在左子树上存在了）
		if (taller) // 在左子树上插入成功, 并且左子树因此长高了
		{
			switch(root->bf)
			{
			case 1: // 如果原本root就是左子树比右子树高1的话, 则现在左子树又长高了, 则就达到了2（因为每步都在调整, 所以保证每个节点的bf的绝对值都不会超过1）
				leftbalance(root); // 则就需要左平衡
				taller = false; // 因为左边原本高1, 但是现在左子树又长高了, 所以比右子树高2, 但是经过左平衡处理之后, 高度会减少1的(注意，但是对于删除这一点未必成立,见下面del函数，对于del函数是需要判断的), 所以root为根节点的AVL的高度 不会变化. 所以taller为false
				break;
			case 0:
				root->bf = 1; // 则左子树比右子树高1了, 不需要做平衡处理
				break;
			case -1:
				root->bf = 0; // 则root平衡了, 亦不需要做平衡处理
				taller = false; // root为根节点的树没有长高
				break;
			}
		}
	}
	else // 则需要在右子树上插入
	{
		if (!insert(root->rc, key, taller)) return false;
		if (taller)
		{
			switch(root->bf)
			{
			case 1:
				root->bf = 0;
				taller = false;
				break;
			case 0:
				root->bf = -1; 
				taller = true;
				break;
			case -1:
				rightbalance(root);
				taller = false;
				break;
			}
		}
	}
}

bool del(AVLTree &root, int key, bool &shorter) // 和insert非常像, 删除root为根节点的AVL树上的key值, 如果此过程导致root为根节点的AVL树变矮, shorter为true, 否则shorter为false
{
	if (!root) return false; // 如果是空树, 直接返回false
	if (root->data == key) // 如果找到了要删除的节点, 和BST一样删除
	{
		if (!root->lc && !root->rc)
		{
			delete root;
			root = NULL;
		}
		else if (root->lc && !root->rc) // 有左子树但是没有右子树
		{
			AVLTree p = root;
			root = root->lc; 
			delete p;
			p = NULL;
		}
		else if (!root->lc&& root->rc) // 有右子树但是没有左子树
		{
			AVLTree p = root;
			root = root->rc;
			delete p;
			p = NULL;
		}
		else // 有左右子树
		{
			AVLTree p = root->rc;
			while(p->lc) p = p->lc; // 最后p没有左孩子, 也就是p是root的右孩子的极左顶点
			root->data = p->data; // 删除root节点（即使用p->data顶替掉了root->data，相当于删除了key）
			del(root->rc,root->data,shorter); // 因为此时树中出现了2个root->data了, 所以必须要删除一个. 不然BST中可没有重复元素哦~ 注意，不能像BST中那样自作主张的安排元素, 必须要递归. 因为我们要维护AVL， 你想啊 如果跟BST那样自作主张的安排元素的话, 如果要删除的元素就在根节点的话,岂不是不做任何递归就完成了AVL树的删除工作? 这是有反例证明这种算法是不对的，
		}
	}
	else if (key < root->data) // 要删除的元素如果存在的话，一定在左子树上
	{
		if (!del(root->lc,key, shorter)) return false; // 如果左子树删除失败的话, 返回false
		if (shorter) // 如果左子树变矮了
		{
			switch(root->bf) // 考察原本root的平衡因子
			{
			case 1:
				root->bf = 0;// 原本就是左边高1，左边还矮了1, 则整体root为根的树就变矮了
				break;
			case 0:
				root->bf =  -1; // 如果原本等高,现在左边矮了1，则右边高1，但是root为根的树没有变矮
				shorter = false;
				break;																																																																	
			case -1:
				if (root->rc->bf == 0) shorter = false; // 如果右孩子的bf是0的话 就不会变矮, 否则就会变矮, 参见图15、16
				rightbalance(root); // 如果原本就是右边高,现在左边还矮了， 则右边肯定要做平衡处理 这个过程会对root->bf进行修改的, 不需要我们决断
				break;
			}
		}
	}
	else // 说明如果要删除的key在右子树中（如果存在的话）
	{
		if (!del(root->rc,key, shorter)) return false;
		if (shorter)
		{
			switch(root->bf) 
			{
			case 1:
				if (root->lc->bf == 0) shorter = false;  // 参见 图17、18
				leftbalance(root);
				break;
			case 0:
				root->bf =  1;
				shorter = false;
				break;																																																																	
			case -1:
				root->bf = 0;
				break;
			}
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	AVLTree root=NULL;
	bool taller,shorter;

	//测试insert方法
	insert(root,13,taller);
	insert(root,24,taller);
	insert(root,37,taller);
	insert(root,53,taller);
	insert(root,90,taller);

	//测试delete方法
	//del(root,53,shorter);
	del(root,24,shorter);
	//del(root,37,shorter);
	//del(root,13,shorter);
	//del(root,90,shorter);

	return 0;
}

这里有必要强调一下, 上面所有的函数都是引用传（指针变量的）参数，因为我们最终都是要真正改变指针的值哦. 这样树的结构才会真正的发生变化, 如果仅仅是值传参的话, 则指针变量里面的值不会发生变化, 则AVL的结构是不会发生变化的. 所以这一点一定要注意. 即必须要是 AVLTree & 作为入参, 而不能是 AVLTree作为入参.

可见, 为了能够维持二叉树高度的平衡, 程序要额外多做多少工作!!!