建个大型网站需,h5生成app,wordpress搜索代码,百度企业认证怎么认证文章目录 上文链接一、什么是 AVL 树二、AVL 树的实现1. 引入平衡因子2. 整体结构3. AVL 树中的插入操作(1) 插入节点(2) 更新平衡因子更新规则停止更新条件 4. 旋转(1) 旋转的目的(2) 右单旋(3) 左单旋(4) 左右双旋(5) 右左双旋 5. AVL 树的查找与删除6. AVL 树的平衡检测 三、… 文章目录 上文链接一、什么是 AVL 树二、AVL 树的实现1. 引入平衡因子2. 整体结构3. AVL 树中的插入操作(1) 插入节点(2) 更新平衡因子更新规则停止更新条件 4. 旋转(1) 旋转的目的(2) 右单旋(3) 左单旋(4) 左右双旋(5) 右左双旋 5. AVL 树的查找与删除6. AVL 树的平衡检测 三、完整代码下文链接 上文链接 【C】map 容器的使用 一、什么是 AVL 树
我们都知道二叉搜索树它的搜索效率很高可以达到 O ( log N ) O(\operatorname{log}N) O(logN)。但是极端情况下一棵二叉搜索树可能退化成一个链表就使得搜索的效率变成 O ( N ) O(N) O(N)。 那么有没有什么办法可以让这个二叉搜索树左右两端 “保持平衡”不让它退化成链表呢答案是肯定的这就是我们要讲的 AVL 树。
AVL 树是最先发明的自平衡的二叉搜索树AVL 树具备以下特点 可以是一棵空树 它的左右子树都是 AVL 树 左右子树的高度差的绝对值不超过 1。 也就是说AVL 树的任意一个子树的左右子树的高度差的绝对值都不超过 1这样平衡之后我们搜索的效率就可以控制在 O ( log N ) O(\operatorname{log}N) O(logN)相比普通的二叉搜索树有了本质的提升。 二、AVL 树的实现
1. 引入平衡因子
AVL 树是一颗高度平衡的搜索二叉树通过控制高度差去控制平衡。
在 AVL 树的实现中我们引入一个平衡因子 (balance factor) 的概念每个节点都有一个平衡因子任何节点的平衡因子等于右子树的高度减去左子树的高度。也就是说任何一个节点的平衡因子都等于 0/1/-1。AVL 树并不是必须要平衡因子但是有了平衡因子可以更方便我们去观察和控制树是否平衡如同风向标一样。
下面这棵树就是一棵典型的 AVL 树。 而下面这棵树就不是一棵 AVL 树因为 10 这个节点它的左右子树的高度差超过了 1。 2. 整体结构
templateclass K, class V
struct AVLTreeNode
{// 需要 parent 指针后续更新平衡因子可以看到pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf; // 平衡因子AVLTreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public://...private:Node* _root nullptr;
};3. AVL 树中的插入操作
(1) 插入节点
在 AVL 树中插入节点的过程如下 ① 按普通二叉搜索树的规则插入节点 ② 插入新节点以后可能会导致树的高度发生变化也就可能会影响某些节点的平衡因子所以我们需要更新平衡因子。但是观察一下就会发现插入操作只会影响插入节点的祖先的平衡因子所以只需要更新从新增节点到根节点路径上节点的平衡因子即可。实际中最坏情况下要更新到根有些情况更新到中间就可以停止了具体情况我们下面再详细分析 ③ 更新平衡因子过程中没有出现某个子树不平衡平衡因子的绝对值大于 1则插入操作结束 ④ 更新平衡因子过程中如果出现不平衡对不平衡的子树需要进行旋转操作旋转的目的是调整这个子树使其平衡这个操作不会影响更上一层的平衡因子因此旋转之后插入操作结束。 (2) 更新平衡因子
更新规则
由于这里我们规定平衡因子 右子树高度 − - − 左子树高度所以插入节点后必然会增加该节点父节点 (parent) 子树的高度因此如果新增节点在 parent 的右子树那么 parent 的平衡因子 1新增节点在 parent 的左子树parent 的平衡因子 - 1。
但是这还没有结束新增节点的所有祖先的高度都有可能发生变化所以我们需要继续顺着从新增节点一直到根节点这条路径更新下去那么什么时候停止呢 停止更新条件 如果更新后 parent 的平衡因子等于 0即 parent 的平衡因子由 -1 变为 0 或者 由 1 变为 0说明更新前以 parent 为根的子树一边高一边低此时新增的节点插入在低的那边插入后以 parent 为根的子树高度不变不会影响 parent 的父亲节点的平衡因子因此停止更新。 如果更新后 parent 的平衡因子等于 1 或 -1即 parent 的平衡因子由 0 变为 1或者由 0 变为 -1说明更新前以 parent 为根的子树两边一样高。插入节点后以 parent 为根的子树一边高一边低但仍然符合平衡要求只不过高度增加了 1此时会影响 parent 的父亲节点的平衡因子所以要继续向上更新。继续向上更新的规则与停止条件同理。 如果更新后 parent 的平衡因子等于 2 或 -2即 parent 的平衡因子由 1 变为 2或者由 -1 变为 -2说明更新前 parent 子树一边高一边低新增的节点在高的那边以 parent 为根的子树高的那边更高了破坏了平衡因此需要对这棵子树进行旋转处理旋转的目的有两个 把 parent 子树调整为平衡状态降低 parent 子树的高度恢复到插入节点以前的高度。 所以旋转后也不需要继续往上更新此时停止更新。 一直更新到根更新后根的平衡因子是 0、1 或 -1 都停止更新。如果更新后为 2 或者 -2那么对整棵树旋转后停止更新。
下面是几个示例
示例一插入 -1 节点由于插入在 1 节点的左子树所以 1 节点的平衡因子 - 1。之后由于 1 节点的平衡因子变成 -1所以需要继续向上更新。更新到 3 节点时平衡因子依旧 - 1此时平衡因子变为 0根据规则此时停止更新。 示例二更新到 10 节点时平衡因子变为 2此时对以 10 节点为根的这棵子树进行旋转操作调整平衡旋转之后停止更新。 示例三一直更新到根节点无论是 0、1 或者 -1都停止更新。 bool Insert(const pairK, V kv)
{// 正常二叉搜索树插入逻辑if (_root nullptr){_root new Node(kv);return true;}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;else parent-_left cur;cur-_parent parent;// 更新平衡因子while (parent){if (cur parent-_left)parent-_bf--;elseparent-_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){// 此时不平衡需要旋转处理// ...break;}else assert(false);}return true;
}4. 旋转
(1) 旋转的目的 保持搜索树的规则 让不平衡的树变成平衡的其次降低旋转树的高度。
旋转总共分为四种左单旋/右单旋/左右双旋/右左双旋。根据不同的不平衡情况我们需要采取不同的旋转方式。 (2) 右单旋
如下图所示一棵以 10 为根的树由 a/b/c 抽象为三棵高度为 h 的子树 (h 0)a/b/c 均符合 AVL 树的要求。10 可能是整棵树的根也可能是一个整棵树中局部的子树的根。这里 a/b/c 是高度为 h 的子树 是一种概括抽象表示他代表了所有右单旋的场景。
在 a 子树中插入一个新节点导致 a 子树的高度从 h 变成 h1不断向上更新平衡因子导致 10 的平衡因子从 -1 变成 -210 为根的树左右高度差超过 1违反平衡规则。仔细观察可发现新插入的节点在失衡节点 (10 节点) 的左子树的左边这种情况可以简单记作左左型 (LL 型) 此时我们需要对以 10 为根的这棵树进行右单旋的操作。 旋转核心步骤因为 5 b子树的值 10所以将 b 变成 10 的左子树10 变成 5 的右子树5 变成这棵树新的根这样依旧符合搜索树的规则并且控制了平衡同时这棵的高度恢复到了插入之前达到了旋转的目的。10 整棵树的一个局部子树旋转后不会再影响上一层的平衡因子插入结束。
下面是一些具体的情况 右单旋的具体情况可以有无数多种是列举不完的比如下面我们可以简单分析一下 但是实际上我们并不需要关注什么 x/y/z我们只需要关注不平衡的那个节点以及采取何种旋转方式至于 a/b/c 三个子树长什么样我们并不关心。
下面是代码演示
// 在插入操作中发现不平衡时我们需要进行旋转并判断采取何种旋转方式
else if (parent-_bf 2 || parent-_bf -2)
{// 此时不平衡需要旋转处理// 插入在失衡节点的左子树的左边 -- 右单旋if(parent-_bf -2 cur-_bf -1) RotateR(parent);break;
}// 右单旋
void RotateR(Node* parent)
{Node* subL parent-_left; // 左子树Node* subLR subL-_right; // 左子树的右子树bparent-_left subLR;if (subLR) subLR-_parent parent; // 注意 b 有可能为空所以要判断一下Node* ppnode parent-_parent;subL-_right parent;parent-_parent subL;// parent 有可能是整棵树的根也可能是局部子树的根 // 如果是整棵树的根要修改 _root // 如果是局部的根指针要跟上一层链接if (parent _root) // 是整棵树的根{_root subL;subL-_parent nullptr;}else // 是局部的根{if (ppnode-_left parent) ppnode-_left subL;else ppnode-_right subL;subL-_parent ppnode;}parent-_bf subL-_bf 0;
}(3) 左单旋
如下图所示一棵以 10 为根的树由 a/b/c 抽象为三棵高度为 h 的子树 (h 0)a/b/c 均符合 AVL 树的要求。同样的10 可能是整棵树的根也可能是一个整棵树中局部的子树的根。这里 a/b/c 是高度为 h 的子树 是一种概括抽象表示他代表了所有左单旋的场景。
在 a 子树中插入一个新节点导致 a 子树的高度从 h 变成 h1不断向上更新平衡因子导致 10 的平衡因子从 1 变成 210 为根的树左右高度差超过 1违反平衡规则需要进行旋转。新插入的节点在失衡节点 (10 节点) 的右子树的右边这种情况可以简单记作右右型 (RR 型) 此时我们需要对以 10 为根的这棵树进行左单旋的操作。 左单旋和右单旋的操作方式几乎是一样的二者可以看作是一个镜像的关系。
下面是代码演示
// 在插入操作中发现不平衡时我们需要进行旋转并判断采取何种旋转方式
else if (parent-_bf 2 || parent-_bf -2)
{// ...// 插入在失衡节点的右子树的右边 -- 左单旋if (parent-_bf 2 cur-_bf 1) RotateL(parent);break;
}void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL) subRL-_parent parent;Node* ppnode parent-_parent;subR-_left parent;parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}else{if (ppnode-_left parent) ppnode-_left subR;else ppnode-_right subR;subR-_parent ppnode;}parent-_bf subR-_bf 0;
}(4) 左右双旋
在一些情况下右单旋和左单旋是无法解决不平衡问题的。比如下面的两种情况左边高时如果插入位置不是在 a 子树而是插入在b 子树b 子树高度从 h 变成 h1引发旋转右单旋后树依旧不平衡。 右单旋解决的是插入在不平衡节点的左子树的左边即纯粹的左边高但是如果插入在 b 子树中10 为根的子树不再是纯粹的左边高因为对于 10 来说是左边高而对于 5 来说是右边高此时需要用两次旋转才能解决以 5 为旋转点进行一个左单旋以 10 为旋转点再进行一个右单旋这棵树这棵树就平衡了。
像上述这种情况插入节点在不平衡节点的左子树的右边时可以记作左右型 (LR 型)此时采用左右双旋的方法去调整平衡即先对不平衡节点的左子树进行一次左单旋之后再对不平衡节点为根的子树进行一次右单旋。
具体的可以分为以下三种情况来讨论 下面是代码演示
// 在插入操作中发现不平衡时我们需要进行旋转并判断采取何种旋转方式
else if (parent-_bf 2 || parent-_bf -2)
{// ...// 插入在失衡节点的左子树的右边 -- 左右双旋if (parent-_bf -2 cur-_bf 1) RotateLR(parent);break;
}void RotateLR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf 0){subL-_bf 0;subLR-_bf 0;parent-_bf 0;}else if (bf -1){subL-_bf 0;subLR-_bf 0;parent-_bf 1;}else if (bf 1){subL-_bf -1;subLR-_bf 0;parent-_bf 0;}else assert(false);
}(5) 右左双旋
右左双旋与左右双旋几乎一样二者可以看作是一个对称的关系。当插入节点在不平衡节点的右子树的左边时可以记作右左型 (RL 型)此时采用右左双旋的方法去调整平衡即先对不平衡节点的右子树进行一次右单旋之后再对不平衡节点为根的子树进行一次左单旋。
具体可以分为以下几种情况 以下是代码演示
// 在插入操作中发现不平衡时我们需要进行旋转并判断采取何种旋转方式
else if (parent-_bf 2 || parent-_bf -2)
{// ...// 插入在失衡节点的右子树的左边 -- 右左双旋if (parent-_bf 2 cur-_bf -1) RotateRL(parent);break;
}void RotateRL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf 0){subR-_bf 0;subRL-_bf 0;parent-_bf 0;}else if (bf 1){subR-_bf 0;subRL-_bf 0;parent-_bf -1;}else if (bf -1){subR-_bf 1;subRL-_bf 0;parent-_bf 0;}else assert(false);
}5. AVL 树的查找与删除
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;else return cur;}return nullptr;
}AVL 树的删除操作这里不做重点讲解这个操作会比插入稍复杂一些但核心思路依然是走正常的二叉搜索树的删除操作 更新平衡因子 失衡时进行旋转。 6. AVL 树的平衡检测
我们实现的 AVL 树是否合格需要通过检查左右子树高度差的的程序进行反向验证同时检查一下节点的平衡因子更新是否出现了问题。
// 获取树的高度
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;
}bool _IsBalanceTree(Node* root)
{// 空树也是 AVL 树 if (nullptr root)return true;// 计算 pRoot 节点的平衡因子: 即 pRoot 左右子树的高度差 int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);int diff rightHeight - leftHeight;// 如果计算出的平衡因子与 pRoot 的平衡因子不相等// 或者 pRoot 平衡因子的绝对值超过 1则一定不是 AVL 树 if (abs(diff) 2){cout root-_kv.first ⾼度差异常 endl;return false;}if (root-_bf ! diff){cout root-_kv.first 平衡因⼦异常 endl;return false;}// pRoot 的左和右如果都是 AVL 树则该树一定是 AVL 树 return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right);
}三、完整代码
// AVLTree.h
#pragma once
#includecassert
#includeutility
#includecmathusing namespace std;templateclass K, class V
struct AVLTreeNode
{// 需要 parent 指针后续更新平衡因子可以看到pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf; // 平衡因子AVLTreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:bool Insert(const pairK, V kv){// 正常二叉搜索树插入逻辑if (_root nullptr){_root new Node(kv);return true;}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;else parent-_left cur;cur-_parent parent;// 更新平衡因子while (parent){if (cur parent-_left)parent-_bf--;elseparent-_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) RotateR(parent);else if (parent-_bf 2 cur-_bf 1) RotateL(parent);else if (parent-_bf -2 cur-_bf 1) RotateLR(parent);else if (parent-_bf 2 cur-_bf -1) RotateRL(parent);else assert(false);break;}else assert(false);}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;else return cur;}return nullptr;}void IsBalanced(){return _IsBalanced(_root);}int Height(){return _Height(_root);}private:void RotateR(Node* parent){Node* subL parent-_left; // 左子树Node* subLR subL-_right; // 左子树的右子树bparent-_left subLR;if (subLR) subLR-_parent parent; // 注意 b 有可能为空所以要判断一下Node* ppnode parent-_parent;subL-_right parent;parent-_parent subL;// parent 有可能是整棵树的根也可能是局部子树的根 // 如果是整棵树的根要修改 _root // 如果是局部的根指针要跟上一层链接if (parent _root) // 是整棵树的根{_root subL;subL-_parent nullptr;}else // 是局部的根{if (ppnode-_left parent) ppnode-_left subL;else ppnode-_right subL;subL-_parent ppnode;}parent-_bf subL-_bf 0;}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL) subRL-_parent parent;Node* ppnode parent-_parent;subR-_left parent;parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}else{if (ppnode-_left parent) ppnode-_left subR;else ppnode-_right subR;subR-_parent ppnode;}parent-_bf subR-_bf 0;}void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf 0){subL-_bf 0;subLR-_bf 0;parent-_bf 0;}else if (bf -1){subL-_bf 0;subLR-_bf 0;parent-_bf 1;}else if (bf 1){subL-_bf -1;subLR-_bf 0;parent-_bf 0;}else assert(false);}void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf 0){subR-_bf 0;subRL-_bf 0;parent-_bf 0;}else if (bf 1){subR-_bf 0;subRL-_bf 0;parent-_bf -1;}else if (bf -1){subR-_bf 1;subRL-_bf 0;parent-_bf 0;}else assert(false);}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;}bool _IsBalanceTree(Node* root){// 空树也是 AVL 树 if (nullptr root)return true;// 计算 pRoot 结点的平衡因子: 即 pRoot 左右子树的高度差 int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);int diff rightHeight - leftHeight;// 如果计算出的平衡因子与 pRoot 的平衡因子不相等// 或者 pRoot 平衡因子的绝对值超过 1则一定不是 AVL 树 if (abs(diff) 2){cout root-_kv.first 高度差异常 endl;return false;}if (root-_bf ! diff){cout root-_kv.first 平衡因子异常 endl;return false;}// pRoot 的左和右如果都是 AVL 树则该树一定是 AVL 树 return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right);}private:Node* _root nullptr;
};下文链接 【C】红黑树详解
