文档章节

AVL树的详细实现

o
 osc_g8254g7s
发布于 2019/08/19 21:00
字数 4498
阅读 9
收藏 0

精选30+云产品,助力企业轻松上云!>>>

【原文:https://cloud.tencent.com/developer/article/1155143

AVL树简介

AVL树的名字来源于它的发明作者G.M. Adelson-Velsky 和 E.M. Landis。AVL树是最先发明的自平衡二叉查找树(Self-Balancing Binary Search Tree,简称平衡二叉树)。

一棵AVL树有如下必要条件:

  1. 条件一:它必须是二叉查找树。
  2. 条件二:每个节点的左子树和右子树的高度差至多为1。

图一中左边二叉树的节点45的左孩子46比45大,不满足二叉搜索树的条件,因此它也不是一棵平衡二叉树。 右边二叉树满足二叉搜索树的条件,同时它满足条件二,因此它是一棵平衡二叉树。

左边二叉树的节点45左子树高度2,右子树高度0,左右子树高度差为2-0=2,不满足条件二; 右边二叉树的节点均满足左右子树高度差至多为1,同时它满足二叉搜索树的要求,因此它是一棵平衡二叉树。

AVL树的查找、插入、删除操作在平均和最坏的情况下都是O(logn),这得益于它时刻维护着二叉树的平衡。如果我们需要查找的集合本身没有顺序,在频繁查找的同时也经常的插入和删除,AVL树是不错的选择。不平衡的二叉查找树在查找时的效率是很低的。

AVL树相关概念

  1. 平衡因子:将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子BF(Balance Factor)。

在图二右边的AVL树上:

节点50的左子树高度为3,右子树高度为2,BF= 3-2 = 1;

节点45的左子树高度为2,右子树高度为1,BF= 2-1 = 1;

节点46的左子树高度为0,右子树高度为0,BF= 0-0 = 0;

节点65的左子树高度为0,右子树高度为1,BF= 0-1 = -1;

对于平衡二叉树,BF的取值范围为[-1,1]。如果发现某个节点的BF值不在此范围,则需要对树进行调整。

  1. 最小不平衡子树:距离插入节点最近的,且平衡因子的绝对值大于1的节点为根的子树。

图三中,左边二叉树的节点45的BF = 1,插入节点43后,节点45的BF = 2。节点45是距离插入点43最近的BF不在[-1,1]范围内的节点,因此以节点45为根的子树为最小不平衡子树。

AVL树的实现详解

节点结构

//结点类
template<typename T>
struct AVLNode
{
    T data;    //数据成员
    int height;    //树的高度
    AVLNode<T>* leftChild;
    AVLNode<T>* rightChild;
    AVLNode() :leftChild(NULL), rightChild(NULL), height(0){}
    AVLNode(T d,AVLNode<T> *l=NULL,AVLNode<T>* r=NULL):data(d),leftChild(l),rightChild(r),height(0){}
};

另外一些AVL实现的节点设计方案中,会把BF作为结点的一个属性存储起来,而在这里我们存储的是节点的高度,通过节点的高度我们也可以间接计算出节点的BF。例如节点A的左孩子的height = 2,右孩子的height = 1,那么节点A的平衡因子为2 - 1 = 1.

AVL树的高度

如前所说,我们的节点结构中并不存储结点的BF,取而代之的是节点的高度。一个节点的BF可由其左右子树的高度计算出来。我们提供返回一个节点高度的操作

//求一棵树的高度
    int Height(AVLNode<T>* cur)
    {
        if (cur == NULL)
            return 0;
        int i = Height(cur->leftChild);
        int j = Height(cur->rightChild);
        return i < j ? j + 1 : i + 1;
    }

AVL树失衡调整

节点的插入或删除都有可能导致AVL树失去平衡,因此,失衡调整是插入与删除操作的基础。 AVL树的失衡调整可以分为四种情况,我们逐一分析。 假设我们要为数组a[]={4,5,6,3,2,8,7,0,1}构建一棵AVL树。

情况一:左单旋转

首先插入{4,5,6},在插入元素6后出现不平衡的情况:

