C++AVL树

2019-11-30 0 条评论 171 次阅读 0 人点赞

上一篇文章中介绍了二叉搜索树, 这是一种非常方便的数据结构, 但是二叉搜索树在处理一些特殊情况的时候会很不方便, 例如: 最差情况下,二叉搜索树退化为单支树,其平均比较次数为N / 2 。于是在此基础上, AVL诞生了, 这是一种特殊的二叉搜索树。

AVL树的概念

二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当 于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年 发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之 差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。 一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在O(logN),搜索时 间复杂度O(logN)。

AVL数的原理实现

AVL数的定义

#include <vector>
#include <stack>

namespace km{
    template <class T>
    class TreeNode{
        int m_bf;//记录平衡因子
        T m_data;
        TreeNode<T> * m_left;
        TreeNode<T> * m_right;
        TreeNode<T> * m_parent;
    public:
        TreeNode(const T &val = T()):
        m_bf(0),
        m_data(val),
        m_left(nullptr),
        m_right(nullptr),
        m_parent(nullptr){}

        template <class U>
        friend class AVLTree;
    };

    template <class T>
    class AVLTree{
        TreeNode<T> * m_root;

        void destory(TreeNode<T> *root){
            if(root){
                destory(root->m_left);
                destory(root->m_right);
                delete root;
            }
        }

    public:
        AVLTree():
            m_root(nullptr){
        }

        ~AVLTree(){
            destory(m_root);
        }

AVL数的插入

AVL树的插入是其最有魅力的一个部分, 为了保证上述条件的存在, AVL在每插入一个节点后其平衡因子都会进行判断是否发生改变, 如果出现不符合要求的情况, 就会发生旋转(左单旋, 右单旋)来保证平衡条件继续成立

        bool insert(const T &val){
            //1. 先按照二叉搜索树的规则将节点插入到AVL树中
            if(m_root == nullptr){
                m_root = new TreeNode<T>(val);
                return true;
            }

            TreeNode<T> *cur = m_root;
            TreeNode<T> * pre = nullptr;

            while (cur){
                if(val < cur->m_data){
                    pre = cur;
                    cur = cur->m_left;
                } else if(val > cur->m_data){
                    pre = cur;
                    cur = cur->m_right;
                } else {
                    return false;
                }
            }

            cur = new TreeNode<T>(val);
            if(val < pre->m_data){
                pre->m_left = cur;
            } else {
                pre->m_right = cur;
            }

            cur->m_parent = pre;

            // 2. 新节点插入后,AVL树的平衡性可能会遭到破坏,
            // 此时就需要更新平衡因子,并检测是否破坏了AVL树的平衡性
            while (pre){
                if (pre->m_left == cur){
                    pre->m_bf--;
                } else {
                    pre->m_bf++;
                }

                if(pre->m_bf == 0){
                    break;
                } else if(pre->m_bf == 1 || pre->m_bf == -1){
                    cur = pre;
                    pre = pre->m_parent;
                } else {
                    if (pre->m_bf == 2){
                        //pre的平衡因子为2, 则分为两种情况
                        if(cur->m_bf == 1){
                            //cur平衡因子为1则说明cur的右子树比左子树高1,此时左旋
                            lRound(pre);
                        } 

                        else {
                            //否则cur平衡因子为-1则说明cur的左子树比右子树高1,此时先左旋再右旋
                            rlRound(pre);
                        }

                    } else {
                        if(cur->m_bf == 1){
                            //cur平衡因子为1则说明cur的右子树比左子树高1,此时先左旋再右旋
                            lrRound(pre);
                        }

                         else {
                            //否则cur平衡因子为-1则说明cur的左子树比右子树高1,此时右旋
                            rRound(pre);
                        }
                    }
                    break;
                }
            }
            return true;
        }

std::vector<T> InOrder(){
            std::stack<TreeNode<T> *> s;
            std::vector<T> res;
            TreeNode<T> * cur = m_root;

            while (cur || !s.empty()){
                for (; cur; cur = cur->m_left){
                    s.push(cur);
                }
                if (!s.empty()){
                    cur = s.top();
                    res.push_back(cur->m_data);
                    s.pop();

                    cur = cur->m_right;
                }
            }
            return res;
        }
    };
};

AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过1,这样可以保证 查询时高效的时间复杂度,即logN 。但是如果要对AVL树做一些结构修改的操作,性能非常低下,比如: 插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,有可能一直要让旋转持续到根的位置。 因此:如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑AVL树, 但一个结构经常修改,就不太适合。

L_KingMing

这个人太懒什么东西都没留下

文章评论(0)