文章目录

• 1、什么是AVL树？
• 2、AVL树部分模块模拟实现
• • 2.1 AVL树结点的定义：
  • 2.2 AVL树的插入
  • 2.3 AVL的验证

1、什么是AVL树？

  AVL树可以是一棵空树
  AVL树也可以是一棵具有如下性质的二叉搜索树：
    ①它的左右子树都是一棵AVL树
    ②左右子树高度之差（平衡因子）的绝对值不能超过1

如果一棵二叉搜索树是高度平衡的，那么他就是AVL树。
如果他有n个结点，其高度可以保持在O(log₂n),搜索时时间复杂度也就是O(log₂n)

2、AVL树部分模块模拟实现

2.1 AVL树结点的定义：

AVL树本质上讲，它是一棵二叉搜索树，只不过加上了平衡因子这一限制条件。

也就是说，在插入一个新节点时，我们不仅要考虑结点的插入位置，还需要考虑插入该节点后对于树中其他结点来说，平衡因子是否需要更新。

其中，插入节点的父节点，它的平衡因子一定需要改变。这就要求我们需要能够快速定位到插入节点的父节点。因此，我们对于AVL树结点的结构应定义为孩子双亲表示法

🆗，下面给出结点的基本结构：

template<class T>struct AVLTreeNode{typedef AVLTreeNode<T> Node;Node* _left;//左孩子Node* _right;//右孩子Node* _parent;//双亲T _value;int _bf;//结点的平衡因子AVLTreeNode(const T& value):_left(nullptr),_right(nullptr),_parent(nullptr),_value(value),_bf(0){}}

2.2 AVL树的插入

AVL树的插入可以分为两大步骤：

①按照二叉搜索树的方式插入新节点
  第一步不是本文的重点，不了解的童鞋移步至二叉搜索树

②调整结点的平衡因子

1、现在我们先给出实现第一部分的核心代码：

if (nullptr == _root){//这是一棵空树，直接插入结点即可_root = new Node(value);return true;}//1、按照二叉搜索树的方式查找结点的插入位置Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_value == value){return false;}else if (cur->_value > value){parent = cur;cur = cur->_left;}else{parent = cur;cur = cur->_right;}}Node* newNode = new Node(value);if (value > parent->_value){parent->_right = newNode;}else{parent->_left = newNode;}newNode->_parent = parent;

2、更新双亲的平衡因子
分析：
  首先，新节点插入之后，其双亲结点的平衡因子一定需要跟新，因为，插入一个结点，则该节点一定会影响其双亲的左右子树高度。因此，我们首先将双亲结点的平衡因子进行更新；

  对parent的平衡因子更新完毕后，parent的平衡因子可能的取值是：
0 、正负1、正负2。我们下面就这三种大情况分别讨论：

情况1：parent的平衡因子为0
  该情况说明插入之前parent的平衡因子为正负1，插入之后被调整成为0，此时满足AVL树的性质，插入成功！

情况2：parent的平衡因子为正负1
  该情况说明插入之前parent的平衡因子一定是0（也就是说以parent为u根的二叉树左右子树高度是一样的）,
  插入后被更新为正负1，此时以parent为根的树高度增加了，势必会影响到parent上面结点的平衡因子，因此需要继续向上跟新。

情况3：parent的平衡因子为正负2
 该种情况较为复杂。首先，我们可以知道此时parent的平衡因子违反了AVL树的特性，因此需要对齐进行旋转处理。至于如何旋转，我们分以下几种场景进行讨论：
  场景一：新节点插入在较高左子树的左侧----->右单旋
具体场景如下图所示：

具体操作见代码：

void RotateRight(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;subL->_right = parent;if (subLR){subLR->_parent = parent;}//更新subL和parent的双亲Node* pparent = parent->_parent;parent->_parent = subL;subL->_parent = pparent;//处理pparentif (nullptr == pparent){_root == subL;}else {if (pparent->_left == parent){pparent->_left = subL;}else{pparent->_right = subL;}}//跟新subL和parent的平衡因子subL->_bf = parent->_bf = 0;}

  场景二：新节点插入在较高右子树的右侧----->左单旋

具体操作见代码：

void RotateLeft(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;//更新parent && subR的双亲Node* pparent = parent->_parent;parent->_parent = subR;subR->_parent = pparent;//处理pparentif (nullptr == pparent){_root = subR;}else{if (pparent->_left == parent){pparent->_left == subR;}else{pparent->_right = subR;}}//跟新subR && parent的平衡因子subR->_bf = parent->_bf = 0;}

  场景三：新节点插入在较高左子树的右侧----->左右双旋

具体代码：

void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateLeft(parent->_left);RotateRight(parent);if (1 == bf){subL->_bf = -1;}else if (-1 == bf){parent->_bf = 1;}}

  场景四：新节点插入在较高右子树的左侧----->右左双旋
此场景类比场景三，这里直接给出代码：

void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateRight(parent->_right);RotateLeft(parent);if (1 == bf)parent->_bf = -1;else if (-1 == bf)subR->_bf = 1;}

2.3 AVL的验证

AVL树是在二叉搜索树的基础上增加了平衡因子，因此我们可以从两方面进行验证：
  1、验证是否是一棵二叉搜索树
思路：查看中序遍历结果，若有序，则为二叉搜索树

  2、验证它是否是一棵平衡树
思路：每个节点的高度差不超过1

int GetHigh(Node* root){if (nullptr == root)return 0;int leftHigh = GetHigh(root->_left);int rightHigh = GetHigh(root->_right);return leftHigh > rightHigh ? leftHigh + 1 : rightHigh + 1;}bool _IsAVLTree(Node* root){if (nullptr == root){return true;}int leftHigh = GetHigh(root->_left);int rightHigh = GetHigh(root->_right);if (rightHigh - leftHigh != root->_bf || abs(root->_bf) > 1){cout << "Node:" << root->_value << endl;cout << rightHigh - leftHigh << " " << root->_bf << endl;return false;}// 根的左子树 和 根的右子树return _IsAVLTree(root->_left) &&_IsAVLTree(root->_right);}

以上就是AVL树插入模块的模拟实现与验证。具体源码请参考AVL模拟

妊娠纹产品大全