当我们在右子树插入右孩子导致AVL失衡时,我们需要进行单左旋调整。旋转围绕最小失衡子树的根节点进行。 在删除新节点时也有可能会出现需要单左旋的情况。 左旋代码如下:

AVLNode<T>* LeftRotation(AVLNode<T>* cur)
    {
        AVLNode<T>* prchid = cur->rightChild;
        cur->rightChild = prchid->leftChild;
        prchid->leftChild = cur;
        //改变了指向后,还要更新结点对应的高度
        cur->height = max(Height(cur->leftChild),Height(cur->rightChild))+1;
        prchid->height = max(Height(prchid->leftChild), Height(prchid->rightChild)) + 1;
        return prchid;
    }

结合例子进行分析:

  1. 参数cur为最小失衡子树的根节点,在图四中为节点4
  2. 若节点5有左子树,则该左子树成为节点4的右子树
  3. 节点4成为节点5的左子树
  4. 最后更新节点的高度值

情况二:右单旋转

我们继续插入元素{3,2},此时二叉树为:

插入3、2后出现了不平衡的情况。此时的插入情况是“在左子树上插入左孩子导致AVL树失衡”,我们需要进行单右旋调整。 单右旋代码为:

AVLNode<T>* RightRotation(AVLNode<T>* cur)
    {
        AVLNode<T>* plchild = cur->leftChild;
        cur->leftChild = plchild->rightChild;
        plchild->rightChild = cur;
        cur->height = max(Height(cur->leftChild), Height(cur->rightChild)) + 1;
        plchild->height = max(Height(plchild->leftChild), Height(plchild->rightChild)) + 1;
        return plchild;
    }

结合例子进行分析:

  1. 参数cur为最小失衡子树的根节点,在图四中为节点4
  2. 若节点3有右子树,则该右子树成为节点4的左子树
  3. 节点4成为节点3的左子树
  4. 调整节点的高度值

情况三:先右旋后左旋

需要进行两次旋转的原因是第一次旋转后,AVL树仍旧处于不平衡的状态,第二次旋转再次进行调整。 我们继续插入元素{8,7}

这种情况,总结起来就是“在右子树上插入左孩子导致AVL树失衡",此时我们需要进行先右旋后左旋的调整。 调整的代码为:

AVLNode<T>* RightLeftRotation(AVLNode<T> *cur)
    {
        cur->rightChild = RightRotation(cur->rightChild);
        return LeftRotation(cur);
    };

结合例子进行分析:

  1. 首先对最小不平衡子树的根节点(也就是节点6)的右孩子(也就是8)进行右旋操作
  2. 再对节点6进行一次左旋操作

情况四:先左旋后右旋

根据对称性原理,当我们“在左子树上插入右孩子导致AVL树失衡",此时我们需要进行先左旋后右旋的调整。如果你不理解接着看图。 我们接着插入节点{0,1}

调整的代码:

AVLNode<T>* LeftRightRotation(AVLNode<T> *cur)
    {
        cur->leftChild = LeftRotation(cur->leftChild);
        return RightRotation(cur);
    };

结合例子进行分析:

  1. 首先对最小不平衡子树的根节点(也就是节点2)的左孩子(也就是0)进行左旋操作
  2. 再对节点2进行一次右旋操作

总结

单左旋

在右子树插入右孩子节点,使得平衡因子绝对值由1增至2

单右旋

在左子树插入左孩子节点,使得平衡因子绝对值由1增至2

先左旋后右旋

在左子树插入右孩子节点,使得平衡因子绝对值由1增至2

先右旋后左旋

在右子树插入左孩子节点,使得平衡因子绝对值由1增至2

插入新节点

其实上面已经展示了一个完整的插入过程,结合例子很好理解下面这段代码。

