【数据结构】AVL树（二叉搜索平衡树）

一、引入AVL树

AVL树是二叉搜索树的升级版，是为了优化整个二叉树的结构并且提高查找速率的一棵特殊的二叉搜索树。平衡二字体现了该树会对插入/删除的结点后进行自动“平衡”（通过旋转进行实现）。

二、AVL树的要求

平衡状态： 当前结点的右子树深度 - 左子树深度 == -1 or 0 or 1

三、AVL树结构设计

AVL.h

#ifndef AVL_H
#define AVL_H
using ElemType = int;
typedef struct AVLNode
{
	ElemType key;
	AVLNode* leftchild;
	AVLNode* rightchild;
	AVLNode* parent;
	int balance;
}AVLNode, *AVLTree;

四、旋转

当插入结点时，会出现以下情况：使树失衡，对此有两种应对策略（实质上都是旋转），通过旋转能够对失衡的树进行再次平衡

在这里插入图片描述

五、单左旋

（1）单左旋三大关键步骤

在这里插入图片描述

（2）单左旋完整过程

在这里插入图片描述

（3）单左旋代码

//单左旋
/*
* root是根节点
* ptr指向即将左旋的旧根
*/
void RotateLeft(AVLTree& root, AVLNode* ptr)
{
	AVLNode* newroot = ptr->rightchild;
	newroot->parent = ptr->parent;

	ptr->rightchild = newroot->leftchild;
	if (newroot->leftchild != nullptr)
	{
		newroot->leftchild->parent = ptr;
	}
	newroot->leftchild = ptr;
	//改变原有ptr的双亲的左右孩子指向（newroot）
	//ptr就是root
	if (ptr == root)
	{
		root = newroot;
	}
	else
	{
		if (ptr->parent->leftchild == ptr)
		{
			ptr->parent->leftchild = newroot;
		}
		else
		{
			ptr->parent->rightchild = newroot;
		}
	}
	ptr->parent = newroot;
}

六、单右旋

（1）单右旋代码

//单右旋
void RotateRight(AVLTree& root, AVLNode* ptr)
{
	AVLNode* newroot = ptr->leftchild;
	newroot->parent = ptr->parent;
	ptr->leftchild = newroot->rightchild;
	if (newroot->rightchild != nullptr)
	{
		newroot->rightchild->parent = ptr;
	}
	newroot->rightchild = ptr;
	if (ptr == root)
	{
		root = newroot;
	}
	else
	{
		if (ptr->parent->leftchild == ptr)
		{
			ptr->parent->leftchild = newroot;
		}
		else
		{
			ptr->parent->rightchild = newroot;
		}
	}
	ptr->parent = newroot;
}