AVL树

基础知识

名称 : AVL树

发明者 :

G. M. Adelson-Velsky

E.M. Landis

年代 : 1962年(58岁)

优点 :

由于对每个节点的左右子树的树高做了限制, 所以整棵树不会退化成一个链表

**学习重点 : **

1. 平衡二叉排序树,本质上也是二叉排序树, 所以拥有二叉排序树的所有性质
2. 平衡二叉排序树的学习重点, 在于平衡条件以及平衡调整的相关学习

性质 :

1. 平衡条件 : | H(left) - H(right) | ≤ 1

思考 :

​ 高度为 H 的树, 所包含节点的范围是?

​ BinarySearchTree : H ≤ size ≤ 2^H - 1

​ AVLTree : low(H-2) + low(H-1) + 1 ≤ size ≤ 2^H - 1 (low(H) 是 H 高度的二叉树的最少节点数) 左边等于 1.5^H

操作SSS

AVL树 - 左旋

左旋前 左旋后 AVL树 - 右旋 右旋前 右旋后

失衡类型

h(1,2,3,4) 分别代表左孩子的左子树个高,左孩子的右子树高,右孩子的左子树高和右孩子的右子树高

LL类型:左子树的左孩子更高

满足条件 : h1 = max(h3, h4) + 2 = h2 + 1

调整方案 : K1 右旋

LR类型:左子树的右孩子更高

满足条件 : max(h2, h3) = h4 = h1

调整方案 : 小左旋, 大右旋(左孩子左旋, 根节点右旋)

RL类型:右子树的左孩子更高

调整方案 : 小右旋, 大左旋

RR类型:右子树的右孩子更高

调整方案 : K1 左旋

平衡调整策略

1. 发生在回溯阶段的, 第一个失衡节点处
2. 理解平衡调整策略的关键在于 : 分析清楚四种情况下, ABCD四棵子树树高的关系
3. LL, 大右旋
4. LR, 先小左旋, 再大右旋
5. RL, 先小右旋, 再大左旋
6. RR, 大左旋

代码关键点

1. 插入和删除以后, 注意调整树高字段, 先调低的root, 再调高的tmp
2. 引入了NIL节点, 代替了 NULL和nullptr, NULL不可访问资源, NIL是一个实际节点, 可以访问资源(h,lchild,rchild)

代码实现

#include <cstdio>
#include <iostream>
using namespace std;

#define L(n) (n->lchild)
#define R(n) (n->rchild)
#define H(n) (n->h)

typedef struct Node{
	int key,h;
	struct Node *lchild, *rchild;
}Node;

//虚拟空节点, 为红黑树做准备的节点
Node __NIL;
#define NIL (&__NIL)
__attribute__((constructor))
void init_NIL(){
	NIL->key = 0, NIL->h = 0;
	NIL->lchild = NIL->rchild = nullptr;
}
//优先初始化上面这一段代码


/*
 * AVL树的若干操作:
 * 1. 创建节点
 * 2. 销毁节点
 * 3. 插入
 * 4. 删除
*/

Node *getNewNode(int key){
	Node * tmp = (Node*)malloc(sizeof(Node));
	tmp->key = key;
	tmp->h = 1;
	tmp->lchild = NIL, tmp->rchild = NIL;
	return tmp;
}

void clear(Node * root){
	if(root == NIL)	return;
	clear(root->lchild);
	clear(root->rchild);
	free(root);
	return;
}

//调整高度
void update_height(Node * root){
	root->h = (H(L(root)) > H(R(root)) ? H(L(root)) : H(R(root))) + 1;
}

//左旋
Node * left_rotate(Node * root){
	Node * tmp = root->rchild; //新根节点
	root->rchild = tmp->lchild; //新左挂旧右
	tmp->lchild = root; //旧根挂新左
	update_height(root);
	update_height(tmp);
	return tmp;
}

//右旋
Node * right_rotate(Node * root){
	Node * tmp = root->lchild; //新根
	root->lchild = tmp->rchild; //新右成旧左
	tmp->rchild = root; //旧根成新左
	update_height(root);
	update_height(tmp);
	return tmp;
}

//调整
Node * maintain(Node * root){
	//平衡调整代码
	if(abs(H(L(root)) - H(R(root))) <= 1)	return root;
	if(root->lchild->h > root->rchild->h) {
		//LR先小左旋
		if(root->lchild->lchild->h < root->lchild->rchild->h)
			root->lchild = left_rotate(root->lchild);
		//LL大右旋
		root = right_rotate(root);
	} else {
		//RL先小右旋
		if(root->rchild->rchild->h < root->rchild->lchild->h)
			root->rchild = right_rotate(root->rchild);
		//RR大左旋
		root = left_rotate(root);
	}
	return root;
}

Node * insert(Node * root, int key){
	if(root == NIL)	return getNewNode(key);
	if(root->key == key)	return root;
	if(key < root->key)	root->lchild = insert(root->lchild, key);
	if(key > root->key)	root->rchild = insert(root->rchild, key);
	update_height(root);
	return maintain(root);
}

//寻找前驱节点,默认传入度为2的节点,前父节点有左子树
Node * predeccessor(Node * root){
	Node * tmp = root->lchild;
	while(tmp->rchild)	tmp = tmp->rchild;
	return tmp;
}

Node * erase(Node * root, int key){
	if(root == NIL)	return NIL;
	if(key < root->key) {
		root->lchild = erase(root->lchild, key);
	} else if(key > root->key) {
		root->rchild = erase(root->rchild, key);
	} else { //删除当前节点
		if(root->rchild == NIL || root->lchild == NIL){
			Node * tmp = root->rchild != NIL ? root->rchild : root->lchild;
			free(root);
			return tmp;
		} else { // 删除度为2的节点
			Node * tmp = predeccessor(root);
			root->key = tmp->key;
			root->lchild = erase(root->lchild, root->key);
		}
	}
	update_height(root);
	return maintain(root);
}

void print(Node * root){
	printf("(%d[%d], %d, %d)\n",
			root->key, root->h,
			root->lchild->key,
			root->rchild->key
			);
}


void output(Node * root){
	if(root == NIL)	return;
	print(root);
	output(root->lchild);
	output(root->rchild);
	return ;
}

int main(int argc, char ** argv){
	int op, val;
	Node* root = NIL;
	while(~scanf("%d%d", &op, &val)){
		switch(op){
			case 0: root = erase(root, val); break;
			case 1: root = insert(root, val); break;
		}
		output(root);
		printf("------------\n");
	}
	return 0;
}