AVLNode<T>* Insert(AVLNode<T>* &cur,T key)
    {
        if(cur==NULL)    //寻找插入位置
        {
            cur = new AVLNode<T>(key);
        }
        else if(key>cur->data)    //插入值比当前结点值大,插入到当前结点的右子树上
        {
            cur->rightChild = Insert(cur->rightChild, key);
            if(Height(cur->rightChild)-Height(cur->leftChild)==2)    //插入后出现失衡
            {
                if (key > cur->rightChild->data)    //情况一:插入右子树的右节点,进行左旋
                    cur = LeftRotation(cur);
                else if (key < cur->rightChild->data)    //情况三:插入右子树的左节点,进行先右再左旋转
                    cur = RightLeftRotation(cur);
            }
        }
        else if(key<cur->data)    //插入值比当前节点值小,插入到当前结点的左子树上
        {
            cur->leftChild = Insert(cur->leftChild, key);
            if(Height(cur->leftChild)-Height(cur->rightChild)==2)//如果插入导致失衡
            {
                if (key < cur->leftChild->leftChild->data)
                    cur = RightRotation(cur);    //情况二:插入到左子树的左孩子节点上,进行右旋
                else if (key > cur->leftChild->data)
                    cur = LeftRightRotation(cur);
            }
        }
        cur->height = max(Height(cur->leftChild), Height(cur->rightChild)) + 1;
        return cur;
    }

删除节点

删除节点也可能导致AVL树的失衡,实际上删除节点和插入节点是一种互逆的操作:

  1. 删除右子树的节点导致AVL树失衡时,相当于在左子树插入节点导致AVL树失衡,即情况情况二或情况四。
  2. 删除左子树的节点导致AVL树失衡时,相当于在右子树插入节点导致AVL树失衡,即情况情况一或情况三。

另外,AVL树也是一棵二叉排序树,因此在删除节点时也要维护二叉排序树的性质。

删除的代码实现:

AVLNode<T>* Remove(AVLNode<T>* &cur,T key)
    {
        if(cur!=NULL)    //找到删除的节点
        {
            if(key==cur->data)     //找到删除的节点
            {
                //因AVL也是二叉排序树,删除节点要维护其二叉排序树的条件
                if(cur->leftChild!=NULL&&cur->rightChild!=NULL)    //有两个孩子
                {
                    //左子树比右子树高
                    if(Height(cur->leftChild)>Height(cur->rightChild))
                    {
                        AVLNode<T>* pmax = maximum(cur->leftChild);
                        cur->data = pmax->data;
                        cur->leftChild = Remove(cur->leftChild, pmax->data);
                    }
                    else  //左子树比右子树低
                    {
                        AVLNode<T>* pmin = minimum(cur->rightChild);
                        cur->data = pmin->data;
                        cur->rightChild = Remove(cur->rightChild, pmin->data);
                    }
                }
                else  //只有一个孩子,直接让这个孩子结点取代当前结点
                {
                    AVLNode<T>* pTemp = cur;
                    if (cur->leftChild != NULL)
                        cur = cur->leftChild;
                    else if (cur->rightChild != NULL)
                        cur = cur->rightChild;
                    delete pTemp;
                    return NULL;
                }
            }
            else if (key>cur->data)    //要删除的节点比当前节点大,则在右子树进行删除
            {
                cur->rightChild = Remove(cur->rightChild, key);
                if (Height(cur->leftChild) - Height(cur->rightChild) == 2)    //删除右子树节点导致不平衡:相当于情况二或情况四
                {
                    if (Height(cur->leftChild->rightChild) > Height(cur->leftChild->leftChild))
                        cur = LeftRightRotation(cur);    //相当于情况四
                    else
                        cur = RightRotation(cur);    //相当于情况二
                }
            }
            else if(key<cur->data)    //要删除的节点比当前节点小,则在左子树进行删除
            {
                cur->leftChild = Remove(cur->leftChild, key);
                //右子树比左子数高
                if(Height(cur->rightChild)-Height(cur->leftChild)==2)    //删除左子树节点导致不平衡:相当于情况三或情况一
                {
                    //右子树左边高导致不平衡,要先右旋,在左旋调整
                    if (Height(cur->rightChild->leftChild) > Height(cur->rightChild->rightChild))
                        cur = RightLeftRotation(cur);
                    else
                        cur = LeftRotation(cur);
                }
            }
            return cur;
        }
        return NULL;
    }
  1. 删除节点时,如果节点同时拥有左子树和右子树,则在高度教低的子树上选择最大(或最小)元素进行替换,这样能保证替换后不会再出现失衡的现象。

至此,AVL树较为复杂的部分都已经分析完毕。剩下的其他操作是普通的二叉排序树共通的操作。为了完整性,我们简单说一下代码。

