站多多 福州网站建设,做网站的学校有哪些,济南建网站送400电话,南京电信网站备案文章目录 高度平衡二叉搜索树实现一颗AVL树结点与树的描述——定义类AVL树的插入操作步骤1#xff1a;按照二叉搜索树的方法插入结点步骤2#xff1a;自底向上调整平衡因子步骤3#xff1a;触发旋转操作#xff08;AVL树平衡的精髓#xff09;右单旋左单旋左右双旋右左双旋… 文章目录 高度平衡二叉搜索树实现一颗AVL树结点与树的描述——定义类AVL树的插入操作步骤1按照二叉搜索树的方法插入结点步骤2自底向上调整平衡因子步骤3触发旋转操作AVL树平衡的精髓右单旋左单旋左右双旋右左双旋 验证AVL树是否平衡 参考文章 高度平衡二叉搜索树
二叉搜索树是一种特殊的树形数据结构一般情况下该树能够缩短查找的效率但是它有个缺陷在结点的插入或删除顺序较为特殊时结构会退化成链表导致搜索、插入和删除等操作的时间复杂度从O(log n)退化到O(n)。
【二叉搜索树退化成链表的例子】
高度平衡二叉搜索树是针对二叉搜索树的缺陷所发明出来的一种改良结构。
高度平衡二叉搜索树常被称为 “ AVL树 ”这主要是为了纪念发明它两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.LandisAVL是两位数学家的名字的缩写。
一颗AVL树或者是空树或者是具有以下性质的二叉搜索树
左右子树高度之差简称为平衡因子的绝对值不超过1。在这里平衡因子的求法定义为右子树的高度 - 左子树的高度。结点的左右两棵子树也都是一棵平衡二叉树。 实现一颗AVL树
概念部分讲的差不多了至于AVL树相较于二叉搜索树是如何保持平衡结构就在接下来的实现过程中一步步讲解。
结点与树的描述——定义类
namespace ljh
{templateclass K, class Vstruct AVLTreeNode{AVLTreeNode(const pairK, V kv) : _kv(kv) {}AVLTreeNodeK, V* _parent nullptr; // A pointer to nodes fatherAVLTreeNodeK, V* _left nullptr; // A pointer to nodes left childAVLTreeNodeK, V* _right nullptr; // A pointer to nodes right childint _bf 0; // balance factorpairK, V _kv; // key-value};templateclass K, class Vclass AVLTree{typedef AVLTreeNodeK, V Node;public:// AVL树的操作方法protected:Node* _root nullptr;};
}【说明】
模板化设计 使用templateclass K, class V来定义AVLTreeNode和AVLTree使得该数据结构能够处理任意类型的键Key和值Value提高了代码的复用性和灵活性。K代表键的类型V代表值的类型。使用者可以根据自己的需求在AVL树存储任何类型的键值对。 AVLTreeNode类 AVLTreeNode结构体定义了AVL树中每个节点的结构用struct定义是为了方便在树类访问。_parent指针指向父节点用于在旋转等操作中快速定位父节点记住这里的旋转这将是后面的重点。_left和_right指针分别指向左孩子和右孩子是二叉树结构的基础。_bf平衡因子存储节点的平衡因子用于衡量树是否平衡。_kv存储于结点中的键值对其中K是键的类型V是值的类型。 构造函数 AVLTreeNode的构造函数接收一个pairK, V对象并初始化_kv成员变量。这样当创建新节点时可以方便地传入键值对。 AVLTree类 AVLTree类代表整个AVL树结构。typedef AVLTreeNodeK, V Node;在内部使用定义了一个类型别名Node目的是简化代码书写。_root指针指向AVL树的根节点是整棵树的入口点。 保护成员 _root成员变量被设计为protected意味着它只能在AVLTree类及其派生类中被访问。这种设计是为了将AVL树的内部实现细节隐藏起来而只暴露必要的公共接口给外部使用。 命名空间 为了方便使用库函数使用using namespace std;展开标准库但这容易引发同名类或函数发生冲突因而将所有定义放在ljh命名空间中。
AVL树的插入操作
AVL树的插入操作实现起来大致分成以下三个大步骤
步骤1按照二叉搜索树的方法插入结点
树为空则构造新结点让_root 指针指向该结点返回true。树不空按key的大小寻找插入位置如果已存在按插入失败处理返回false。走到空表示找到合适位置然后插入构造的新结点插入时要判断左边插入或者右边插入。
此时插入并未结束接下来进行步骤二的平衡因子更新操作
【步骤1的代码如下】
bool insert(pairK, V kv)
{// empty tree - 直接插入if(_root nullptr){_root new Node(kv);return true;}// not empty tree - 找到合适的位置再插入else{Node* child _root;Node* parent nullptr;while (child){// 大往右走if (child-_kv.first kv.first){parent child;child child-_right;}// 小往左走else if (child-_kv.first kv.first){parent child;child child-_left;}// 相同插入失败else{return false;}}// child nullptr, 找到合适的位置child new Node(kv);if (child-_kv.first parent-_kv.first) parent-_right child;else parent-_left child;child-_parent parent;// 自底向上更新平衡因子// ...}
}步骤2自底向上调整平衡因子
我们将新插入结点称为child新插入结点的双亲结点称为parent。
平衡因子的更新规则如下
如果child是parent的左孩子parent的平衡因子-1。如果child是parent的右孩子parent的平衡因子1。
这是第一次更新更新完之后要不要继续向上更新取决于以parent为根结点的这棵树的高度是否变化情况有以下3种 平衡因子更新后parent的平衡因子为0 这意味着parent-_bf是从-1 - 0或者 从1 - 0以parent为根结点的这棵树的高度没有发生变化不用再向上更新平衡因子可以返回true表示插入成功。 平衡因子更新后parent的平衡因子为-1或1 这意味着parent-_bf是从0 - -1或者 从0 - 1以parent为根结点的这棵树的高度发生了变化但还没有达到需要旋转的程度。 在这种情况下更新child child-_parent更新parent parent-_parent继续更新parent 的平衡因子直到情况1找到平衡因子为0的节点或者情况2到达根节点parent nullptr。 平衡因子更新后parent的平衡因子为-2或2 这意味着此时以parent为根结点的这棵树已经违反了AVL树的规则需要进行旋转处理处理完之后可以直接返回true。
【步骤2的代码如下】
// 自底向上更新平衡因子
while (parent)
{if (child parent-_left){--parent-_bf;}else{parent-_bf;}if (parent-_bf 0){return true;}else if (parent-_bf 1 || parent-_bf -1){child child-_parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){// 违反规则旋转处理// ...}else{// 理论上没错误不会走到这里assert(false);}
}步骤3触发旋转操作AVL树平衡的精髓
根据节点插入位置的不同AVL树的旋转分为以下4种
由于具象图的种类繁多根本不可能画得完下面AVL树旋转的图解中大多画的是抽象图。
右单旋
这里给出了一棵以结点90作为根节点的AVL树的抽象图图中 a / b / c 代表三棵高度为 h 的子树。 这颗AVL树的左子树高度高于右子树高度。 首先以90为根结点的这棵树有三种可能
它是某棵AVL树的左子树它是某棵AVL树的右子树它就是AVL树的根结点 当新结点插入在了较高左子树的左侧即 a 子树时child 和 parent 自底向上更新平衡因子当出现parent-_bf -2, child-_bf -1时该树违反了AVL树的规则需要进行右单旋操作。 在右单旋中涉及到改变链接关系的结点主要有以下4个 当 a / b / c 3棵子树高度为零时插入新结点平衡因子为 -2 的结点向右旋转
当 a / b / c 3棵子树高度不为零时插入新结点平衡因子为 -2 的结点向右旋转 【右单旋操作的代码如下】
void R_Rotate(Node* parent)
{Node* ppnode parent-_parent;Node* subL parent-_left;Node* subLR subL-_right;// subL and parentsubL-_right parent;parent-_parent subL;// parent and subLRparent-_left subLR;if (subLR) subLR-_parent parent;// ppnode and subLif (ppnode nullptr){_root subL;subL-_parent nullptr;}else{subL-_parent ppnode;if (parent ppnode-_left){ppnode-_left subL;}else{ppnode-_right subL;}}parent-_bf subL-_bf 0;
}左单旋
这里给出了一棵以结点30作为根节点的AVL树的抽象图图中 a / b / c 代表三棵高度为 h 的子树。 这颗AVL树的右子树高度高于左子树高度。 首先以30为根结点的这棵树有三种可能
它是某棵AVL树的左子树它是某棵AVL树的右子树它就是AVL树的根结点 当新结点插入在了较高右子树的右侧即 c 子树时child 和 parent 自底向上更新平衡因子当出现parent-_bf 2, child-_bf 1时该树违反了AVL树的规则需要进行左单旋操作。 在左单旋中涉及到改变链接关系的结点同样有4个 当 a / b / c 3棵子树高度为零时插入新结点平衡因子为 2 的结点向左旋转
当 a / b / c 3棵子树高度不为零时插入新结点平衡因子为 2 的结点向左旋转 【左单旋操作的代码如下】
void L_Rotate(Node* parent)
{Node* ppnode parent-_parent;Node* subR parent-_right;Node* subRL subR-_left;// subR and parentsubR-_left parent;parent-_parent subR;// parent and subRLparent-_right subRL;if (subRL) subRL-_parent parent;//ppnode and subRif (ppnode nullptr){_root subR;subR-_parent nullptr;}else{subR-_parent ppnode;if (parent ppnode-_left){ppnode-_left subR;}else{ppnode-_right subR;}}parent-_bf subR-_bf 0;
}左右双旋
这里给出了一棵以结点90作为根节点的AVL树的抽象图图中 a / b / c / d 代表四棵子树。 这颗AVL树的左子树高度高于右子树高度。 首先以90为根结点的这棵树有三种可能
它是某棵AVL树的左子树它是某棵AVL树的右子树它就是AVL树的根结点 下面三种情况都有一个共同给特点就是parent-_bf -2, child-_bf 1。 我们不难发现左右双旋可以视为先左旋再右旋即结点30先左旋结点90再右旋。 单旋中的subLR不管怎么操作它的平衡因子都是 0但是在双旋中subLR有可能是 -1、0、1中任意一种因此虽然双旋操作我们可以复用单旋的代码但是双旋之后的平衡因子调整需要单独处理。
【左右双旋的代码如下】
void LR_Rotate(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;// 双旋之后要靠bf来更新平衡因子int bf subLR-_bf;L_Rotate(subL);R_Rotate(parent);if (bf 0){subLR-_bf 0;subL-_bf 0;parent-_bf 0;}else if (bf -1){subLR-_bf 0;subL-_bf 0;parent-_bf 1;}else{subLR-_bf 0;subL-_bf -1;parent-_bf 0;}
}右左双旋
这里给出了一棵以结点30作为根节点的AVL树的抽象图图中 a / b / c / d 代表四棵子树。 这颗AVL树的右子树高度高于左子树高度。 首先以30为根结点的这棵树有三种可能
它是某棵AVL树的左子树它是某棵AVL树的右子树它就是AVL树的根结点 下面三种情况都有一个共同给特点就是parent-_bf 2, child-_bf -1。 我们不难发现右左双旋可以视为先右旋再左旋即结点90先右旋结点30再左旋。 单旋中的subRL不管怎么操作它的平衡因子都是 0但是在双旋中subRL有可能是 -1、0、1中任意一种因此虽然双旋操作我们可以复用单旋的代码但是双旋之后的平衡因子调整需要单独处理。
【右左双旋的代码如下】
void RL_Rotate(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;// 双旋之后要靠bf来更新平衡因子int bf subRL-_bf;R_Rotate(subR);L_Rotate(parent);if (bf 0){subRL-_bf 0;parent-_bf 0;subR-_bf 0;}else if (bf -1){subRL-_bf 0;parent-_bf 0;subR-_bf 1;}else{subRL-_bf 0;parent-_bf -1;subR-_bf 0;}
}验证AVL树是否平衡 虽然目前已经将AVL树的插入操作的代码已经写出来了但是仅仅是写出来了一定能够保证代码就是正确的吗——肯定不是
所以接下来还要再实现一个方法来验证一棵AVL树是不是平衡的。
AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步
验证其为二叉搜索树 如果中序遍历可得到一个有序的序列就说明为二叉搜索树。验证其为平衡树 每个结点子树高度差的绝对值不超过1注意节点中如果没有平衡因子。 结点的平衡因子是否计算正确。
【写法一代码简单但是效率低】
// 求AVL树的高度
size_t _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;
}size_t Height()
{return _Height(_root);
}bool _IsBalance(Node* root)
{// 空树也是AVL树if (root nullptr) return true;// 计算root节点的平衡因子即root左右子树的高度差int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);// 如果计算出的平衡因子与pRoot的平衡因子不相等或者// root平衡因子的绝对值超过1则一定不是AVL树int diff rightHeight - leftHeight;if (abs(diff) 2){cout root-_kv.first 不平衡 endl;return false;}if (diff ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}// root的左和右如果都是AVL树则该树一定是AVL树return _IsBalance(root-_left) _IsBalance(root -_right);
}【写法二代码效率高但是相较写法一难理解】
// 判断AVL树是否平衡高效
bool _IsBalance(Node* root, int height)
{// 空树也是AVL树if (root nullptr){height 0;return true;}// 后序递归leftHeight、rightHeight会分别获取root的左右子树的高度int leftHeight 0, rightHeight 0;if (!_IsBalance(root-_left, leftHeight) || !_IsBalance(root-_right, rightHeight)){return false;}// 如果高度差的绝对值 2AVL树不平衡int diff rightHeight - leftHeight;if (abs(diff) 2){cout root-_kv.first 不平衡 endl;return false;}// 如果高度差 ! root-_bfAVL树插入过程中的平衡因子更新有问题if (diff ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}// 将root自己的高度通过引用返回给上一层栈帧height leftHeight rightHeight ? leftHeight 1 : rightHeight 1;// root的左子树平衡、右子树平衡、root自身也平衡那这棵AVL树就平衡return true;
}参考文章 数据结构 —— 图解AVL树(平衡二叉树) 高度平衡二叉搜索树AVLTree 【数据结构】AVL树的删除解析有点东西哦
