AVL树实现代码、红黑树参考链接

平衡二叉树的调整

被插入/删除节点 到 根节点 路径上的那些节点 有失去平衡的可能性（只有这些节点的字数结构发生了改变）

只要将 距离新节点最近的不平衡节点 进行调整，就能使得AVL树恢复平衡（下面的平衡了上面的自然就会平衡）。

调整后一要平衡、二要保证是二叉搜索树，
不止一种调整方法！！！二叉搜索树形态稍稍改变也可以仍然是二叉搜索树呀！

最基本最稳的规律——

LL——第一个不平衡节点右旋一次

RR——第一个不平衡节点左旋一次

LR——涉及的节点有三个g，p，q，第一个被破坏节点g，g的左孩子g->left（记作p），g的左孩子的右孩子p->right(记作q)(不一定是被插入节点噢，被插入节点可能是q，也可能在q的左/右子树，但不管是三种情况中的哪种，只关心q）

要将这三个节点规规矩矩调整成（左下<顶点<右下）的情形

LR型 先左旋再右旋（和LL型右旋不同，这里可以理解成先解决后犯的右倾错误进行左旋，再解决先犯的左倾错误进行右旋）LL，RR与名字相反，LR，RL按名字来旋转

调整必定自底而上
p（相对于q，q相对于p是RR）左旋，g（相对于p，其实无需多言，g右旋就是相对于g的左孩子嘛）右旋

RL——先右旋再左旋

根据插入节点位于被破坏节点的方位，将不平衡的情形分为4类——LL，RR、 LR、RL

插入节点位于被破坏节点的LL,那么对于被破坏节点需要进行一次右旋——被破坏节点g（仅仅包括g本身和它的孩子，不管它的祖先）将 它的左儿子g->left (记作p)的右孩子p->right收做左孩子，p再将g收做右儿子 、接着p取代g的位置（继承他的祖先）。

node*p=g->left;
g->left=p->right;
p->right=g;
g=p;//g是一开始被破坏节点的祖先指向被破坏节点的祖先

如果用root来表示这个被破坏节点g就更好，最后一步root=p；让p成为新的根节点就更容易理解，

但注意：第一个被破坏平衡的节点g不一定位于根节点的位置，g可能有很多祖先（由于孩子g不平衡，这些祖先都不平衡），但只要将g调整平衡（将g的孩子提上来取代g，g右旋下去做孩子），这些祖先 自然平衡了

这是不同于以上所讲规律的调整方式，对第二个失衡节点进行右旋的
对第一个失衡节点进行右旋的成果是

两种都OK，还是严格按照第二种叭

删除

先find 用前驱或后继替代它
对于二叉搜索树的删除，例如偏偏费力只用后继替代删除节点
删除节点有右孩子，后继节点在右子树的最左下角(右子树的最小节点)
没有右孩子就麻烦了，还要到祖先中找后继
其实完全没必要，可以根据删除节点的左右子树情况来判断用前驱还是
后继节点来替代被删除节点(没有右儿子就到左子树中找前驱，要是左子树
都没有，那感情更好，直接删掉)
而为了尽可能考虑高度使AVL树平衡，就从更高的子树中取前驱或后继
（左子树更高就取前驱节点，左子树中的最大节点）
用前驱/后继节点p替代删除节点，在原来位置删去p(这个很好的递归
就避免了错位的麻烦，省的用p的右子树来替p 这一步)

源代码总体测试

麻了🙂

#include <iostream>
#include<stdlib.h>
#include<math.h>
using namespace std;
typedef struct node{
	int val;
	node*left;
	node*right;
}node;
node*LL(node*g){//g是第一个失衡节点，右旋一次 
	node*p=g->left;
	g->left=p->right;
	p->right=g;
	//return p;直接return p也行 
	g=p; 
	return g;
}
node*RR(node*g){
	node*p=g->right;
	g->right=p->left;
	p->left=g;
	g=p;
	return g;
} 
node*LR(node*g){//先左旋再右旋 
	g->left=RR(g->left);//RR型是左旋噢 
	return LL(g); 
}
node*RL(node*g){//先左旋再右旋 
	g->right=LL(g->right);
	return RR(g); 
}
int getHeight(node*root){
	if(root==NULL)return 0;
	else return max(getHeight(root->left),getHeight(root->right)) 1;
}
bool balanced(node*root){
	if(root==NULL)return true;
	if(abs(getHeight(root->right)-getHeight(root->left))>1)return false;
	return balanced(root->right)&&balanced(root->left);
}
node*insert(node*root,int v){
	node*newnode=(node*)malloc(sizeof(node));
	newnode->val=v;
	newnode->left=NULL;
	newnode->right=NULL;
	if(root==NULL){
		root=newnode;
		return newnode;
	}
	else{
		if(v>root->val){
			root->right=insert(root->right,v);
			if(balanced(root)==false){
				if(v>root->right->val){//RR
					root=RR(root);
				}
				else{//RL
					root=RL(root);
				}
			}
		}
		else if(v<root->val){
			root->left=insert(root->left,v);
			if(balanced(root)==false){
				if(v>root->left->val){//LR
					root=LR(root);
				}
				else{//LL
					root=LL(root);
				}
			}
		}
	}
	return root;
}
node*find(node*root,int v){
	if(root==NULL)return NULL;
	if(root->val==v)return root;
	if(root->val>v)return find(root->left,v);
	if(root->val<v)return find(root->right,v);
}
node*findMax(node*root){
	if(root==NULL)return NULL;
	while(root->right){
		root=root->right;
	}
	return root;
} 
node*findMin(node*root){
	if(root==NULL)return NULL;
	while(root->left){
		root=root->left;
	}
	return root;
} 
node*Delete(node*root,int v){
	node*t=root;
//	node*del=find(root,v);
	if(t==NULL)return t;
		if(t->val==v){
			if(t->left&&t->right){//左右孩子都不为空 
				if(getHeight(t->left)>getHeight(t->right)){//保证一定平衡了（原来是平衡的） 
					node* p=findMax(t->left);
					t->val=p->val;//直接替换数据，换节点还得动指针 
					t->left=Delete(t->left,p->val); 
				} 
				else{
					node* p=findMin(t->right);
					t->val=p->val;//直接替换数据，换节点还得动指针 
					t->right=Delete(t->right,p->val); 
				} 
			}
			else{
				node*q=t;
				t=(t->left)?t->left:t->right;//t赋值为不空的子结点
				delete q;//清除那个被删节点 
			}
		} 
		else if(v<t->val){//递归删除左子树上的结点
			t->left=Delete(t->left,v);
			if(balanced(t)==false){
//				if(v<t->left->val)
				if (getHeight(t->right->left) < getHeight(t->right->right)){//RR
					t=RR(t);
	//删除节点在t左子树的左子树，左边矮右边高是RR型 将非平衡点左旋 
				}
				else t=RL(t); 
			} 
		}
		else{
			t->right=Delete(t->right,v);
			if(balanced(t)==false){//左边的高 
//				if(v<t->right->val)
				if (getHeight(t->left->right) > getHeight(t->left->left)){//L
					t=LR(t);
	//删除节点在t右子树的左子树， 
				}
				else t=LL(t); 
			} 
		}
	return t;
}
void inorder(node*root){
	if(root==NULL)return;//不要忘啦！！！递归出口 
	inorder(root->left);
	cout<<root->val<<" ";
	inorder(root->right);
}
int main(){
	int n,v;
	cin>>n;
	node*root=NULL;
	while(n--){
		cin>>v;
		root=insert(root,v);
	}
	cout<<root->val<<endl;//根节点 
	inorder(root);
	cout<<getHeight(root)<<endl;
	root=Delete(root,4);
	cout<<root->val<<endl;//根节点 
	inorder(root);
	cout<<getHeight(root)<<endl;
    return 0;
} 

[1066 Root of AVL Tree (25 分)]

[1066 Root of AVL Tree (25 分)]
两个注意要避免的错误：
1、判断NULL时，’=’ 和 ’==‘
2、==root->left=insert(root->left,v);==不要写成
root=insert(root->left,v);

#include <iostream>
#include <math.h>
#include<stdlib.h>
using namespace std;
typedef struct node{
	int val;
	node*left;
	node*right;
}node;
int getHeight(node*root){
	if(root==NULL)return 0;
	else return max(getHeight(root->left),getHeight(root->right)) 1;
}
bool balanced(node*root){
	if(root==NULL)return true;
	if(abs(getHeight(root->left)-getHeight(root->right))>1)return false;
	return balanced(root->left)&&balanced(root->right);
}
node*LL(node*g){
	node*p=g->left;
	g->left=p->right;
	p->right=g;
	g=p;
	return g;
}
node*RR(node*g){
	node*p=g->right;
	g->right=p->left;
	p->left=g;
	g=p;
	return g; 
}
node*LR(node*g){//先左旋再右旋 
	g->left=RR(g->left);
	g=LL(g);
	return g; 
}
node*RL(node*g){//先右旋再左旋
	g->right=LL(g->right);
	g=RR(g);
	return g; 
}
node*insert(node*root,int v){
	node*newnode=(node*)malloc(sizeof(node));
	newnode->val=v;
	newnode->left=NULL;
	newnode->right=NULL;
	if(root==NULL){
		root=newnode;
		return root;
	}
	if(v<root->val){
		root->left=insert(root->left,v);
		if(balanced(root)==false){
			if(v<root->left->val)root=LL(root);
			else root=LR(root);
		}
	}
	else if(v>root->val){
		root->right=insert(root->right,v);
		if(balanced(root)==false){
			if(v<root->right->val)root=RL(root);
			else root=RR(root);
		}
	}
	return root;
}
int main(){
	int n;
	cin>>n;
	node*root=NULL;
	int v;
	while(n--){
		cin>>v;
		root=insert(root,v);
	} 
	cout<<root->val; 
    return 0;
} 

参考博客
彻底搞懂平衡二叉树（AVL）建树过程（左旋、右旋）
平衡二叉树(AVL树)的平衡原理以及插入,删除操作

红黑树

为什么有了AVL树还需要红黑树？

虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在O(logn),不过却不是最佳的,因为平衡树要求每个节点的左子树和右子树的高度差至多等于1,这个要求实在是太严了，导致每次进行插入删除节点的时候,几乎都会破坏平衡树的第二个规则 ，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树! ! !

1.红黑树的性质

1.每个节点要么是黑色，要么是红色。

2.根结点是黑色。

3.每个叶子节点（NIL：空）是黑色。

4.每个红色节点的两个子节点一定都是黑色。

5.任意一节点到每个叶子节点的路径都包含数量相同的黑结点。俗称：黑高

如果一个节点存在黑子节点，那么该结点肯定有两个子节点。（性质五）
不会有两个连续的红色节点（性质四）……

红黑树并不是一个完美平衡叉查找树，左子树可以显然比右子树高，但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每 个叶子结点的路径都包含数量相同的结点(性质5)。所以我们叫红黑树这种平衡为黑色完美平衡。

红黑树能自平衡，它靠的是什么?

三种操作:左旋、右旋和变色。

1.变色:结点的颜色由红变黑或由黑变红。
2.左旋:以某个结点作为支点(旋转结点),其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。
3.右旋:以某个结点作为支点(旋转结点)，左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变

插入自平衡

插入节点，必须为红色，
理由很简单，插入红色节点，

针对最难维护的性质五——在父节点(如果存在)为黑色节点时,红黑树的黑色平衡没被破坏，不需要做自平衡操作。
但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1,必须做自平衡。

针对性质四：红色节点两个黑色孩子。插入黑色节点不会破坏性质四，插入红色节点也只有一半可能性破坏性质四（父节点为红色破坏，父节点为黑色不破坏），而且易于通过变色恢复

下面是可能遇到的插入的几种状况：

1、当插入的节点是根节点时，直接涂黑即可；

2、当要插入的节点的父节点是黑色的时候。

由于插入的结点是红色的，当插入结点的黑色时，并不会影响红黑树的平衡，直接插入即可，无需做自平衡。

3、……
大佬们的总结云集
插入删除情景分类与图解
插入情景分类与图解
插入删除图解
插入删除图解
map、set红黑树实现机制
红黑树2-3叉树

这篇好文章是转载于：学新通技术网