查找元素

二叉树是一种递归的定义,因此,二叉树的许多操作都可以通过递归简单地实现,例如遍历二叉树、查找指定元素、销毁二叉树等。 基于二叉排序树的特殊性质, 元素查找操作也能够使用非递归算法简单地实现,我们提供递归与非递归两种版本的元素查找算法。

AVLNode<T>* SearchRecurse(AVLNode<T>* cur,T key)
    {
        if(cur!=NULL)
        {
            if (key == cur->data)
                return cur;
            if (key > cur->data)
                return SearchRecurse(cur->rightChild, key);
            else
                return SearchRecurse(cur->leftChild, key);
        }
        return NULL;
    }

    AVLNode<T>* SearchIterator(AVLNode<T>* cur,T key)
    {
        while (cur!=NULL)
        {
            if (cur->data == key)
                return cur;
            else if (key > cur->data)
                cur = cur->rightChild;
            else
                cur = cur->leftChild;
        }
        return NULL;
    }

AVL树的销毁

采用后序遍历AVL树来销毁二叉树。即先销毁根节点的左子树,然后销毁根节点的右子树,最后才销毁根节点。

void Destroy(AVLNode<T>* &cur)
    {
        if(cur!=NULL)
        {
            Destroy(cur->leftChild);
            Destroy(cur->rightChild);
            delete cur;
            cur = NULL;
        }
    }

求最大最小值

二叉排序树的最小值位于最左节点,最大值位于其最右节点。

//返回以cur为根的最大结点的地址
    AVLNode<T>* maximum(AVLNode<T>* cur)
    {
        if(cur!=NULL)
        {
            while (cur->rightChild!=NULL)
            {
                cur = cur->rightChild;
            }
            return cur;
        }
        return NULL;
    }

    //返回以cur为根的最小结点的地址
    AVLNode<T>* minimum(AVLNode<T>* cur)
    {
        if(cur!=NULL)
        {
            while (cur->leftChild=NULL)
            {
                cur = cur->leftChild;
            }
            return cur;
        }
        return NULL;
    }

完整代码

//结点类
template<typename T>
struct AVLNode
{
    T data;    //数据成员
    int height;    //树的高度
    AVLNode<T>* leftChild;
    AVLNode<T>* rightChild;
    AVLNode() :leftChild(NULL), rightChild(NULL), height(0){}
    AVLNode(T d,AVLNode<T> *l=NULL,AVLNode<T>* r=NULL):data(d),leftChild(l),rightChild(r),height(0){}
};

//AVL类型
template<typename T>
class AVLTree
{
public:
    //构造空树
    AVLTree():root(NULL){}

    //析构函数
    ~AVLTree() { Destroy(root); }

    //递归方式查找
    AVLNode<T>* SearchRecurse(T key) { return SearchRecurse(root, key); }

    //非递归(迭代)方式查找
    AVLNode<T>* SearchIterator(T key) { return SearchIterator(root,key); }

    //插入
    bool Insert(T key) { return Insert(root, key); }
    
    //删除
    bool Remove(T key) { return Remove(root, key); }
    
    //求高度
    int Height() { return Height(root); }
    
    //返回两个中较大的数
    int max(int a, int b) { return a > b ? a : b; }
    
    //中序遍历
    void InOrder() { InOrder(root); }

    //以广义表的形式输出二叉树(前序遍历的应用)
    void PrintBinTree() { PrintBinTree(root); }

private:

    /*左旋转操作*/
    /*cur为最小失衡子树的根节点*/
    /*返回旋转后的根节点*/
    /*
     *     9
     *    / \
     *   6   12            
     *  /      \   
     * 3        15
     *         /  \
     *        13   19
     */
    AVLNode<T>* LeftRotation(AVLNode<T>* cur)
    {
        AVLNode<T>* prchid = cur->rightChild;
        cur->rightChild = prchid->leftChild;
        prchid->leftChild = cur;
        //改变了指向后,还要更新结点对应的高度
        cur->height = max(Height(cur->leftChild),Height(cur->rightChild))+1;
        prchid->height = max(Height(prchid->leftChild), Height(prchid->rightChild)) + 1;
        return prchid;
    }

