[数据结构 C++] AVL树的模拟实现

guduadmin311月前

[数据结构 C++] AVL树的模拟实现,在这里插入图片描述,第1张

文章目录

1、AVL树
- 1.1 AVL树的概念
- 2、AVL树节点的定义
- 3、AVL树的插入和旋转
- - 3.1 左单旋
  - - 左旋代码实现
    - 3.2 右单旋
    - - 右旋代码实现
      - 3.3 右左双旋
      - 右左双旋的代码实现
        3.4 左右双旋
        左右双旋的代码实现
        3.5 insert接口实现
        4、判断是否为AVL树
        判断AVL树的代码实现
        5、AVL树的性能
        问题引入：
        在上一篇文章中，我们提到了二叉搜索树在插入时，可能会形成单边树，会降低二叉搜索的性能。因此我们需要平衡二叉搜索树，降低二叉搜索树的高度，使得二叉搜索树趋于一颗完全二叉树的样子，这样就可以提高二叉搜索树的性能。本篇文章就来介绍一种平衡二叉树，AVL树。
        
        1、AVL树
        
        1.1 AVL树的概念
        
        二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
        一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
        
        它的左右子树都是AVL树
        左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
        如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(log N)，搜索时间复杂度O(log N)。
        我们了解了AVL树的基本规则后，下面我们来实现一下AVL树。
        2、AVL树节点的定义
        
        template struct AVLTreeNode { AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _parent; pair _kv; // 右子树 - 左子树的高度差 int _bf; // 平衡因子 AVLTreeNode(const pair& kv) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_kv(kv) ,_bf(0) {} };
        
        3、AVL树的插入和旋转
        
        AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么
        AVL树的插入过程可以分为两步：
        1. 按照二叉搜索树的方式插入新节点
        2. 调整节点的平衡因子
        当某个节点的平衡因子被修改为2的时候，就需要旋转来调节，因此就存在一下四种旋转方式：
        
        3.1 左单旋
        
        我们将左单旋的情况抽象出来，如下图所示：
        
        当 h >= 0，且parent->_bf == 2 && subR->_bf == 1时，触发左旋。
        在这个图中，只能是在 c 子树新增，才能触发左旋的条件parent->_bf == 2 && subR->_bf == 1。此时进行左旋。
        如果是在 b 子树新增，那么仅仅左旋是不够的，
        旋转步骤：将60的左树变为30的右树，将60的左树变为30，最后将parent和subR的平衡因子变为0就完成了左旋。
        
        左旋代码实现
        
        // 左单旋 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; Node* parentParent = parent->_parent; parent->_right = subRL; if (subRL) subRL->_parent = parent; subR->_left = parent; parent->_parent = subR; if (_root == parent) // 父节点就是根节点 { _root = subR; subR->_parent = nullptr; } else // 子树情况 { if (parentParent->_left == parent) { parentParent->_left = subR; } else { parentParent->_right = subR; } subR->_parent = parentParent; } // 修改平衡因子 parent->_bf = subR->_bf = 0; }
        
        3.2 右单旋
        
        我们将右单旋的情况抽象出来，如下图所示：
        当 h >= 0，且 parent->_bf == 2 && subL->_bf == -1时，触发右旋。
        在这个图中，只能是在 a子树新增，才能触发右旋的条件parent->_bf == -2 && subL->_bf == -1。此时进行右旋。
        如果是在 b 子树新增，那么仅仅右旋是不够的。
        旋转步骤：将30的右树接到60的左树并断开与30的链接，再将60接到30的右树，并将60的父节点改为3，最后再调整parent与SubL的平衡因子为0，就完成整个右旋。
        
        右旋代码实现
        
        // 右单旋 void RotateR(Node* parent) { Node* parentParent = parent->_parent; Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; parent->_parent = subL; if (_root == parent) // 父节点是根节点 { _root = subL; subL->_parent = nullptr; } else // 子树情况 { if (parentParent->_left == parent) { parentParent->_left = subL; } else { parentParent->_right = subL; } subL->_parent = parentParent; } // 修改平衡因子 parent->_bf = subL->_bf = 0; }
        
        3.3 右左双旋
        
        我们将右左双旋的所有情况抽象出来，如下图所示：
        
        右左双旋的本质是先将子树右旋，让右侧一侧高，再进行整体的左旋，这样就完成了高度的调整。
        双旋的插入位置可以是 b/c 子树，此类型插入之后就会触发右左双旋。
        旋转步骤：直接复用右旋，再复用左旋即可。不过旋转的基点不同，右旋是以subR为基点，左旋是以parent为基点旋转的。旋转就完成了，难点在于平衡因子的调节。
        平衡因子的调节：
        这里主要是记下subRL最初的平衡因子，它的平衡因子就代表了插入节点是在subRL的左边还是右边插入的，由此可以推出最终的parent与subR的平衡因子。
        
        当subRL->_bf = 1时，最后parent->_bf = -1，subR->_bf = 0，subRL->_bf = 0;
        当subRL->_bf = -1时，最后parent->_bf = 0，subR->_bf = 1，subRL->_bf = 0;
        当subRL->_bf = 0时，最后parent->_bf = 0，subR->_bf = 0，subRL->_bf = 0;
        右左双旋的代码实现
        
        // 右左双旋 void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(subR); RotateL(parent); if (bf == 0) // subRL 就是插入的 { parent->_bf = subR->_bf = subRL->_bf = 0; } else if (bf == 1) // subRL 右边边插入 { parent->_bf = -1; subR->_bf = 0; subRL->_bf = 0; } else if (bf == -1) // subRL 左边插入 { parent->_bf = 0; subR->_bf = 1; subRL->_bf = 0; } else { assert(false); } }
        
        3.4 左右双旋
        
        我们将右左双旋的所有情况抽象出来，如下图所示：
        
        左右双旋与右左双旋的思路是差不多的，我们来看看。
        左右双旋的本质是先将子树左旋，让左侧一侧高，在进行整体的右旋,这样就完成了高度的调整。
        双旋的插入位置可以是 b/c 子树，此类型插入之后就会触发左右双旋。
        旋转步骤：直接复用左旋，再复用右旋即可。不过旋转的基点不同，右旋是以subR为基点，左旋是以parent为基点旋转的。旋转就完成了，难点也是在于平衡因子的调节。
        平衡因子的调节：
        这里主要是记下subLR最初的平衡因子，它的平衡因子就代表了插入节点是在subLR的左边还是右边插入的，由此可以推出最终的parent与subL的平衡因子。
        
        当subLR->_bf = 1时，最后parent->_bf = 1，subL->_bf = 0，subLR->_bf = 0;
        当subLR->_bf = 1时，最后parent->_bf = 0，subL->_bf = -1，subLR->_bf = 0;
        当subLR->_bf = 0时，最后parent->_bf = 0，subL->_bf = 0，subLR->_bf = 0;
        左右双旋的代码实现
        
        // 左右双旋 void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(subL); RotateR(parent); if (0 == bf) { parent->_bf = subL->_bf = subLR->_bf = 0; } else if (1 == bf) { parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0; } else if (-1 == bf) { parent->_bf = 1; subL->_bf = 0; subLR->_bf = 0; } else { assert(false); } }
        
        3.5 insert接口实现
        
        bool Insert(const pair& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; // 1、先找到插入的位置 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; } } // 2、new一个节点，并与parent链接起来 cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->_right = cur; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; } // 3、调平横 —— 旋转 + 平衡因子的调节 while (parent) { if (parent->_left == cur) { parent->_bf--; } else { parent->_bf++; } if (0 == parent->_bf) { 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) { RotateRL(parent); } else if (parent->_bf == -2 && cur->_bf == 1) { RotateLR(parent); } else if (parent->_bf == -2 && cur->_bf == -1) { RotateR(parent); } // 1、旋转让这颗子树平衡了 // 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新 break; } else { assert(false); } } return true; }
        
        4、判断是否为AVL树
        
        AVL树的本质是搜索二叉树 + 平衡机制，所以验证步骤：
        1、首先判断是否为搜索树，写一个中序遍历，看看是不是升序即可；
        2、按照AVL树的性质来判断：
        
        每个节点的左右子树高度差绝对值小于等于1；
        节点的平衡因子是否正确；
        判断AVL树的代码实现
        
        bool _IsBalance(Node* pRoot) { if (pRoot == nullptr) return true; int leftHeight = _Height(pRoot->_left); int rightHeight = _Height(pRoot->_right); if (rightHeight - leftHeight != pRoot->_bf) { cout << pRoot->_kv.first << "平衡因子异常" << endl; return false; } return rightHeight - leftHeight < 2 && _IsAVLTree(pRoot->_left) && _IsAVLTree(pRoot->_right); } size_t _Height(Node* pRoot) { if (pRoot == nullptr) return 0; int leftHeight = _Height(pRoot->_left); int rightHeight = _Height(pRoot->_right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } void _InOrder(Node* pRoot) { if (pRoot == nullptr) return; _InOrder(pRoot->_left); cout << pRoot->_kv.first << " "; _InOrder(pRoot->_right); }
        
        5、AVL树的性能
        
        AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即O(log N)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。
        AVL树的实现代码放在代码仓库：https://gitee.com/xiaobai-is-working-hard-jy/data-structure/tree/master/AVLTree