目录

1.什么是平衡二叉树

2.平衡二叉树的失衡调整

2.1左旋

2.2 右旋

3. AVL树的四种插入节点方式

4.平衡二叉树完整代码实现

5.红黑树与平衡二叉树

5.1 红黑树的性质

5.2 旋转和颜色变化规则

5.3 平衡二叉树(AVL)的性质

1.什么是平衡二叉树

在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)。

可以是空树。假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。

增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。

二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序时，例如序列 A = {1，2，3，4，5，6}，构造二叉搜索树如图 1.1。依据此序列构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为 O(n)。

2.平衡二叉树的失衡调整

主要是通过旋转最小失衡子树来实现的。根据旋转的方向有两种处理方式，左旋与右旋。

旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。

2.1左旋

当插入的新节点在节点右子树的右子树位置时。

简称：右右->左旋

（1）原节点的右孩子替代此节点位置

（2）原节点右孩子的左子树变为该节点的右子树

（3）原节点本身变为右孩子新节点的左子树

2.2 右旋

当新插入是节点左子树的左子树时，需要右旋。

右旋操作与左旋类似，操作流程为：

（1）原节点的左孩子代表此节点

（2）原节点的左孩子的右子树变为节点的左子树

（3）将原节点作为左孩子新节点的右子树。

3. AVL树的四种插入节点方式

插入方式：LL

描述：在 A 的左子树根节点的左子树上插入节点而破坏平衡

旋转方式：右旋转

插入方式：RR

描述：在 A 的右子树根节点的右子树上插入节点而破坏平衡

旋转方式：左旋转

插入方式：LR

描述：在A的左子树根节点的右子树上插入节点而破坏平衡

旋转方式：先左旋后右旋

插入方式：RL

描述：在 A 的右子树根节点的左子树上插入节点而破坏平衡

旋转方式：先右旋后左旋

4.平衡二叉树完整代码实现

AvlTree.h