    /*右旋转操作*/
    /*cur为最小失衡子树的根节点*/
    /*返回旋转后的根节点*/
    /*
    *       9
    *      / \
    *     6   12
    *    /     \
    *   3       15
    *  / \       
    * 1   4   
    */
    AVLNode<T>* RightRotation(AVLNode<T>* cur)
    {
        AVLNode<T>* plchild = cur->leftChild;
        cur->leftChild = plchild->rightChild;
        plchild->rightChild = cur;
        cur->height = max(Height(cur->leftChild), Height(cur->rightChild)) + 1;
        plchild->height = max(Height(plchild->leftChild), Height(plchild->rightChild)) + 1;
        return plchild;
    }

    /*先左后右做旋转*/
    /*参数cur为最小失衡子树的根节点*/
    /*返回旋转后的根节点*/
    AVLNode<T>* LeftRightRotation(AVLNode<T> *cur)
    {
        cur->leftChild = LeftRotation(cur->leftChild);
        return RightRotation(cur);
    };

    /*先右旋再左旋*/
    /*参数cur为最小失衡子树的根节点*/
    /*返回旋转后的根节点*/
    AVLNode<T>* RightLeftRotation(AVLNode<T> *cur)
    {
        cur->rightChild = RightRotation(cur->rightChild);
        return LeftRotation(cur);
    };

/*
 *     8
 *    / \
 *   3   10
 */
    //插入结点
    AVLNode<T>* Insert(AVLNode<T>* &cur,T key)
    {
        if(cur==NULL)    //寻找插入位置
        {
            cur = new AVLNode<T>(key);
        }
        else if(key>cur->data)    //插入值比当前结点值大,插入到当前结点的右子树上
        {
            cur->rightChild = Insert(cur->rightChild, key);
            if(Height(cur->rightChild)-Height(cur->leftChild)==2)    //插入后出现失衡
            {
                if (key > cur->rightChild->data)    //情况一:插入右子树的右节点,进行左旋
                    cur = LeftRotation(cur);
                else if (key < cur->rightChild->data)    //情况三:插入右子树的左节点,进行先右再左旋转
                    cur = RightLeftRotation(cur);
            }
        }
        else if(key<cur->data)    //插入值比当前节点值小,插入到当前结点的左子树上
        {
            cur->leftChild = Insert(cur->leftChild, key);
            if(Height(cur->leftChild)-Height(cur->rightChild)==2)//如果插入导致失衡
            {
                if (key < cur->leftChild->leftChild->data)
                    cur = RightRotation(cur);    //情况二:插入到左子树的左孩子节点上,进行右旋
                else if (key > cur->leftChild->data)
                    cur = LeftRightRotation(cur);
            }
        }
        cur->height = max(Height(cur->leftChild), Height(cur->rightChild)) + 1;
        return cur;
    }

    /*
    *     8
    *    / \
    *   3   10
    *  /\   /\  
    * 1  6 9  11
    */
    //删除结点
    AVLNode<T>* Remove(AVLNode<T>* &cur,T key)
    {
        if(cur!=NULL)    //找到删除的节点
        {
            if(key==cur->data)     //找到删除的节点
            {
                //因AVL也是二叉排序树,删除节点要维护其二叉排序树的条件
                if(cur->leftChild!=NULL&&cur->rightChild!=NULL)    //有两个孩子
                {
                    //左子树比右子树高
                    if(Height(cur->leftChild)>Height(cur->rightChild))
                    {
                        AVLNode<T>* pmax = maximum(cur->leftChild);
                        cur->data = pmax->data;
                        cur->leftChild = Remove(cur->leftChild, pmax->data);
                    }
                    else  //左子树比右子树低
                    {
                        AVLNode<T>* pmin = minimum(cur->rightChild);
                        cur->data = pmin->data;
                        cur->rightChild = Remove(cur->rightChild, pmin->data);
                    }
                }
                else  //只有一个孩子,直接让这个孩子结点取代当前结点
                {
                    AVLNode<T>* pTemp = cur;
                    if (cur->leftChild != NULL)
                        cur = cur->leftChild;
                    else if (cur->rightChild != NULL)
                        cur = cur->rightChild;
                    delete pTemp;
                    return NULL;
                }
            }
            else if (key>cur->data)    //要删除的节点比当前节点大,则在右子树进行删除
            {
                cur->rightChild = Remove(cur->rightChild, key);
                if (Height(cur->leftChild) - Height(cur->rightChild) == 2)    //删除右子树节点导致不平衡:相当于情况二或情况四
                {
                    if (Height(cur->leftChild->rightChild) > Height(cur->leftChild->leftChild))
                        cur = LeftRightRotation(cur);    //相当于情况四
                    else
                        cur = RightRotation(cur);    //相当于情况二
                }
            }
            else if(key<cur->data)    //要删除的节点比当前节点小,则在左子树进行删除
            {
                cur->leftChild = Remove(cur->leftChild, key);
                //右子树比左子数高
                if(Height(cur->rightChild)-Height(cur->leftChild)==2)    //删除左子树节点导致不平衡:相当于情况三或情况一
                {
                    //右子树左边高导致不平衡,要先右旋,在左旋调整
                    if (Height(cur->rightChild->leftChild) > Height(cur->rightChild->rightChild))
                        cur = RightLeftRotation(cur);
                    else
                        cur = LeftRotation(cur);
                }
            }
            return cur;
        }
        return NULL;
    }

