网站空间登录北京 建设官方网站

1、AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

AVL树实现这里我们引入一个平衡因子(balance factor)的概念，每个结点都有一个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1，AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进⾏观察和控制树是否平衡，就像一个风向标一样。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
1、它的左右子树都是AVL树。
2、左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)。

平衡因子的计算我们统一用右边高度减去左边高度，后面的实现也是如此。当然也可以反过来。

思考一下为什么AVL树是高度平衡搜索二叉树，要求高度差不超过1，而不是高度差是0呢？0不是更好的平衡吗？画画图分析我们发现，不是不想这样设计，而是有些情况是做不到高度差是0的。比如一棵树是2个结点，4个结点等情况下，高度差最好就是1，无法作为高度差是0。而如果高度差是2/3/4…呢？也是不行的，因为这样在插入删除时的旋转调整将会非常麻烦。

下面对AVL树的效率进行分析：

---

2、AVL树的结构

节点的结构是三叉链，需要存储父节点的指针，还需要存储bf平衡因子变量。存储父节点的指针是为了在更新平衡因子的时候可以快速找到父节点。
然后我们这里就直接实现key/value模型了，所以需要两个模板参数，分别用K、V来表示，通过pair存储。

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv;int _bf;AVLTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:private:Node* _root = nullptr;
};

---

3、AVL树的插入

3.1、大概过程

这里的插入代码和我们之前写的二叉搜索树是类似的，只不过由于插入之后平衡因子可能发生变化，例如变成2/-2，那么就需要调整平衡并更新平衡因子，所以比二叉搜索树多了一步更新平衡因子的过程。

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);return false;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first)parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;// 更新平衡因子// ...return true;
}

---

3.2、更新平衡因子

更新规则：
1、新增节点在父节点的左侧，父节点的平衡因子--。
2、新增节点在父节点的右侧，父节点的平衡因子++。
3、更新后父节点的平衡因子==0，说明父节点所在的子树高度没有发生变化，不会影响祖先，不用再沿着到根节点的路径往上更新，更新结束。
4、更新后父节点的平衡因子==1/-1，说明父节点所在的子树高度发生了变化，会影响祖先，需要沿着到根节点的路径往上更新。
5、更新后父节点的平衡因子==2/-2，说明父节点所在的子树高度变化并且不平衡，需要对父节点所在的子树旋转并更新平衡因子。由于旋转后父节点所在子树高度并没有增加，所以不需要再向上更新，更新结束。
6、若更新到根节点，则停止。

---

3.3、更新平衡因子代码

while (parent)
{if (parent->_left == cur){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}break;}else{assert(false);}
}

正常情况下，节点的平衡因子要么是0，±1，±2，不会是其他值，但是说不准我们写的代码有bug，所以对于其他值我们直接assert终止程序。

---

3.4、左单旋

代码如下：

