平衡二叉搜索树＞AVL树

文章目录回顾二叉搜索树AVL树AVL树的定义AVL的插入平衡因子的调整左单旋转右单旋转右左双旋左右双旋总结回顾二叉搜索树首先我们回顾一下先前我们实现的二叉搜索树.

文章目录

• • 回顾二叉搜索树
  • AVL树
  • • AVL树的定义
    • AVL的插入
    • • 平衡因子的调整
      • 左单旋转
      • 右单旋转
      • 右左双旋
      • 左右双旋
    • 总结

回顾二叉搜索树

首先我们回顾一下先前我们实现的二叉搜索树. 首先这棵二叉树的每一个节点都满足左子树都比它小右子树都比它大。 虽然听上去似乎可以每次查找砍掉一半的搜索范围。但是实际上这个二叉搜索树的时间复杂度是O(n)! 而当数据接近有序的时候二叉搜索树就会退化成单边树或者是两边高度差的很多在这种情况下搜索树的优势就荡然无存了所以为了保持搜索树的高效性所以我们需要对搜索树的左右子树高度进行调整使得这棵树平衡。 而这样平衡的二叉树有两种,其中一种就是我们今天下面要介绍的AVL树

AVL树

AVL树是在1972年由俄罗斯的两位计算机科学家提出的二叉搜索平衡树所以这颗二叉搜索树以这两位科学家的名字命名。因此得名AVL树。现在我们都是站在巨人的肩膀上学习。而AVL树对于任意的情况下查找时间复杂度都是O(logn)可以说是一个非常优秀的数据结构。 下面我们就来深入探索一下AVL树为什么能够做到如此快速的查找。

AVL树的定义

如果一棵二叉树满足以下的几个条件那么这棵树才能算得上是AVL树

1.这是一棵二叉搜索树 2.AVL树的每一棵子树的左右子树高度差不超过1 3.空树也是AVL树

下面的这样一棵树就是AVL树 而如下的这样的一棵树就不是AVL树 接下来我们就来实现一棵AVL树并实现AVL树的插入而由于删除算法较为复杂所以后面会专门用一篇博客来讲解AVL树的删除算法。

AVL的插入

接下来我们就来实现一棵AVL树和我们先前的二叉树不一样。因为我们可能进行左右子树的平衡调整所以要求我们能够快速找到父节点因此这里我们选择实现一棵三叉链的二叉树。 同时我们记录一个平衡因子来确定是否进行平衡调整

//树的节点结构//如果不用三叉链的话可以使用一个栈来保存父节点以便进行回溯//平衡因子也不是必要但是这样设计会相对比较好实现templatestruct AVLTreeNode{pair _kv;AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent; //父节点的指针int _bf; //平衡因子记录是否需要调整//这里的explicit可选这里设计是为了防止隐式类型转换//建议单参数构造可以带上explicit AVLTreeNode(const pair//树的总体结构templateclass AVLTree{typedef AVLTreeNode Node;public:AVLTree():_root(nullptr){}private:Node* _root;

接下来我们来看分析AVL树的插入存在的情况

我们实现的AVL树是不支持重复插入的所以在插入的时候需要参看二叉树里面是否已经有存在的节点插入。 和二叉搜索树不同的是AVL树在插入的时候要严格保证自己的性质所以要时刻观察平衡因子的情况

我们先按照二叉搜索树的规则进行查找对应的插入位置

