C语言平衡二叉树详解 C语言平衡二叉树详解

调整措施：

一、单旋转
二、双旋转

AVL树的删除操作：

删除分为以下几种情况：

1.要删除的节点是当前根节点T。
2、要删除的节点元素值小于当前根节点T值，在左子树中进行删除。
3、要删除的节点元素值大于当前根节点T值，在右子树中进行删除。

总结

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

文章图片

平衡二叉树大部分操作和二叉查找树类似，主要不同在于插入删除的时候平衡二叉树的平衡可能被改变，并且只有从那些插入点到根结点的路径上的结点的平衡性可能被改变，因为只有这些结点的子树可能变化。
平衡二叉树不平衡的情形：
把需要重新平衡的结点叫做α，由于任意两个结点最多只有两个儿子，因此高度不平衡时，α结点的两颗子树的高度相差2.容易看出，这种不平衡可能出现在下面4中情况中：
1.对α的左儿子的左子树进行一次插入
2.对α的左儿子的右子树进行一次插入
3.对α的右儿子的左子树进行一次插入
4.对α的右儿子的右子树进行一次插入

文章图片

情形1和情形4是关于α的镜像对称，二情形2和情形3也是关于α的镜像对称，因此理论上看只有两种情况，但编程的角度看还是四种情形。
第一种情况是插入发生在“外边”的情形（左左或右右），该情况可以通过一次单旋转完成调整；第二种情况是插入发生在“内部”的情形（左右或右左），这种情况比较复杂，需要通过双旋转来调整。

调整措施：
一、单旋转

文章图片

上图是左左的情况，k2结点不满足平衡性，它的左子树k1比右子树z深两层，k1子树中更深的是k1的左子树x，因此属于左左情况。
为了恢复平衡，我们把x上移一层，并把z下移一层，但此时实际已经超出了AVL树的性质要求。为此，重新安排结点以形成一颗等价的树。为使树恢复平衡，我们把k2变成这棵树的根节点，因为k2大于k1，把k2置于k1的右子树上，而原本在k1右子树的Y大于k1，小于k2，就把Y置于k2的左子树上，这样既满足了二叉查找树的性质，又满足了平衡二叉树的性质。
这种情况称为单旋转。

二、双旋转
对于左右和右左两种情况，单旋转不能解决问题，要经过两次旋转。

文章图片

对于上图情况，为使树恢复平衡，我们需要进行两步，第一步，把k1作为根，进行一次右右旋转，旋转之后就变成了左左情况，所以第二步再进行一次左左旋转，最后得到了一棵以k2为根的平衡二叉树。

AVL树的删除操作：同插入操作一样，删除结点时也有可能破坏平衡性，这就要求我们删除的时候要进行平衡性调整。

删除分为以下几种情况：
首先在整个二叉树中搜索要删除的结点，如果没搜索到直接返回不作处理，否则执行以下操作：

1.要删除的节点是当前根节点T。如果左右子树都非空。在高度较大的子树中实施删除操作。
分两种情况：
(1)、左子树高度大于右子树高度，将左子树中最大的那个元素赋给当前根节点，然后删除左子树中元素值最大的那个节点。
(1)、左子树高度小于右子树高度，将右子树中最小的那个元素赋给当前根节点，然后删除右子树中元素值最小的那个节点。
如果左右子树中有一个为空，那么直接用那个非空子树或者是NULL替换当前根节点即可。

2、要删除的节点元素值小于当前根节点T值，在左子树中进行删除。递归调用，在左子树中实施删除。
这个是需要判断当前根节点是否仍然满足平衡条件，
如果满足平衡条件，只需要更新当前根节点T的高度信息。
否则，需要进行旋转调整：
如果T的左子节点的左子树的高度大于T的左子节点的右子树的高度，进行相应的单旋转。否则进行双旋转。

3、要删除的节点元素值大于当前根节点T值，在右子树中进行删除。下面给出详细代码实现：
AvlTree.h

#include #include using namespace std; #pragma once//平衡二叉树结点template struct AvlNode{T data; int height; //结点所在高度AvlNode *left; AvlNode *right; AvlNode(const T theData) : data(theData), left(NULL), right(NULL), height(0){}}; //AvlTreetemplate class AvlTree{public:AvlTree(){}~AvlTree(){}AvlNode *root; //插入结点void Insert(AvlNode *&t, T x); //删除结点bool Delete(AvlNode *&t, T x); //查找是否存在给定值的结点bool Contains(AvlNode *t, const T x) const; //中序遍历void InorderTraversal(AvlNode *t); //前序遍历void PreorderTraversal(AvlNode *t); //最小值结点AvlNode *FindMin(AvlNode *t) const; //最大值结点AvlNode *FindMax(AvlNode *t) const; private://求树的高度int GetHeight(AvlNode *t); //单旋转左AvlNode *LL(AvlNode *t); //单旋转右AvlNode *RR(AvlNode *t); //双旋转右左AvlNode *LR(AvlNode *t); //双旋转左右AvlNode *RL(AvlNode *t); }; template AvlNode * AvlTree::FindMax(AvlNode *t) const{if (t == NULL)return NULL; if (t->right == NULL)return t; return FindMax(t->right); }template AvlNode * AvlTree::FindMin(AvlNode *t) const{if (t == NULL)return NULL; if (t->left == NULL)return t; return FindMin(t->left); }template int AvlTree::GetHeight(AvlNode *t){if (t == NULL)return -1; elsereturn t->height; }//单旋转//左左插入导致的不平衡template AvlNode * AvlTree::LL(AvlNode *t){AvlNode *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 AvlNode * AvlTree::RR(AvlNode *t){AvlNode *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 AvlNode * AvlTree::LR(AvlNode *t){//双旋转可以通过两次单旋转实现//对t的左结点进行RR旋转，再对根节点进行LL旋转RR(t->left); return LL(t); }//双旋转//插入点位于t的右儿子的左子树template AvlNode * AvlTree::RL(AvlNode *t){LL(t->right); return RR(t); }template void AvlTree::Insert(AvlNode *&t, T x){if (t == NULL)t = new AvlNode(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 bool AvlTree::Delete(AvlNode *&t, T x){//t为空未找到要删除的结点if (t == NULL)return false; //找到了要删除的结点else if (t->data =https://www.it610.com/article/= x){//左右子树都非空if (t->left != NULL && t->right != NULL){//在高度更大的那个子树上进行删除操作//左子树高度大，删除左子树中值最大的结点，将其赋给根结点if (GetHeight(t->left) > GetHeight(t->right)){t->data = https://www.it610.com/article/FindMax(t->left)->data; Delete(t->left, t->data); }else//右子树高度更大，删除右子树中值最小的结点，将其赋给根结点{t->data = https://www.it610.com/article/FindMin(t->right)->data; Delete(t->right, t->data); }}else{//左右子树有一个不为空，直接用需要删除的结点的子结点替换即可AvlNode *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 bool AvlTree::Contains(AvlNode *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 void AvlTree::InorderTraversal(AvlNode *t){if (t){InorderTraversal(t->left); cout << t->data << ' '; InorderTraversal(t->right); }}//前序遍历template void AvlTree::PreorderTraversal(AvlNode *t){if (t){cout << t->data << ' '; PreorderTraversal(t->left); PreorderTraversal(t->right); }}

main.cpp

#include "AvlTree.h"int main(){AvlTree tree; int value; int tmp; cout << "请输入整数建立二叉树(-1结束)：" << endl; while (cin >> value){if (value =https://www.it610.com/article/= -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); }

测试结果：