    //求一棵树的高度
    int Height(AVLNode<T>* cur)
    {
        if (cur == NULL)
            return 0;
        int i = Height(cur->leftChild);
        int j = Height(cur->rightChild);
        return i < j ? j + 1 : i + 1;
    }
    
    //返回以cur为根的最大结点的地址
    AVLNode<T>* maximum(AVLNode<T>* cur)
    {
        if(cur!=NULL)
        {
            while (cur->rightChild!=NULL)
            {
                cur = cur->rightChild;
            }
            return cur;
        }
        return NULL;
    }

    //返回以cur为根的最小结点的地址
    AVLNode<T>* minimum(AVLNode<T>* cur)
    {
        if(cur!=NULL)
        {
            while (cur->leftChild=NULL)
            {
                cur = cur->leftChild;
            }
            return cur;
        }
        return NULL;
    }

    //中序遍历
    void InOrder(AVLNode<T>* cur)
    {
        if(cur!=NULL)
        {
            InOrder(cur->leftChild);
            cout << cur->data << " ";
            InOrder(cur->rightChild);
        }
    }

    //以广义表形式输出二叉树
    void PrintBinTree(AVLNode<T>* BT)
    {
        if (BT != NULL) //树为空时结束递归
        {
            cout << BT->data;
            if (BT->leftChild != NULL || BT->rightChild != NULL)
            {
                cout << '(';
                if (BT->leftChild != NULL)
                {
                    PrintBinTree(BT->leftChild);
                }
                cout << ',';
                if (BT->rightChild != NULL)
                {
                    PrintBinTree(BT->rightChild);
                }
                cout << ')';
            }
        }
    }
    
    //销毁
    void Destroy(AVLNode<T>* &cur)
    {
        if(cur!=NULL)
        {
            Destroy(cur->leftChild);
            Destroy(cur->rightChild);
            delete cur;
            cur = NULL;
        }
    }

    //递归查找
    AVLNode<T>* SearchRecurse(AVLNode<T>* cur,T key)
    {
        if(cur!=NULL)
        {
            if (key == cur->data)
                return cur;
            if (key > cur->data)
                return SearchRecurse(cur->rightChild, key);
            else
                return SearchRecurse(cur->leftChild, key);
        }
        return NULL;
    }

    //非递归查找
    AVLNode<T>* SearchIterator(AVLNode<T>* cur,T key)
    {
        while (cur!=NULL)
        {
            if (cur->data == key)
                return cur;
            else if (key > cur->data)
                cur = cur->rightChild;
            else
                cur = cur->leftChild;
        }
        return NULL;
    }

private:
    AVLNode<T>* root;
};

测试代码

