本文主要是介绍【C++】【数据结构】一步一步写平衡二叉树[AVL]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
转载：有修正，原作者存在一些错误，这里进行了更正。
/* 平衡二叉树（Balanced Binary Tree）是二叉查找树的一个进化体第一个引入平衡概念的二叉树。特点：对于每一个结点，它的左右子树的高度之差不能超过1，若插入或删除一个节点之后使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。这个方案很好的解决的了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对于二叉查找树来说，时间上稳定了很多。平衡二叉树实现的大部分过程和二叉查找树是一样的（一定要会二叉查找树），区别就在于插入和删除之后要写一个旋转算法去维持平衡，维持平衡需要救助一个节点高度的属性。作者参考的机械工业出版社的《数据结构与算法分析-C语言描述》写了一个C++版的代码。这本书的AVLTree讲的很好，不过没有很完整的去描述。我会一步一步的讲解如何写平衡二叉树，重点是平衡二叉树的核心部分，也就是旋转算法。
*/// 第一步：结点信息
/* 相对于二叉查找树的结点来说，我们需要用一个属性二叉树的高度，
目的是维护插入和删除过程中的旋转算法*/// AVL树节点信息
template<class T>
class TreeNode
{
public:TreeNode():lson(NULL), rson(NULL), freq(1), hgt(0){}T data; // dataint hgt; // height from this nodeunsigned int freq; // frequencyTreeNode *lson; // point to address of left-sonTreeNode *rson; // point to address of right-son
};// 第二步：平衡二叉树类的声明
/* 声明中的旋转函数将在后边的步骤中详解 */// AVL树类的属性和方法声明
template<class T>
class AVLTree
{
private:TreeNode<T>* root; // 根节点void insertpri(TreeNode<T>* &node, T x); // 插入TreeNode<T>* findpri(TreeNode<T>* node, T x); // 查找void insubtree(TreeNode<T>* node); // 中序遍历void Deletepri(TreeNode<T>* &node, T x); // 删除int height(TreeNode<T>* node); // 求树的高度void SingRotateLeft(TreeNode<T>* &k2); // 左左情况下的旋转void SingRotateRight(TreeNode<T>* &k2); // 右右情况下的旋转void DoubleRotateLR(TreeNode<T>* &k3); // 左右情况下的旋转void DoubleRotateRL(TreeNode<T>* &k3); // 右左情况下的旋转int Max(int cmpa, int cmpb); // 求最大值public:AVLTree():root(NULL){}void insert(T x); // 插入接口TreeNode<T>* find(T x); // 查找接口void Delete(T x); // 删除接口void traversal(); // 遍历接口
};// 第三步：两个辅助方法
/* 旋转算法需要借助于两个功能的辅助，一个是求树的高度，一个是求两个高度的最大值。这里规定，一棵空树的高度为-1，只有一个根节点的树的高度为0，以后每多一层高度加1。为了解决指针NULL这种情况，写了一个求高度的函数，这个函数还是很有必要的。
*/// 计算以节点为根的树的高度
template<class T>
int AVLTree<T>::height(TreeNode<T>* node)
{if (node != NULL)return node->hgt;return -1;
}// 求最大值
template<class T>
int AVLTree<T>::Max(int cmpa, int cmpb)
{return cmpa > cmpb ? cmpa : cmpb;
}// 第四步：旋转
/* 对于一个平衡的节点，由于任意节点最多有两个儿子，因此高度不平衡时，此节点的两颗子树的高度差2，这种不平衡出现在下面四种情况；1、6节点的左子树3节点高度比右子树7节点大2，左子树3节点的左子树1节点高度大于右子树4节点，这种为 __左左2、6节点的左子树2节点高度比右子树7节点大2，左子树2节点的左子树1节点高度小于右子树4节点，这种为 __左右3、2节点的左子树1节点高度比右子树5节点小2，右子树5节点的左子树3节点高度大于右子树6节点，这种为 __右左4、2节点的左子树1节点高度比右子树4节点小2，右子树4节点的左子树3节点高度小于右子树6节点，这种为 __右右从图2中可以看出，1和4两种情况是对称的，这两种情况的旋转算法是一致的，只需要经过一次旋转就可以达到目标，我们称之为单旋转。2和3两种情况也是对称的，这两种情况的旋转算法也是一致的，需要进行两次旋转，我们称之为双旋转。
*/// 第五步：单旋转
/* 单旋转是针对于左左和右右这两种情况的解决方案，这两种情况是对称的，只要解决了左左这种情况，右右就很好办了。图3是左左情况的解决方案，节点K2不满足平衡特性，因为它的左子树K1比右子树Z深2层，而且K1子树中，更深的一层是K1的左子树X子树，所以属于左左情况。K2 K1/ \ / \K1 Z 旋转 X K2 / \ ===> | / \X Y ?X? Y Z|?X?图3 左左情况下单旋转的过程为使树恢复平衡，我们要把K2变成这棵树的根节点，因为K2大于K1，把K2置于K1的右子树上，而原本K1右子树的Y大于K1,小于K2,就把Y置于K2的左子树上，这既满足了二叉查找树的性质，又满足了平衡二叉树的性质。这样的操作只需要一部分指针改变，结果我们得到另外一颗二叉查找树，因为X向上移动了一层，Y还停留在原来的层面上，Z向下移动了一层。整棵树的新高度和之前没有在左子树上插入的高度相同，插入操作使得X高度长高了。因此，由于这颗子树高度没有变化，所以通往根节点的路径就不需要继续旋转了。
*/// 左左情况下的旋转
template<class T>
void AVLTree<T>::SingRotateLeft(TreeNode<T>* &k2)
{TreeNode<T>* k1;k1 = k2->lson; // 暂存左子树k2->lson = k1->rson; // 实际情形中，k1可能有rson，可能没有k1->rson = k2;k2->hgt = Max(height(k2->lson), height(k2->rson)) + 1;k1->hgt = Max(height(k1->lson), k2->hgt) + 1;
}
// 右右情况下的旋转
template<class T>
void AVLTree<T>::SingRotateRight(TreeNode<T>* &k2)
{TreeNode<T>* k1;k1 = k2->rson; // 暂存右子树k2->rson = k1->lson;k1->lson = k2;k2->hgt = Max(height(k2->lson), height(k2->rson)) + 1;k1->hgt = Max(height(k1->rson), k2->hgt) + 1;
};// 第六步：双旋转
/* 对于左右和右左这两种情况，单旋转不能使他达到一个平衡状态，要经过两次旋转。双旋转是针对这两种情况的解决方案，同样的，这样两种情况也是对称的，只要解决了左右这种情况，右左就很好办了。图4是左右情况的解决方案，节点k3不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且k1子树中，更深的一层是k1的右子树k2子树，所以属于左右情况。为使树恢复平衡，我们需要进行两步，第一步，把k1作为根，进行一次右右旋转，旋转之后就变成了左左情况，所以第二步再进行一次左左旋转，最后得到了一棵以K2为根的平衡二叉树。K3 K3/ \ / \K1 Z 旋转(转换成左左问题) k2 Z/ \ ==========> / ==X k2 k1 ||| / \ ||?Y? X ?Y? \/(a) 第一次旋转K2 / \ K1 k3 / \ \ X ?Y? Z(b) 第二次旋转图4 左右情况下双旋转的过程
*/
// 左右情况下的旋转
template<class T>
void AVLTree<T>::DoubleRotateLR(TreeNode<T>* &k3)
{SingRotateRight(k3->lson); // 2步分拆SingRotateLeft(k3); // 2步分拆
}
// 右左情况下的旋转
template<class T>
void AVLTree<T>::DoubleRotateRL(TreeNode<T>* &k3)
{SingRotateLeft(k3->lson); // 2步分拆SingRotateRight(k3);
}// 第七步：插入
/* 插入的方法和二叉查找树基本一样，区别是，插入完成后需要从插入的节点
开始维护一个到根节点的路径，每经过一个节点都要维持树的平衡。维持树的
平衡要根据高度差的特点选择不同的旋转算法。
*/
// 插入
template<class T>
void AVLTree<T>::insertpri(TreeNode<T>* &node, T x)
{if (node == NULL){// 如果节点为空，就在此节点加入x信息node = new TreeNode<T>();node->data = x;return;}// 如果x小于节点的值，就继续在节点的左子树中插入xif (node->data > x){insertpri(node->lson, x); // 迭代if (2 == height(node->lson) - height(node->rson)){if (x < node->lson->data)SingRotateLeft(node);elseDoubleRotateLR(node);}}// 如果x大于节点的值，就继续在节点的右子树中插入xelse if (node->data < x){insertpri(node->rson, x); // 迭代// 若高度之差为2，则失去平衡，需要进行旋转if (2 == height(node->rson) - height(node->lson)){if (x > node->lson->data)SingRotateRight(node);elseDoubleRotateRL(node);}}else++(node->freq); // 如果相等，就把频率加1node->hgt = Max(height(node->lson), height(node->rson)) + 1;
}// 插入接口 public
template<class T>
void AVLTree<T>::insert(T x)
{insertpri(root, x);
}// 第八步：查找
/* 和二叉查找树相比，查找方法没有变法，不过根据存储的特性，AVL树能维持在一个O(logN)的稳定的时间，而二叉查找树则相当不稳定。
*/
// 查找
template<class T>
TreeNode<T>* AVLTree<T>::findpri(TreeNode<T>* node, T x)
{// 如果节点为空说明没找到，返回NULLif (node == NULL){return NULL;}// 如果x小于节点的值，就继续在节点的左子树中查找xif (node->data > x){return findpri(node->lson, x);}// 如果x大于节点的值，就继续在节点的左子树中查找xelse if (node->data < x){return findpri(node->rson, x);}elsereturn node;
}// 查找接口
template<class T>
TreeNode<T>* AVLTree<T>::find(T x)
{return findpri(root, x);
}// 第九步：删除
/* 删除的方法也和二叉查找树的一致，区别是，删除完成后，需要从删除节点的父亲开始向上维护树的平衡一直到根节点。
*/
// 删除
template<class T>
void AVLTree<T>::Deletepri(TreeNode<T>* &node, T x)
{if (node == NULL)return; // 没有找到值是x的节点if (x < node->data){Deletepri(node->lson, x);if (2 == height(node->rson) - height(node->lson)){if (node->rson->lson != NULL && (height(node->rson->lson) > height(node->rson->rson)))DoubleRotateRL(node);elseSingRotateRight(node);}}else if (x > node->data){Deletepri(node->rson, x);if (2 == height(node->lson) - height(node->rson)){if (node->lson->rson != NULL && (height(node->lson->rson) > height(node->lson->lson)))DoubleRotateLR(node);elseSingRotateLeft(node);}}else // 如果相等，此节点就是要删除的节点{ /* 下面这个 if 没搞懂 */if (node->lson && node->rson)// 此节点有两个儿子{TreeNode<T>* temp = node->rson;while (temp->lson != NULL)temp = temp->lson;// 找到右子树中值最小的节点// 把右子树中最小节点的值赋给本节点node->data = temp->data;node->freq = temp->freq;// 删除右子树中最小值的节点Deletepri(node->rson, temp->data);if (2 == height(node->lson) - height(node->rson)){if (node->lson->rson != NULL && (height(node->lson->rson) > height(node->lson->lson)))DoubleRotateLR(node);elseSingRotateLeft(node);}}else // 此节点有1个或0个儿子{TreeNode<T>* temp = node;if (node->lson == NULL) // 有右儿子或者没有儿子node = node->rson;else if (node->rson == NULL) // 有左儿子node = node->lson;delete(temp);temp = NULL;}}if (node == NULL)return; // 此节点已经为NULL，直接返回node->hgt = Max(height(node->lson), height(node->rson))+1;return;
}// 删除接口
template<class T>
void AVLTree<T>::Delete(T x)
{Deletepri(root, x);
}// 第十步：中序遍历
/* 中序遍历函数 */
template<class T>
void AVLTree<T>::insubtree(TreeNode<T>* node)
{if (node == NULL) return;insubtree(node->lson); // 先遍历左子树cout << node->data << " "; // 输出根节点insubtree(node->rson); // 再遍历右子树
}// 中序遍历接口
template<class T>
void AVLTree<T>::traversal()
{insubtree(root);
}// 第十一步：关于效率
/* 此数据结构插入、查找和删除的时间复杂度均为O(logN),但是插入和删除
需要额外的旋转算法需要时间，有时旋转过多也会影响效率。关于递归和非递归。我用的是递归的方法进行插入，查找和删除，而递归的
方法一般来说要比递归的方法快很多，但是我感觉非递归的方法写出来会比较困
难，所以还是选择了递归的方法。还有一种效率的问题是关于高度信息的存储，由于我们需要的仅仅是高度的
差，不需要知道这棵树的高度，所以只需要使用两个二进制位就可以表示这个差。
这样可以避免平衡因子的重复计算，可以稍微的加快一些速度，不过代码也丧失*/
这篇关于【C++】【数据结构】一步一步写平衡二叉树[AVL]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