#include <iostream>#include <algorithm>using namespace std;#pragma once//平衡二叉树结点template <typename T>struct AvlNode{T data;int height; //结点所在高度AvlNode<T> *left;AvlNode<T> *right;AvlNode<T>(const T theData) : data(theData), left(NULL), right(NULL), height(0){}};//AvlTreetemplate <typename T>class AvlTree{public:AvlTree<T>(){}~AvlTree<T>(){}AvlNode<T> *root;//插入结点void Insert(AvlNode<T> *&t, T x);//删除结点bool Delete(AvlNode<T> *&t, T x);//查找是否存在给定值的结点bool Contains(AvlNode<T> *t, const T x) const;//中序遍历void InorderTraversal(AvlNode<T> *t);//前序遍历void PreorderTraversal(AvlNode<T> *t);//最小值结点AvlNode<T> *FindMin(AvlNode<T> *t) const;//最大值结点AvlNode<T> *FindMax(AvlNode<T> *t) const;private://求树的高度int GetHeight(AvlNode<T> *t);//单旋转 左AvlNode<T> *LL(AvlNode<T> *t);//单旋转 右AvlNode<T> *RR(AvlNode<T> *t);//双旋转 右左AvlNode<T> *LR(AvlNode<T> *t);//双旋转 左右AvlNode<T> *RL(AvlNode<T> *t);};template <typename T>AvlNode<T> * AvlTree<T>::FindMax(AvlNode<T> *t) const{if (t == NULL)return NULL;if (t->right == NULL)return t;return FindMax(t->right);}template <typename T>AvlNode<T> * AvlTree<T>::FindMin(AvlNode<T> *t) const{if (t == NULL)return NULL;if (t->left == NULL)return t;return FindMin(t->left);}template <typename T>int AvlTree<T>::GetHeight(AvlNode<T> *t){if (t == NULL)return -1;elsereturn t->height;}//单旋转//左左插入导致的不平衡template <typename T>AvlNode<T> * AvlTree<T>::LL(AvlNode<T> *t){AvlNode<T> *q = t->left;t->left = q->right;q->right = t;t = q;t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;q->height = max(GetHeight(q->left), GetHeight(q->right)) + 1;return q;}//单旋转//右右插入导致的不平衡template <typename T>AvlNode<T> * AvlTree<T>::RR(AvlNode<T> *t){AvlNode<T> *q = t->right;t->right = q->left;q->left = t;t = q;t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;q->height = max(GetHeight(q->left), GetHeight(q->right)) + 1;return q;}//双旋转//插入点位于t的左儿子的右子树template <typename T>AvlNode<T> * AvlTree<T>::LR(AvlNode<T> *t){//双旋转可以通过两次单旋转实现//对t的左结点进行RR旋转，再对根节点进行LL旋转RR(t->left);return LL(t);}//双旋转//插入点位于t的右儿子的左子树template <typename T>AvlNode<T> * AvlTree<T>::RL(AvlNode<T> *t){LL(t->right);return RR(t);}template <typename T>void AvlTree<T>::Insert(AvlNode<T> *&t, T x){if (t == NULL)t = new AvlNode<T>(x);else if (x < t->data){Insert(t->left, x);//判断平衡情况if (GetHeight(t->left) - GetHeight(t->right) > 1){//分两种情况 左左或左右if (x < t->left->data)//左左t = LL(t);else //左右t = LR(t);}}else if (x > t->data){Insert(t->right, x);if (GetHeight(t->right) - GetHeight(t->left) > 1){if (x > t->right->data)t = RR(t);elset = RL(t);}}else;//数据重复t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;}template <typename T>bool AvlTree<T>::Delete(AvlNode<T> *&t, T x){//t为空 未找到要删除的结点if (t == NULL)return false;//找到了要删除的结点else if (t->data == x){//左右子树都非空if (t->left != NULL && t->right != NULL){//在高度更大的那个子树上进行删除操作//左子树高度大，删除左子树中值最大的结点，将其赋给根结点if (GetHeight(t->left) > GetHeight(t->right)){t->data = FindMax(t->left)->data;Delete(t->left, t->data);}else//右子树高度更大，删除右子树中值最小的结点，将其赋给根结点{t->data = FindMin(t->right)->data;Delete(t->right, t->data);}}else{//左右子树有一个不为空，直接用需要删除的结点的子结点替换即可AvlNode<T> *old = t;t = t->left ? t->left: t->right;//t赋值为不空的子结点delete old;}}else if (x < t->data)//要删除的结点在左子树上{//递归删除左子树上的结点Delete(t->left, x);//判断是否仍然满足平衡条件if (GetHeight(t->right) - GetHeight(t->left) > 1){if (GetHeight(t->right->left) > GetHeight(t->right->right)){//RL双旋转t = RL(t);}else{//RR单旋转t = RR(t);}}else//满足平衡条件 调整高度信息{t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;}}else//要删除的结点在右子树上{//递归删除右子树结点Delete(t->right, x);//判断平衡情况if (GetHeight(t->left) - GetHeight(t->right) > 1){if (GetHeight(t->left->right) > GetHeight(t->left->left)){//LR双旋转t = LR(t);}else{//LL单旋转t = LL(t);}}else//满足平衡性 调整高度{t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;}}return true;}//查找结点template <typename T>bool AvlTree<T>::Contains(AvlNode<T> *t, const T x) const{if (t == NULL)return false;if (x < t->data)return Contains(t->left, x);else if (x > t->data)return Contains(t->right, x);elsereturn true;}//中序遍历template <typename T>void AvlTree<T>::InorderTraversal(AvlNode<T> *t){if (t){InorderTraversal(t->left);cout << t->data << ' ';InorderTraversal(t->right);}}//前序遍历template <typename T>void AvlTree<T>::PreorderTraversal(AvlNode<T> *t){if (t){cout << t->data << ' ';PreorderTraversal(t->left);PreorderTraversal(t->right);}}

main.cpp

#include "AvlTree.h"int main(){AvlTree<int> tree;int value;int tmp;cout << "请输入整数建立二叉树(-1结束)：" << endl;while (cin >> value){if (value == -1)break;tree.Insert(tree.root,value);}cout << "中序遍历";tree.InorderTraversal(tree.root);cout << "\n前序遍历:";tree.PreorderTraversal(tree.root);cout << "\n请输入要查找的结点：";cin >> tmp;if (tree.Contains(tree.root, tmp))cout << "已查找到" << endl;elsecout << "值为" << tmp << "的结点不存在" << endl;cout << "请输入要删除的结点：";cin >> tmp;tree.Delete(tree.root, tmp);cout << "删除后的中序遍历：";tree.InorderTraversal(tree.root);cout << "\n删除后的前序遍历：";tree.PreorderTraversal(tree.root);}

5.红黑树与平衡二叉树

5.1 红黑树的性质

性质1.节点是红色或黑色。

性质2.根节点是黑色。

性质3.每个叶子节点都是黑色的空节点（NIL节点）。

性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

5.2 旋转和颜色变化规则

1、添加的节点必须为红色

2、变色的情况：当前结点的父亲是红色，且它的叔结点也是红色：

2.1把父节点设置为黑色

2.2把叔节点设置为黑色

2.3把祖父节点设置为红色

2.4把当前指针定义到祖父节点，设为当前要操作的

3、左旋的情况：当前父节点是红色，叔节点是黑色，且当前的节点是右子树。

3.1以父节点作为左旋。

4、右旋的情况：当前父节点是红色，叔节点是黑色，且当前的节点是左子树。

4.1把父节点变成黑色

4.2把祖父节点变为红色

4.3以祖父节点右旋转

5.3 平衡二叉树(AVL)的性质

它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

区别：

1、红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。

2、平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。