int main()
{
    AVLTree<int> t;
    for (int i = 0; i < 10; i++)
        t.Insert(i);
    cout <<"树高:"<< t.Height()<<endl;
    t.PrintBinTree();
    t.Remove(5);
    cout << endl;
    t.PrintBinTree();
    cout << endl;
    cout << t.SearchRecurse(7)->data << endl;
    cout << t.SearchIterator(6)->data << endl;
    return 0;
}
上一篇: 关于重绘和回流
下一篇: jmeter+jenkins+git+ant
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
AVL-平衡二叉树的原理和实现

一、简介   本文将通过图解和代码详细讲解AVL平衡二叉树的性质及失衡和再平衡的内容。在看本文之前希望大家具备二分搜索树的相关知识。或移步《二分搜索树》了解二分搜索树。 二、平衡二叉...

osc_ab70hsav
04/16
4
0
数据结构与算法之10(AVL自平衡二叉树与RB红黑树)

本节继续总结二叉树的变种,上节里的哈夫曼树是一种独特的二叉树,用于编解码会比较有效。这里的两种树都是BST二叉搜索树的加强版。 》BST二叉搜索树的弱点 我们之前也提到了,当插入序列是有...

kkae8643150
2017/12/01
0
0
AVL树和平衡二叉树 平衡因子 右旋转LL 左旋转RR LR RL

  前言   今天要介绍几种高级数据结构AVL树,介绍之前AVL,会先说明平衡二叉树,并将树的学习路线进行总结,并介绍维持平衡的方法:右旋转、左旋转。   一、树学习路线   1、路线总结...

osc_ymlf86ez
2018/10/31
2
0
树、二叉树、二叉查找树、AVL树、红黑树、B-树、B+树、trie树综述

AVL树,红黑树,B树,B+树,Trie树都分别应用在哪些现实场景中? 参考知乎知友的回答AVL树,红黑树,B树,B+树,Trie树现实应用场景 AVL树:windows对进程地址空间的管理用到了AVL树。 红黑树...

jacksu在简书
2018/02/19
0
0
数据结构与算法(九):AVL树详细讲解

数据结构与算法(一):基础简介 数据结构与算法(二):基于数组的实现ArrayList源码彻底分析 数据结构与算法(三):基于链表的实现LinkedList源码彻底分析 数据结构与算法(四):基于哈希表实现HashM...

osc_keofad7g
2018/12/11
1
0

没有更多内容

加载失败,请刷新页面

加载更多

macz技巧分享—macOS高端使用技巧

Macos 的占有量不如 Windows,两者之间当操作方式也有很大的不同,当很多人熱悉 Windows 的操作之后,再接触 macos,觉得难上手,其实是习惯问题。如果你学习一些技巧,会觉得 macos 其实也不...

mac小叮当
56分钟前
11
0
手把手教你如何用黑白显示器显示彩色!

来源:大数据文摘 本文约1000字,建议阅读6分钟。 本文为你介绍如何通过黑白显示器上也能显示出彩色。 原来在黑白显示器上也能显示出彩色啊!通过在监视器上覆盖拜耳滤色镜,并拼接彩色图像,...

osc_jklrr90y
56分钟前
18
0
key-value结构排序:给定一个字符串,统计每个字符出现频率,先按value降序,再按key升序

对于key-value结构的排序 第一种:lambda表达式 第二种:函数 第三种:类对()的重载,仿函数形式 #include <iostream>#include <vector>#include <unordered_map>#include <string>#in......

osc_gwtkg2dc
57分钟前
0
0
BlockChain:2020年7月10日世界人工智能大会WAIC《链智未来 赋能产业区块链主题论坛——2020全球区块链创新50强》

BlockChain:2020年7月10日世界人工智能大会WAIC《链智未来 赋能产业区块链主题论坛——2020全球区块链创新50强》 目录 世界人工智能大会WAIC《链智未来 赋能产业区块链主题论坛——2020全球...

osc_vew1u0h0
59分钟前
0
0
BlockChain:2020年7月10日世界人工智能大会WAIC《链智未来 赋能产业区块链主题论坛》(三)

BlockChain:2020年7月10日世界人工智能大会WAIC《链智未来 赋能产业区块链主题论坛》(三) 目录 2020年7月10日世界人工智能大会WAIC《链智未来 赋能产业区块链主题论坛》 演讲嘉宾 演讲内容 ...

osc_8o71811p
59分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部