void RotateL(Node* parent)
{Node* cur = parent->_right;Node* curleft = cur->_left;Node* ppnode = parent->_parent;parent->_right = curleft;if (curleft) curleft->_parent = parent;cur->_left = parent;parent->_parent = cur;if (_root == parent){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;
}

---

3.5、右单旋

代码如下：

void RotateR(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;Node* ppnode = parent->_parent;parent->_left = curright;if (curright)curright->_parent = parent;cur->_right = parent;parent->_parent = cur;if (_root == parent){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;
}

---

3.6、右左双旋

代码如下：

void RotateRL(Node* parent)
{Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;	RotateR(cur);RotateL(parent);if (bf == 0){curleft->_bf = 0;parent->_bf = 0;cur->_bf = 0;}else if (bf == -1){curleft->_bf = 0;parent->_bf = 0;cur->_bf = 1;}else if (bf == 1){curleft->_bf = 0;parent->_bf = -1;cur->_bf = 0;}else{assert(false);}
}

这里bf==0这种情况不需要写，包括bf==1和bf==-1这两种情况中平衡因子=0的也不需要赋值，只需要写出平衡因子不为0的赋值，因为在我们写的左旋和右旋函数中已经将平衡因子修改为0了。
这里我们三种情况分别写出来是为了对应上图的分析，写出来更加清晰、好理解。

---

3.7、左右双旋

代码如下：

void RotateLR(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(cur);RotateR(parent);if (bf == 0){curright->_bf = 0;cur->_bf = 0;parent->_bf = 0;}else if (bf == -1){curright->_bf = 0;cur->_bf = 0;parent->_bf = 1;}else if (bf == 1){curright->_bf = 0;cur->_bf = -1;parent->_bf = 0;}else{assert(false);}
}

---

4、AVL树的删除

代码如下：

bool Erase(const K& key) {Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < key){parent = cur;cur = cur->_right;}else if (cur->_kv.first > key){parent = cur;cur = cur->_left;}else{if (cur->_left == nullptr)	// 左边为空{if (_root == cur){_root = cur->_right;if (_root)_root->_parent = nullptr;delete cur;return true;}}else if (cur->_right == nullptr) // 右边为空{if (_root == cur){_root = cur->_left;if (_root)_root->_parent = nullptr;delete cur;return true;}}else // 左右都不为空，寻找替换节点{parent = cur;Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}cur->_kv.first = leftMax->_kv.first;cur->_kv.second = leftMax->_kv.second;cur = leftMax;}break;}}// 找不到直接返回if (cur == nullptr) return false;Node* del = cur;Node* delParent = parent;while (parent){if (parent->_left == cur){	parent->_bf++;}else{parent->_bf--;}if (parent->_bf == 0){cur = parent;parent = parent->_parent;}else if (parent->_bf == 1 || parent->_bf == -1){break;}else if (parent->_bf == 2 || parent->_bf == -2){if (parent->_bf == -2){if (parent->_left->_bf == 0){cur = parent->_left;RotateR(parent);cur->_bf = 1;parent->_bf = -1;break;}else if (parent->_left->_bf == -1){cur = parent->_left;RotateR(parent);}else // parent->_left->_bf == 1;{cur = parent->_left->_right;RotateLR(parent);}}else // parent->_bf == 2{if (parent->_right->_bf == 0){cur = parent->_right;RotateL(parent);cur->_bf = -1;parent->_bf = 1;break;}else if (parent->_right->_bf == 1){cur = parent->_right;RotateL(parent);}else{cur = parent->_right->_left;RotateRL(parent);}}parent = cur->_parent;}else{assert(false);}}cur = del, parent = delParent;if (cur->_left == nullptr){if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;if (cur->_right)cur->_right->_parent = parent;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;if (cur->_left)cur->_left->_parent = parent;}delete cur;return true;
}

---

5、AVL树的查找

Node* Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_kv.first < key)cur = cur->_right;else if (cur->_kv.first > key)cur = cur->_left;elsereturn cur;}return nullptr;
}

---

6、AVL树的平衡检测

