Loading... > 在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(logn）。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL 树得名于它的发明者 G. M. Adelson-Velsky 和 Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。 ——Wiki ##1. 为什么要有平衡二叉树 二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序时，例如序列 A = {1，2，3，4，5，6}，构造二叉搜索树。依据此序列构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为 O(n)。 为了避免这种“退化”，改善查找效率，就可以使用平衡二叉树。 ##2. 定义 **平衡二叉查找树**：简称平衡二叉树。由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树，根据科学家的英文名也称为 AVL 树。它具有如下几个性质： 1. 可以是空树。 2. 假如不是空树，任何一个节点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。 平衡之意，如天平，即两边的分量大约相同。 ##3. 平衡因子 **定义**：某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子（BF,Balance Factor），平衡二叉树中不存在平衡因子大于 1 的节点。在一棵平衡二叉树中，节点的平衡因子只能取 0 、1 或者 -1 ，分别对应着左右子树等高，左子树比较高，右子树比较高。 ###二叉树的深度 我最开始没理解平衡因子就是理解错了这个深度。深度的定义如下： > 根节点到这个节点所经历的边的个数。 记不住的话可以想象生活中的例子。比如水中的深度，一般是从上往下计量的。所以深度是从上向下的。 (图示后面再补吧QAQ) ##4. AVL树插入的失衡与调整 **最小失衡子树**：在新插入的节点向上查找，以第一个平衡因子的绝对值超过 1 的节点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。 平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。根据旋转的方向有两种处理方式，`左旋` 与 `右旋` 。 旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。 ###4.1 左旋 对节点进行左旋操作，流程如下： 1. 节点的右孩子替代此节点位置 2. 右孩子的左子树变为该节点的右子树 3. 节点本身变为右孩子的左子树 ####代码实现 ```cpp /***************************************************************** Function:LeftRotate Description：左旋。 *****************************************************************/ Node* AVL::LeftRotate(Node * node) { Node* parent = node->parent; Node* left_child = node->left; Node* right_child = node->right; //判断右节点的左孩子 if (right_child->left != nullptr) right_child->left->parent = node; //改变node的右孩子 node->right = right_child->left; update_depth(node);//更新node节点的深度 //将node和right_child接在一起 right_child->left = node; node->parent = right_child; update_depth(right_child);//更新right_child节点深度 //如果父节点存在，修改父节点的关系 if (parent != nullptr) { if (parent->left == node) parent->left = right_child; else parent->right = right_child; } right_child->parent = parent;//更新right_child的父亲 update_depth(right_child);//更新右节点深度 return right_child; } ``` ###4.2 右旋 右旋操作与左旋类似，操作流程为： 1. 节点的左孩子代表此节点 2. 节点的左孩子的右子树变为节点的左子树 3. 将此节点作为左孩子节点的右子树。 ####代码实现 ```cpp /***************************************************************** Function:RightRotate Description：右旋。 *****************************************************************/ Node* AVL::RightRotate(Node * node) { Node* parent = node->parent; Node* left_child = node->left; Node* right_child = node->right; //判断左节点的右孩子 if (left_child->right != nullptr) left_child->right->parent = node; //改变node的左孩子 node->left = left_child->right; update_depth(node);//更新深度 //将node和left_child接在一起 node->parent = left_child; left_child->parent = parent; //如果父节点存在，修改父节点的关系 if (parent != nullptr) { if (parent->left = node) parent->left = left_child; else parent->right = left_child; } left_child->parent = parent;//更新父节点 update_depth(left_child); return left_child; } ``` ##5. AVL树的插入 ###5.1 AVL树的四种插入节点方式 假设一颗 AVL 树的某个节点为 A，有四种操作会使 A 的左右子树高度差大于 1，从而破坏了原有 AVL 树的平衡性。平衡二叉树插入节点的情况分为以下四种： | 插入方式 | 描述 | 旋转方式 | | ------------ | ------------ | ------------ | | LL | 在A的左子树的左节点上插入节点而破坏平衡 | 右旋 | | RR | 在A的右子树的右节点上插入节点而破坏平衡 | 左旋 | | LR | 在A的左子树的右节点上插入节点而破坏平衡 | 先左旋后右旋 | | RL | 在A的右子树的左节点上插入节点而破坏平衡 | 先右旋后左旋 | ###5.2 插入代码实现 ```cpp /***************************************************************** Function:insert Description：插入一个节点。 *****************************************************************/ inline Node* AVL::__insert(Node * node, int data) { if (node == nullptr) return new Node(data); //根据值的大小递归判断插入位置 if (data > node->value) __insert(node->right, data); else if (data < node->value) __insert(node->left, data); else //如果有重复的就返回当前节点 return node; update_depth(node);//更新当前节点深度 int factor = balance_factors(node);//平衡因子 if (factor > 1 && data < node->left->value) return RightRotate(node);//LL型最小失衡树 else if (factor < -1 && data > node->right->value) return LeftRotate(node);//RR型最小失衡树 else if (factor > 1 && data > node->left->value) {//LR型最小失衡树 LeftRotate(node->left); return RightRotate(node); } else if (factor < -1 && data < node->right->value) {//RL型最小失衡树 RightRotate(node->right); return LeftRotate(node); } return node; } inline bool AVL::insert(int data) { if (find(data) != nullptr) return false; __insert(root, data); SIZE++; return true; } ``` ###5.3 一些总结 - 在所有的不平衡情况中，都是按照先 **寻找最小不平衡树**，然后 **寻找所属的不平衡类别**，再 **根据 4 种类别进行固定化程序的操作**。 - LL , LR ，RR ，RL其实已经为我们提供了最后哪个节点作为新的根指明了方向。如 LR 型最后的根节点为原来的根的左孩子的右孩子，RL 型最后的根节点为原来的根的右孩子的左孩子。只要记住这四种情况，可以很快地推导出所有的情况。 - 维护平衡二叉树，最麻烦的地方在于平衡因子的维护。可以自己动手画一遍加深印象。 ##6.AVL树的删除 一般的二叉树删除有三种情况： 1. 删除的节点为叶节点； 2. 删除的节点仅有一颗子树； 3. 删除的节点有两颗子树； AVL树也是一颗二叉搜索树，只是多了一个平衡性质。所以AVL树的删除和二叉搜索树差不多，但是因为其平衡性质需要进行平衡处理。 ###删除代码实现 ```cpp /***************************************************************** Function:erase Description：删除一个节点。 *****************************************************************/ inline Node * AVL::__erase(Node * node, int data) { if (node == nullptr) return node; //递归找到需删除的节点 if (data < node->value) __erase(node->left, data); else if (data > node->value) __erase(node->right, data); else { if (node->left == nullptr || node->right == nullptr) {//node为叶节点或node仅有一个孩子 Node* son = node->left == nullptr ? node->right : node->left; //处理node的父节点 if (node->parent->left == node) node->parent->left = son; else node->parent->right = son; if (son != nullptr)//如果有儿子则修改 son->parent = node->parent; delete node;//直接删除node return son; } else //有两个儿子的时候 {//这里使用前驱或者后继都可以。我使用的是后继 node->value = find_successor(node)->value; //因为使用的是后继所以从右儿子继续 __erase(node->right, node->value); } } /*以下操作是为了恢复AVL树的平衡性*/ if (node == nullptr) return node; int factor = balance_factors(node); //这两个用 >= 是为了保证一次旋转就可以平衡 if (factor > 1 && balance_factors(node->left) >= 0) return RightRotate(node);//LL型最小失衡树 else if (factor < -1 && balance_factors(node->right) <= 0) return LeftRotate(node);//RR型最小失衡树 else if (factor > 1 && balance_factors(node->left) < 0) {//LR型最小失衡树 LeftRotate(node->left); return RightRotate(node); } else if (factor < -1 && balance_factors(node->right) < 0) {//RL型最小失衡树 RightRotate(node->right); return LeftRotate(node); } return node; } inline Node* AVL::erase(int data) { Node* tmp = find(data); if (tmp == nullptr) return false; SIZE--; return __erase(root, data); } inline Node* AVL::erase(Node * node) { if (node == nullptr) return nullptr; SIZE--; return __erase(root, node->value); } ``` ##7. 整体代码 这是我在学习时写的代码，我还没有测试，如果发现了BUG请在评论区留言或和我私聊。欢迎指教。 ```cpp #include <vector> #include <queue> #include <algorithm> using namespace std; struct Node { int depth;//树的深度 int value; Node* parent = nullptr; Node* left = nullptr; Node* right = nullptr; Node() :depth(0), value(0) { } Node(int n) :depth(0), value(n) { } void clear() { depth = value = 0; parent = nullptr; left = right = nullptr; } }; class AVL { private: Node* root; int SIZE; private: /*左旋，右旋*/ Node* LeftRotate(Node* node); Node* RightRotate(Node* node); /*插入, 删除*/ Node* __insert(Node* node, int data); Node* __erase(Node* node, int data); /*三序遍历*/ void __preorderTraversal(Node* node, vector<int> &res); void __inorderTraversal(Node* node, vector<int> &res); void __postorderTraversal(Node* node, vector<int> &res); /*一些辅助函数*/ int balance_factors(Node* node);//获取平衡因子 void update_depth(Node* node);//更新当前节点深度 public: /*构造，析构*/ AVL() :SIZE(0) { } AVL(vector<int> data); ~AVL(); /*插入*/ bool insert(int data); /*删除*/ Node* erase(int data); Node* erase(Node* node); void clear(); /*查找*/ Node* find(int data); /*寻找前驱, 后继*/ Node* find_predecesser(Node* node); Node* find_successor(Node* node); /*树信息*/ int size() { return SIZE; } int depth(Node* node) { return node == nullptr ? 0 : node->depth; } bool empty() { return SIZE == 0; } Node* begin() { return root; } /*三序遍历*/ vector<int> preorderTraversal(Node* node); vector<int> inorderTraversal(Node* node); vector<int> postorderTraversal(Node* node); }; /***************************************************************** Function:AVL Description：构造函数，将data里面的数据输入到树中。 *****************************************************************/ AVL::AVL(vector<int> data) { for (auto n : data)//C++11支持的冒号遍历 insert(n); //auto的作用是自动选择相应的类型 return; } /***************************************************************** Function:~AVL Description：析构函数。 *****************************************************************/ AVL::~AVL() { clear(); delete root; return; } /***************************************************************** Function:LeftRotate Description：左旋。 *****************************************************************/ inline Node* AVL::LeftRotate(Node * node) { Node* parent = node->parent; Node* left_child = node->left; Node* right_child = node->right; //判断右节点的左孩子 if (right_child->left != nullptr) right_child->left->parent = node; //改变node的右孩子 node->right = right_child->left; update_depth(node);//更新node节点的深度 //将node和right_child接在一起 right_child->left = node; node->parent = right_child; update_depth(right_child);//更新right_child节点深度 //如果父节点存在，修改父节点的关系 if (parent != nullptr) { if (parent->left == node) parent->left = right_child; else parent->right = right_child; } right_child->parent = parent;//更新right_child的父亲 update_depth(right_child);//更新右节点深度 return right_child; } /***************************************************************** Function:RightRotate Description：右旋。 *****************************************************************/ inline Node* AVL::RightRotate(Node * node) { Node* parent = node->parent; Node* left_child = node->left; Node* right_child = node->right; //判断左节点的右孩子 if (left_child->right != nullptr) left_child->right->parent = node; //改变node的左孩子 node->left = left_child->right; update_depth(node);//更新深度 //将node和left_child接在一起 node->parent = left_child; left_child->parent = parent; //如果父节点存在，修改父节点的关系 if (parent != nullptr) { if (parent->left = node) parent->left = left_child; else parent->right = left_child; } left_child->parent = parent;//更新父节点 update_depth(left_child); return left_child; } /***************************************************************** Function:insert Description：插入一个节点。 *****************************************************************/ inline Node* AVL::__insert(Node * node, int data) { if (node == nullptr) return new Node(data); //根据值的大小递归判断插入位置 if (data > node->value) __insert(node->right, data); else if (data < node->value) __insert(node->left, data); else //如果有重复的就返回当前节点 return node; update_depth(node);//更新当前节点深度 int factor = balance_factors(node);//平衡因子 if (factor > 1 && data < node->left->value) return RightRotate(node);//LL型最小失衡树 else if (factor < -1 && data > node->right->value) return LeftRotate(node);//RR型最小失衡树 else if (factor > 1 && data > node->left->value) {//LR型最小失衡树 LeftRotate(node->left); return RightRotate(node); } else if (factor < -1 && data < node->right->value) {//RL型最小失衡树 RightRotate(node->right); return LeftRotate(node); } return node; } inline bool AVL::insert(int data) { if (find(data) != nullptr) return false; __insert(root, data); SIZE++; return true; } /***************************************************************** Function:erase Description：删除一个节点。 *****************************************************************/ inline Node * AVL::__erase(Node * node, int data) { if (node == nullptr) return node; //递归找到需删除的节点 if (data < node->value) __erase(node->left, data); else if (data > node->value) __erase(node->right, data); else { if (node->left == nullptr || node->right == nullptr) {//node为叶节点或node仅有一个孩子 Node* son = node->left == nullptr ? node->right : node->left; //处理node的父节点 if (node->parent->left == node) node->parent->left = son; else node->parent->right = son; if (son != nullptr)//如果有儿子则修改 son->parent = node->parent; delete node;//直接删除node return son; } else //有两个儿子的时候 {//这里使用前驱或者后继都可以。我使用的是后继 node->value = find_successor(node)->value; //因为使用的是后继所以从右儿子继续 __erase(node->right, node->value); } } /*以下操作是为了恢复AVL树的平衡性*/ if (node == nullptr) return node; int factor = balance_factors(node); //这两个用 >= 是为了保证一次旋转就可以平衡 if (factor > 1 && balance_factors(node->left) >= 0) return RightRotate(node);//LL型最小失衡树 else if (factor < -1 && balance_factors(node->right) <= 0) return LeftRotate(node);//RR型最小失衡树 else if (factor > 1 && balance_factors(node->left) < 0) {//LR型最小失衡树 LeftRotate(node->left); return RightRotate(node); } else if (factor < -1 && balance_factors(node->right) < 0) {//RL型最小失衡树 RightRotate(node->right); return LeftRotate(node); } return node; } inline Node* AVL::erase(int data) { Node* tmp = find(data); if (tmp == nullptr) return false; SIZE--; return __erase(root, data); } inline Node* AVL::erase(Node * node) { if (node == nullptr) return nullptr; SIZE--; return __erase(root, node->value); } /***************************************************************** Function:clear Description：清空树。 *****************************************************************/ inline void AVL::clear() {//利用了广搜的思想遍历删除 if (root == nullptr) return; queue<Node*> q; q.push(root); while (!q.empty()) { Node* tmp = q.front(); q.pop(); if (tmp->left != nullptr) q.push(tmp->left); if (tmp->right != nullptr) q.push(tmp->right); delete tmp; SIZE--; } root->clear(); return; } /***************************************************************** Function:find Description：查找值为data的节点。 *****************************************************************/ inline Node * AVL::find(int data) {//二分搜索 if (root == nullptr) return nullptr; Node* tmp = root; while (tmp != nullptr) { if (tmp->value == data) return tmp; else if (data > tmp->value) tmp = tmp->right; else if (data < tmp->value) tmp = tmp->left; } return nullptr; } /***************************************************************** Function:find_predecessor Description：查找节点的前驱。 节点x的前驱，就是指value小于x节点中value最大的那个节点 若x的左子树不为空，则x前驱是x节点左子树里最靠右的那个节点 如果x的左子树为空，那么我们就要向上找x的第一个有右孩子且左子树里 没有x节点的祖先。 *****************************************************************/ inline Node * AVL::find_predecesser(Node * node) { if (node == nullptr) return nullptr; Node* tmp = node; if (node->left != nullptr) { tmp = node->left; while (tmp->right != nullptr) tmp = tmp->right; return tmp; } while (tmp->parent != nullptr && tmp->parent->left != tmp) tmp = tmp->parent; return tmp->parent; } /***************************************************************** Function:find_predecessor Description：查找节点的后继。 节点x的后继，就是指value大于x节点中value最小的那个节点 若x的右子树不为空，则x后继是x节点右子树里最靠左的那个节点 如果x的右子树为空，那么我们就要向上找x的第一个有左孩子且右子树里 没有x节点的祖先。 *****************************************************************/ inline Node * AVL::find_successor(Node * node) { if (node == nullptr) return nullptr; Node* tmp = node; if (node->right != nullptr) { tmp = node->right; while (tmp->left != nullptr) tmp = tmp->left; return tmp; } while (tmp->parent != nullptr && tmp->parent->right != tmp) tmp = tmp->parent; return tmp->parent; } /***************************************************************** Function:balance_factors Description：获取当前节点的平衡因子。 *****************************************************************/ inline int AVL::balance_factors(Node * node) { if (node == nullptr) return 0; return depth(node->left) - depth(node->right); } /***************************************************************** Function:update_depth Description：更新当前节点深度，为旋转做准备。 *****************************************************************/ inline void AVL::update_depth(Node * node) { if (node == nullptr) return; if (node->left == nullptr && node->right == nullptr) node->depth = 0;//叶节点的深度为0 else node->depth = max(depth(node->left), depth(node->right)) + 1; return; } /***************************************************************** Function:preorderTraversal Description：前序遍历。 *****************************************************************/ inline void AVL::__preorderTraversal(Node* node, vector<int> &res) { if (node) { res.push_back(node->value); __preorderTraversal(node->left, res); __preorderTraversal(node->right, res); } return; } inline vector<int> AVL::preorderTraversal(Node* node) { vector<int> res; __preorderTraversal(node, res); return res; } /***************************************************************** Function:inorderTraversal Description：中序遍历。 *****************************************************************/ inline void AVL::__inorderTraversal(Node* node, vector<int> &res) { if (node) { __inorderTraversal(node->left, res); res.push_back(node->value); __inorderTraversal(node->right, res); } return; } inline vector<int> AVL::inorderTraversal(Node* node) { vector<int> res; __inorderTraversal(node, res); return res; } /***************************************************************** Function:postorderTraversal Description：后序遍历。 *****************************************************************/ inline void AVL::__postorderTraversal(Node* node, vector<int> &res) { if (node) { __postorderTraversal(node->left, res); __postorderTraversal(node->right, res); res.push_back(node->value); } return; } inline vector<int> AVL::postorderTraversal(Node* node) { vector<int> res; __postorderTraversal(node, res); return res; } ``` ##8.随便写写 这个平衡二叉树花了我两三天才算是比较弄懂它的实现方法。这里有个小插曲，那个插入和删除的参考代码，我写完后才发现是JAVA的(捂脸)。在写的时候也踩了许多坑。我想了很多不可能出现的情况，然后就写不下去了，到最后才发现根本不存在这些问题。到最后想想还是不够仔细啊。 最后修改：2019 年 07 月 31 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