bool insert(const pair new Node(kv);return true;}Node* parent nullptr;Node* cur _root;while (cur){//如果大于就往左子树走if (cur->_kv.first > kv.first){parent cur;cur cur->_left;}//走左子树else if (cur->_kv.first _right;}//存在不插入else{return false;}}cur new Node(kv);//插入if (parent->_kv.first > kv.first){parent->_left cur;}else{parent->_right cur;}//由于是三叉链所有还要维护父亲指针cur->_parent parent;}

接下来我们就来分析插入节点以后这颗二叉搜索树会发生什么。 毫无疑问的是对于新增节点的父节点的平衡因子必然变化而平衡因子是右子树的高度减去左子树的高度。所以假如插入父节点的右那么bf就要1反之bf就要-1。 但是父亲节点可能也是一棵局部的子树因此父亲的平衡因子的变化可能会影响上层所以我们还需要进行具体分析

平衡因子的调整

设新增的节点为cur对应的父亲节点为parent 情况1经过调整后parent的平衡因子是0。 情况2parent的平衡因子经过调整后是1或者-1 情况3parent的平衡因子是2或者-2这时候平衡树的平衡性遭遇了严重的破坏需要进行旋转处理来维护子树的平衡而这也是最复杂的情况 情况4parent->_bf>2这种情况就说明原先的树的平衡就已经被破坏了。对于这种情况直接暴力断言。 接下来我们来看一看对应的旋转是如何旋转的。

左单旋转

由于子树的情况无穷无尽所以下面的图我们使用的是抽象图来代替具体的子树。虽然子树的情况很多但是我们都可以用一种统一的方式去进行处理 对应的旋转代码

void RotateL(Node* parent){ //左单旋需要右子树右子树的左子树Node* subR parent->_right;Node* subRL subR->_left;parent->_right subRL;subR->_left parent;//如果右子树的左子树非空需要维护三叉链if (subRL)subRL->_parent parent;//处理根节点的情况if (parent _root){_root subR;_root->_parent nullptr;}//局部的子树else{Node* ppNode parent->_parent;if (ppNode->_left parent){ppNode->_left subR;}else{ppNode->_right subR;}subR->_parent ppNode;}//更改父节点parent->_parent subR;subR->_bf 0;parent->_bf 0;}

右单旋转

和左单旋相似右单旋就是处理左边子树太高的情况 对应的旋转代码如下

void RotateR(Node* parent){ //右单旋需要找左子树左子树的右子树Node* subL parent->_left;Node* subLR subL->_right;parent->_left subLR;subL->_right parent;//维护三叉链if (subLR)subLR->_parent parent;//如果是根节点需要特殊处理if (parent _root){_root subL;_root->_parent nullptr;}//当前的树可能是一棵局部的子树else{ Node* ppNode parent->_parent;if (ppNode->_left parent){ppNode->_left subL;}else{ppNode->_right subL;}subL->_parent ppNode;}parent->_parent subL;subL->_bf parent->_bf 0;}

右左双旋

来看这样一种右边高的特殊情况 而这种双旋转的情况调整平衡因子就变成了一项复杂的工作平衡因子的调整关键看subL的平衡因子

情况1subRL的bf0,就是如上的图式那么parent,subR的平衡因子是0 情况2subRL的平衡因子是1旋转后的示意图如下

情况3subRL的平衡因子是-1。 对应的就是parentd->_bf0,subR->_bf1,subRL->_bf0 对应的代码如下

//右左双旋void RotateRL(Node* parent){Node* subR parent->_right;Node* subRL subR->_left;int bf subRL->_bf;RotateR(parent->_right);RotateL(parent);//调整平衡因子if (bf 0){parent->_bf 0;subR->_bf 0;subRL->_bf 0;}else if (bf 1){parent->_bf -1;subR->_bf 0;subRL->_bf 0;}else if (bf -1){parent->_bf 0;subR->_bf 1;subRL->_bf 0;}else{assert(false);}}

左右双旋

同样如下这种情况单旋转不能够调整平衡所以我们需要进行双旋。

情况1subLR->_bf0 ,那么经过旋转后对应的平衡因子调整为parent->_bf0,subL->_bf0,subLR->_bf0 情况2: subLR->_bf1,那么旋转后的结果如下 对应的处理平衡因子parent->_bf0,subL->_bf1,subLR->_bf0

情况3subLR->_bf-1,对应的情况如下 对应的调整为parent->_bf1,subL->_bf0,subLR->_bf0

完整的代码如下

//左右双旋的代码void RotateLR(Node* parent){Node* subL parent->_left;Node* subLR subL->_right;int bf subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf 0){parent->_bf 0;subL->_bf 0;subLR->_bf 0;}else if (bf 1){parent->_bf 0;subL->_bf -1;subLR->_bf 0;}else if (bf -1){parent->_bf 1;subL->_bf 0;subLR->_bf 0;}else{assert(false);}}

插入的完整代码

//插入bool insert(const pair new Node(kv);return true;}Node* parent nullptr;Node* cur _root;while (cur){//如果大于就往左子树走if (cur->_kv.first > kv.first){parent cur;cur cur->_left;}//走左子树else if (cur->_kv.first _right;}//存在不插入else{return false;}}cur new Node(kv);//插入if (parent->_kv.first > kv.first){parent->_left cur;}else{parent->_right cur;}cur->_parent parent;//调整平衡因子while (parent){if (cur parent->_left){parent->_bf--;}else{parent->_bf;}//平衡因子调整if (parent->_bf 0){break;}else if (abs(parent->_bf) 1){//继续向上调整cur parent;parent parent->_parent;}//旋转处理else if (abs(parent->_bf) 2){if (parent->_bf 2 1){RotateL(parent);}else if (parent->_bf -2 -1){RotateR(parent);}else if (parent->_bf 2 -1){RotateRL(parent);}else if (parent->_bf -2 1){RotateLR(parent);}break;}//走不到这里,走到这里先前就不是平衡树else{assert(false);}}return true;}

总结

AVL树是一棵绝对平衡的二叉树它查找的效率是O(logn), 但是由于插入的时候会频繁的旋转这会导致性能的消耗。而标准库里面的set和map容器采用的则是红黑树关于红黑树的具体细节我们将会在下一篇博客里面详细介绍。