bool IsBalance(){return IsBalance(_root);}int Height()
{return Height(_root);
}bool IsBalance(Node* root)
{if (root == nullptr) return true;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (rightHeight - leftHeight != root->_bf){cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl;return false;}return abs(leftHeight - rightHeight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);
}int Height(Node* root)
{if (root == nullptr) return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

通过IsBalance函数来判断树中的平衡因子计算是否正确，如果存在异常就会打印输出信息。
同时为了计算平衡因子，需要求出左右高度然后相减，所以还需要实现Height函数获取树的高度。

---

7、AVL树的其他函数

这里实现构造函数、拷贝构造函数、赋值运算符重载、析构函数、中序遍历函数。基本上类似前面的二叉搜索树。

AVLTree():_root(nullptr)
{}AVLTree(const AVLTree<K, V>& t):_root(nullptr)
{_root = Copy(t._root, nullptr);
}AVLTree<K, V>& operator=(AVLTree<K, V> t)
{swap(_root, t._root);return *this;
}~AVLTree()
{Destroy(_root);
}void InOrder()
{InOrder(_root);cout << endl;
}Node* Copy(Node* root, Node* parent)
{if (root == nullptr) return nullptr;Node* copy = new Node(root->_kv);copy->_bf = root->_bf;copy->_parent = parent;copy->_left = Copy(root->_left, copy);copy->_right = Copy(root->_right, copy);return copy;
}void Destroy(Node*& root)
{if (root == nullptr) return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;
}void InOrder(Node* root)
{if (root == nullptr) return;InOrder(root->_left);cout << root->_kv.first << " ";InOrder(root->_right);
}

---

完整代码

#pragma oncetemplate<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv;int _bf;AVLTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:AVLTree():_root(nullptr){}AVLTree(const AVLTree<K, V>& t):_root(nullptr){_root = Copy(t._root, nullptr);}AVLTree<K, V>& operator=(AVLTree<K, V> t){swap(_root, t._root);return *this;}~AVLTree(){Destroy(_root);}bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return false;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first)parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;while (parent){if (parent->_left == cur){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}break;}else{assert(false);}}return true;}bool Erase(const K& key) {Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < key){parent = cur;cur = cur->_right;}else if (cur->_kv.first > key){parent = cur;cur = cur->_left;}else{if (cur->_left == nullptr)	// 左边为空{if (_root == cur){_root = cur->_right;if (_root)_root->_parent = nullptr;delete cur;return true;}}else if (cur->_right == nullptr) // 右边为空{if (_root == cur){_root = cur->_left;if (_root)_root->_parent = nullptr;delete cur;return true;}}else // 左右都不为空，寻找替换节点{parent = cur;Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}cur->_kv.first = leftMax->_kv.first;cur->_kv.second = leftMax->_kv.second;cur = leftMax;}break;}}// 找不到直接返回if (cur == nullptr) return false;Node* del = cur;Node* delParent = parent;while (parent){if (parent->_left == cur){	parent->_bf++;}else{parent->_bf--;}if (parent->_bf == 0){cur = parent;parent = parent->_parent;}else if (parent->_bf == 1 || parent->_bf == -1){break;}else if (parent->_bf == 2 || parent->_bf == -2){if (parent->_bf == -2){if (parent->_left->_bf == 0){cur = parent->_left;RotateR(parent);cur->_bf = 1;parent->_bf = -1;break;}else if (parent->_left->_bf == -1){cur = parent->_left;RotateR(parent);}else // parent->_left->_bf == 1;{cur = parent->_left->_right;RotateLR(parent);}}else // parent->_bf == 2{if (parent->_right->_bf == 0){cur = parent->_right;RotateL(parent);cur->_bf = -1;parent->_bf = 1;break;}else if (parent->_right->_bf == 1){cur = parent->_right;RotateL(parent);}else{cur = parent->_right->_left;RotateRL(parent);}}parent = cur->_parent;}else{assert(false);}}cur = del, parent = delParent;if (cur->_left == nullptr){if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;if (cur->_right)cur->_right->_parent = parent;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;if (cur->_left)cur->_left->_parent = parent;}delete cur;return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key)cur = cur->_right;else if (cur->_kv.first > key)cur = cur->_left;elsereturn cur;}return nullptr;}bool IsBalance(){return IsBalance(_root);}int Height(){return Height(_root);}void InOrder(){InOrder(_root);cout << endl;}private:Node* Copy(Node* root, Node* parent){if (root == nullptr) return nullptr;Node* copy = new Node(root->_kv);copy->_bf = root->_bf;copy->_parent = parent;copy->_left = Copy(root->_left, copy);copy->_right = Copy(root->_right, copy);return copy;}void Destroy(Node*& root){if (root == nullptr) return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}void InOrder(Node* root){if (root == nullptr) return;InOrder(root->_left);cout << root->_kv.first << " ";InOrder(root->_right);}bool IsBalance(Node* root){if (root == nullptr) return true;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (rightHeight - leftHeight != root->_bf){cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl;return false;}return abs(leftHeight - rightHeight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);}int Height(Node* root){if (root == nullptr) return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;Node* ppnode = parent->_parent;parent->_right = curleft;if (curleft) curleft->_parent = parent;cur->_left = parent;parent->_parent = cur;if (_root == parent){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;Node* ppnode = parent->_parent;parent->_left = curright;if (curright)curright->_parent = parent;cur->_right = parent;parent->_parent = cur;if (_root == parent){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}void RotateRL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;	RotateR(cur);RotateL(parent);if (bf == 0){curleft->_bf = 0;parent->_bf = 0;cur->_bf = 0;}else if (bf == -1){curleft->_bf = 0;parent->_bf = 0;cur->_bf = 1;}else if (bf == 1){curleft->_bf = 0;parent->_bf = -1;cur->_bf = 0;}else{assert(false);}}void RotateLR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(cur);RotateR(parent);if (bf == 0){curright->_bf = 0;cur->_bf = 0;parent->_bf = 0;}else if (bf == -1){curright->_bf = 0;cur->_bf = 0;parent->_bf = 1;}else if (bf == 1){curright->_bf = 0;cur->_bf = -1;parent->_bf = 0;}else{assert(false);}}
private:Node* _root = nullptr;
};