精华内容
下载资源
问答
  • 平衡二叉树或者是棵空树,或者是具体下列性质的二叉查找树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的高度只差的绝对值不超过1。若将二叉树结点的平衡因子定义为该节点的左子树的高度减去它的右子树的...

    概念

    平衡二叉树或者是棵空树,或者是具体下列性质的二叉查找树:它的左子树右子树都是平衡二叉树,且左子树和右子树的高度只差的绝对值不超过1。若将二叉树结点的平衡因子定义为该节点的左子树的高度减去它的右子树的高度,则所有结点的平衡因子只可能为-1,0,1。只要有一个结点的平衡因子的绝对值大于1,那么这棵树就失去了平衡

    平衡二叉树的目的是:

    为了防止二叉排序树的最后坏的情况(当先后插入的关键字有序时,构成的二叉排序树蜕变为单支树,树的深度为其平均查找长度(n+1)/2(和顺序查找相同),时间复杂度为O(n))。

    也就是将二叉排序树处于最好的情况(二叉排序树的形态和折半查找的判定树相同,其平均查找长度和log 2 (n)成正比。算法时间复杂度为O(1))

    (a)平衡二叉树

    此节点往下 左子树深度 - 右子树深度=平衡因子

    (注意这里是深度相减,而不是平衡因子)

    5的结点平衡因子就是 3 - 2 = 1;

    2的结点平衡因子就是 1 - 2 = -1;

    4的结点平衡因子就是 1 - 0 = 1;

    6的结点平衡因子就是 0 - 1 = -1;

    叶子结点都是为 0;

    (b)不平衡二叉树

    此节点往下 左子树深度- 右子树深度=平衡因子

    3 的结点平衡因子就是 2 - 4 = -2;

    1 的结点平衡因子就是 0 - 1 = -1;

    4 的结点平衡因子就是 0 - 3 = -3;

    5 的结点平衡因子就是 0 - 2 = -2;

    6 的结点平衡因子就是 0 - 1 = -1;

    叶子结点都是为 0;

    遍历二叉树:

    struct node
    {
        string data;
        node* lNode,rNode;
    };

    (1)前序(先根)遍历(根-左-右)

    void PreorderTraversal(node* data)
    {
        if(!data)
            return;//节点为空,返回
        printf("%s\n",data->data);//先取出根节点
        PreorderTraversal(data->lNode);//再取出左节点
        PreorderTraversal(data->rNode);//在取出右节点
    }

    (2)中序遍历(左-右-根)

    void MiddleOrderTraversal(node* data)
    {
        if(!data)
            return;//节点为空,返回
        MiddleOrderTraversal(data->lNode);//找出左节点
        printf("%s\n",data->data);//打印根节点
        MiddleOrderTraversal(data->rNode);//找出右节点
    }

    (3)后序遍历(右-左-根)

    void PostOrderTraversal(node* data)
    {
        if(!data)
            return;//节点为空,返回
        PostOrderTraversal(data->rNode);//找出右节点
        PostOrderTraversal(data->lNode);//找出左节点
        printf("%s\n",data->data);//打印根节点
        
    }

    (4)层序遍历(根据深度一层一层从左往右,从上往下遍历)

    队列方式遍历:

    //队列方式
    void queueTraversal(node* data)
    {
        if(!data)
            return;
        std::list<node*> list;//遍历的队列
        list.push_back(data);//放入根节点
        while(!list.empty())
        {
            cout<<list.front()->data<<endl;//取出遍历到的节点信息
            if(!list.front()->lNode)
            {
                list.push_back(list.front()->lNode);//放入左节点
            }
            if(!list.front()->rNode)
            {
                list.push_back(list.front()->rNode);//放入右节点
            }
            list.pop_front();//是删除已经遍历的
        }
    }

    数组方式遍历

    void FloorPrint(node Tree)  //层序遍历
    {
        node temp[100];   //创建pTreeNode指针类型的指针数组
        int in = 0;//表示当前已经进入数组的节点的下标
        int out = 0;//表示当前正在遍历的节点的下标
    
        temp[in++] = Tree;  //先保存二叉树根节点 
    
        while (in > out)
        {
            if (temp[out])
            {
                cout << temp[out]->data << " → ";
                temp[in++] = temp[out]->lNode;
                temp[in++] = temp[out]->rNode;
            }
            out++;
        }
    }
                 A
              /    \
            B        C
          /  \      /  \ 
         D    E     F   G  
     层序遍历结果是:  ABCDEFG
     前序遍历结果是:  ABDECFG
     中序遍历结果是:  DBEAFCG
     后序遍历结果是:  DEBFGCA

     

     

     

     

     

    展开全文
  • 平衡二叉树 ​ 平衡二叉搜索树,又被称为AVL树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。—-来自百度百科 ​ 由于普通的二叉查找树会...

    平衡二叉树

    ​  平衡二叉搜索树,又被称为AVL树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 —-来自百度百科

    ​  由于普通的二叉查找树会容易失去”平衡“,极端情况下,二叉查找树会退化成线性的链表,导致插入和查找的复杂度下降到 O(n) ,所以,这也是平衡二叉树设计的初衷。那么平衡二叉树如何保持”平衡“呢?根据定义,有两个重点,一是左右两子树的高度差的绝对值不能超过1,二是左右两子树也是一颗平衡二叉树。

      如下图所示,左图是一棵平衡二叉树,根节点10,左右两子树的高度差是1,而右图,虽然根节点左右两子树高度差是0,但是右子树15的左右子树高度差为2,不符合定义,所以右图不是一棵平衡二叉树。

    是否为平衡二叉树例图

    ​  由此可以看出平衡二叉树是一棵高度平衡的二叉查找树。所以,要构建跟维系一棵平衡二叉树就比普通的二叉树要复杂的多。在构建一棵平衡二叉树的过程中,当有新的节点要插入时,检查是否因插入后而破坏了树的平衡,如果是,则需要做旋转去改变树的结构。

      关于旋转,这东西不拿动态图将还真很难讲明白。所以我就借一下 最容易懂得红黑树 这篇文章中左旋右旋的图来讲。

    ​ 左旋

    左旋

    ​ 右旋

    右旋

      不同于顺时针跟逆时针变换这种方式去记忆,上面两个动态图特别方便记忆跟理解:

      左旋就是将节点的右支往左拉,右子节点变成父节点,并把晋升之后多余的左子节点出让给降级节点的右子节点;

      而右旋就是反过来,将节点的左支往右拉,左子节点变成了父节点,并把晋升之后多余的右子节点出让给降级节点的左子节点。

      即左旋就是往左变换,右旋就是往右变换。不管是左旋还是右旋,旋转的目的都是将节点多的一支出让节点给另一个节点少的一支

    ​  举个例子,像上图是否平衡二叉树的图里面,左图在没插入前”19“节点前,该树还是平衡二叉树,但是在插入”19“后,导致了”15“的左右子树失去了”平衡“,所以此时可以将”15“节点进行左旋,让”15“自身把节点出让给”17“作为”17“的左树,使得”17“节点左右子树平衡,而”15“节点没有子树,左右也平衡了。如下图,

    非平衡二叉树左旋变换成平衡二叉树例图

      由于在构建平衡二叉树的时候,当有新节点插入时,都会判断插入后时候平衡,这说明了插入新节点前,都是平衡的,也即高度差绝对值不会超过1。当新节点插入后,有可能会有导致树不平衡,这时候就需要进行调整,而可能出现的情况就有4种,分别称作左左,左右,右左,右右

    左左

    平衡二叉树失衡情况之左左

      左左即为在原来平衡的二叉树上,在节点的左子树的左子树下,有新节点插入,导致节点的左右子树的高度差为2,如上即为”10“节点的左子树”7“,的左子树”4“,插入了节点”5“或”3“导致失衡。

    ​  左左调整其实比较简单,只需要对节点进行右旋即可,如下图,对节点”10“进行右旋,

      注意:如果对左右旋变换还不是很懂或不是很熟练的,可以对照着前面的那两个动图去想象,自己动手变换几次,就明白了。

    平衡二叉树左左情况进行右旋

    左右

    平衡二叉树失衡情况之左右

      左右即为在原来平衡的二叉树上,在节点的左子树的右子树下,有新节点插入,导致节点的左右子树的高度差为2,如上即为”11“节点的左子树”7“,的右子树”9“,插入了节点”10“或”8“导致失衡。

      左右的调整就不能像左左一样,进行一次旋转就完成调整。我们不妨先试着让左右像左左一样对”11“节点进行右旋,结果图如下,右图的二叉树依然不平衡,而右图就是接下来要讲的右左,即左右跟右左互为镜像,左左跟右右也互为镜像。

    平衡二叉树左右情况右旋错误示范

      右右跟左左一样,只需要旋转一次就能把树调整平衡,而左右跟右左也一样,都要进行旋转两次才能把树调整平衡,所以,首先上图的这种调整是错误的,正确的调整方式是,将左右进行第一次旋转,将左右先调整成左左,然后再对左左进行调整,从而使得二叉树平衡。

    ​  即先对上图的节点”7“进行左旋,使得二叉树变成了左左,之后再对”11“节点进行右旋,此时二叉树就调整完成,如下图,

    平衡二叉树左右情况进行左旋再右旋

    右左

    平衡二叉树失衡情况之右左

    ​  右左即为在原来平衡的二叉树上,在节点的右子树的左子树下,有新节点插入,导致节点的左右子树的高度差为2,如上即为”11“节点的右子树”15“,的左子树”13“,插入了节点”12“或”14“导致失衡。

    ​  前面也说了,右左跟左右其实互为镜像,所以调整过程就反过来,先对节点”15“进行右旋,使得二叉树变成右右,之后再对”11“节点进行左旋,此时二叉树就调整完成,如下图,

    平衡二叉树右左情况进行右旋再左旋

    右右

    平衡二叉树失衡情况之右右

      右右即为在原来平衡的二叉树上,在节点的右子树的右子树下,有新节点插入,导致节点的左右子树的高度差为2,如上即为”11“节点的右子树”13“,的左子树”15“,插入了节点”14“或”19“导致失衡。

      右右只需对节点进行一次左旋即可调整平衡,如下图,对”11“节点进行左旋。

    平衡二叉树右右情况进行左旋

    展开全文
  • 平衡二叉树要求对于每一个节点来说,它的左右子树的高度之差不能超过1,如果插入或者删除一个节点使得高度之差大于1,就要进行节点之间的旋转,将二叉树重新维持在一个平衡状态。这个方案很好的解决了二叉查找树退化...

    一、定义及原理

    平衡二叉树要求对于每一个节点来说,它的左右子树的高度之差不能超过1,如果插入或者删除一个节点使得高度之差大于1,就要进行节点之间的旋转,将二叉树重新维持在一个平衡状态。这个方案很好的解决了二叉查找树退化成链表的问题,把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多。

    定义平衡二叉树:

    public class BalancedTree {
    
        private Integer iData;
        private Double dData;
        private BalancedTree leftNode;
        private BalancedTree rightNode;
        private Integer height = 1;
    
        public BalancedTree(Integer data, BalancedTree left, BalancedTree right) {
            this.iData = data;
            this.leftNode = left;
            this.rightNode = right;
        }
    
        public BalancedTree(Integer data) {
            this(data, null, null);
        }
    
        /**
         * 判断是否为叶子结点
         *
         * @return
         */
        public boolean isLeaf() {
            return this.leftNode == null && this.rightNode == null;
        }
    
        /**
         * 计算节点深度
         *
         * @param node
         * @return
         */
        public int height(BalancedTree node) {
            if (node == null) {
                return 0;
            } else {
                int l = height(node.leftNode);
                int r = height(node.rightNode);
                return (l > r) ? (l + 1) : (r + 1);//返回并加上当前层
            }
        }
    
        // ...
    }

    二、结点插入

    1、插入原理

    根据二叉平衡树的定义,一定保持左右子树深度绝对值小于1.在平衡二叉树插入工作一定考虑深度差,在AVL树进行插入工作时候,困难在于可能破坏AVL树的平衡属性。

    针对此类问题,需要根据树的实际结构进行几种简单的旋转(rotation)操作就可以让树恢复AVL树的平衡性质。

    2、旋转问题

    对于一个平衡的节点,由于任意节点最多有两个儿子,因此高度不平衡时,此节点的两颗子树的高度差2.容易看出,这种不平衡出现在下面四种情况:

    • 6节点的左子树3节点高度比右子树7节点大2,左子树3节点的左子树1节点高度大于右子树4节点,这种情况成为左左。
    • 6节点的左子树2节点高度比右子树7节点大2,左子树2节点的左子树1节点高度小于右子树4节点,这种情况成为左右。
    • 2节点的左子树1节点高度比右子树5节点小2,右子树5节点的左子树3节点高度大于右子树6节点,这种情况成为右左。
    • 2节点的左子树1节点高度比右子树4节点小2,右子树4节点的左子树3节点高度小于右子树6节点,这种情况成为右右。

    从图2中可以可以看出,1和4两种情况是对称的,这两种情况的旋转算法是一致的,只需要经过一次旋转就可以达到目标,我们称之为单旋转。2和3两种情况也是对称的,这两种情况的旋转算法也是一致的,需要进行两次旋转,我们称之为双旋转。

    3、旋转操作

    单旋转

    单旋转是针对于左左和右右这两种情况的解决方案,这两种情况是对称的,只要解决了左左这种情况,右右就很好办了。图3是左左情况的解决方案,节点k2不满足平衡特性,因为它的左子树k1比右子树Z深2层,而且k1子树中,更深的一层的是k1的左子树X子树,所以属于左左情况。

    为使树恢复平衡,我们把k2变成这棵树的根节点,因为k2大于k1,把k2置于k1的右子树上,而原本在k1右子树的Y大于k1,小于k2,就把Y置于k2的左子树上,这样既满足了二叉查找树的性质,又满足了平衡二叉树的性质。

    这样的操作只需要一部分指针改变,结果我们得到另外一颗二叉查找树,它是一棵AVL树,因为X向上一移动了一层,Y还停留在原来的层面上,Z向下移动了一层。整棵树的新高度和之前没有在左子树上插入的高度相同,插入操作使得X高度长高了。因此,由于这颗子树高度没有变化,所以通往根节点的路径就不需要继续旋转了。

    对于左左情况:进行右旋转=顺时针旋转,旋转轴的右子节点移动到父节点(失衡点)的左子节点。

    对于右右情况:进行左旋转=逆时针旋转,旋转轴的左子节点移动到父节点(失衡点)的右子节点。

    以左左情况为例,找到失衡点w,它的左子节点x变为父节点,而w则变为x的右子节点。

    单旋转代码实现:

        /**
         * 左左单旋转(LL旋转),w变为根节点,x变为w的右子树
         *
         * @param x
         * @return
         */
        private BalancedTree singleRotateLeft(BalancedTree x) {
            /**
             * 左左情况(x的左右相差2,w的左大于右),进行一次向右旋转
             *          x
             *        /   \
             *       w     c
             *      /  \
             *     A   B
             *    /
             *   m
             *
             */
    
            //把w结点旋转为根结点
            BalancedTree w = x.leftNode;
            //同时w的右子树变为x的左子树
            x.leftNode = w.rightNode;
            //x变为w的右子树
            w.rightNode = x;
    
            //返回新的根结点
            return w;
        }

    右右情况则完全相反,找到失衡点w,它的右子节点x变为父节点,而w则变为x的左子节点。

    单旋转代码实现:

        /**
         * 右右单旋转(RR旋转),x变为w的根节点,w变为x的左子树
         *
         * @param w
         * @return
         */
        private BalancedTree singleRotateRight(BalancedTree w) {
            /**
             * 右右情况(x的左右相差2,w的左大于右),进行一次向右旋转
             *       W
             *     /  \
             *    A    X
             *       /  \
             *      B   C
             *           \
             *            m
             *
             */
    
            BalancedTree x = w.rightNode;
            w.rightNode = x.leftNode;
            x.leftNode = w;
    
            //返回新的根结点
            return x;
        }

    双旋转

    对于左右和右左这两种情况,单旋转不能使它达到一个平衡状态,要经过两次旋转。双旋转是针对于这两种情况的解决方案,同样的,这样两种情况也是对称的,只要解决了左右这种情况,右左就很好办了。图4是左右情况的解决方案,节点k3不满足平衡特性,因为它的左子树k1比右子树Z深2层,而且k1子树中,更深的一层的是k1的右子树k2子树,所以属于左右情况。

    为使树恢复平衡,我们需要进行两步,第一步,把k1作为根,进行一次z左旋转,旋转之后就变成了左左情况,所以第二步再进行一次右旋转,最后得到了一棵以k2为根的平衡二叉树树。

    双旋转代码实现:

        /**
         * 左右旋转(LR旋转) x(根) w y 节点 经过旋转把y变成根节点
         * @param x 失衡点
         * @return
         */
        private BalancedTree doubleRotateWithLeft(BalancedTree x){
            /**
             * 左右情况,需要二次旋转,失衡点x的左子节点w,也是一个失衡点
             * 需要将y变为整棵树的根节点,以达到平衡;图示可看成以y为轴进行两次旋转
             *
             *     x
             *    / \
             *   w  D
             *  / \
             * A   y
             *    / \
             *   B   C
             *
             *
             */
            // w是x的左节点
            x.leftNode=singleRotateRight(x.leftNode);
            return singleRotateLeft(x);
        }
    
        /**
         * 右左旋转(RL旋转) x(根) w y 节点,经过旋转把y变为根节点
         * @param x
         * @return
         */
        private BalancedTree doubleRotateWithRight(BalancedTree x){
    
            /**
             * 右左情况,需要二次旋转,失衡点为x和w,因为x的左右节点深度差-2(右大于左),w的左节点深度大于右节点
             * 需要针对失衡点进行二次旋转,先是w左旋(顺时针),再x右旋(逆时针)
             *    x
             *   / \
             *  A   w
             *     / \
             *    y   D
             *   / \
             *  B   C
             *
             *
             */
            // w是x的右节点
            x.rightNode=singleRotateLeft(x.rightNode);
            return singleRotateRight(x);
        }

    能够触发旋转操作的,就是平衡二叉树的插入和删除了。

    4、节点插入实现

    与BST(二叉查找树)的插入实现原理一样,使用递归算法,根据值大小查找到插入位置,然后进行插入操作,插入完成后,我们需要进行平衡判断,评估子树是否需要进行平衡修复,需要则利用上述的四种情景套入代码即可,最后要记得重新计算插入结点路径上的高度。代码实现如下:

        /**
         * 插入节点
         *
         * @param data
         * @param pNode 平衡节点/插入目标节点
         * @return
         */
        public BalancedTree insert(Integer data, BalancedTree pNode) {
            if (pNode == null) {
                pNode = new BalancedTree(data);
            } else if (data.compareTo(pNode.getData()) < 0) {
                // 向左子树寻找插入位置
                pNode.leftNode = insert(data, pNode.leftNode);
    
    
                //插入完成后计算子树的高度,大于1则需要重新恢复平衡,由于是左边插入,左子树的高度肯定大于等于右子树的高度
                if (height(pNode.leftNode) - height(pNode.rightNode) > 1) {
                    //判断data是插入点的左孩子还是右孩子
                    if (data.compareTo(pNode.leftNode.getData()) < 0) {
                        // 进行LL旋转
                        pNode = singleRotateLeft(pNode);
                    } else {
                        // LR
                        pNode = doubleRotateWithLeft(pNode);
                    }
                }
            } else if (data.compareTo(pNode.getData()) > 0) {
                // 向右子树寻找插入位置
                pNode.rightNode = insert(data, pNode.rightNode);
    
                if (height(pNode.rightNode) - height(pNode.leftNode) > 1) {
                    if (data.compareTo(pNode.rightNode.getData()) < 0) {
                        pNode = doubleRotateWithRight(pNode);
                    } else {
                        pNode = singleRotateRight(pNode);
                    }
                }
            } else {
    
            }
            //重新计算各个结点的高度
            pNode.height = Math.max(height(pNode.leftNode), height(pNode.rightNode)) + 1;
            return pNode;
        }

    5、节点删除实现

     关于平衡二叉树的删除,我们这里给出一种递归的实现方案,和二叉查找树中删除方法的实现类似,但是在移除结点后需要进行平衡检测,以便判断是否需要进行平衡修复,主要明白的是,这种实现方式在删除时效率并不高,不过我们并不打算过多讨论它,更复杂的删除操作过程将放在以后进行讨论。下面给出实现代码:

        /**
         * 删除节点
         *
         * @param data  期望删除的节点值
         * @param pNode 平衡节点/删除目标节点
         * @return
         */
        public BalancedTree remove(Integer data, BalancedTree pNode) {
            if (pNode == null) {
                return null;
            }
            int result = data.compareTo(pNode.getData());
    
            //从左子树寻找需要删除的元素
            if (result < 0) {
                pNode.leftNode = remove(data, pNode.leftNode);
    
                // 检测是否平衡
                if (height(pNode.rightNode) - height(pNode.leftNode) > 1) {
                    BalancedTree currentNode = pNode;
                    // 判断需要哪种旋转
                    if (height(currentNode.leftNode) < height(currentNode.rightNode)) {
                        // RR
                        pNode= singleRotateRight(currentNode);
                    } else {
                        // RL
                        pNode= doubleRotateWithRight(currentNode);
                    }
                }
    
            } else if (result > 0) {
                pNode.rightNode = remove(data, pNode.rightNode);
    
                //检测是否平衡
                if (height(pNode.leftNode) - height(pNode.rightNode) > 1) {
                    BalancedTree currentNode = pNode;
                    // 判断需要哪种旋转
                    if (height(currentNode.rightNode) < height(currentNode.leftNode)) {
                        // LL
                        pNode = singleRotateLeft(currentNode);
                    } else {
                        // RL
                        pNode = doubleRotateWithLeft(currentNode);
                    }
                }
    
            } else if (pNode.rightNode != null && pNode.leftNode != null) {
                //已找到需要删除的元素,并且要删除的结点拥有两个子节点
    
                //寻找替换结点值、保留当前节点的左右子树(根据二叉树节点删除后替换逻辑)
                pNode.data = findMin(pNode.rightNode).data;
                //移除用于替换的结点 ;由于从右子树中找到了替换的节点值,并保存到了data中,因此需要将右子树中对应的替换节点删除
                pNode.rightNode = remove(pNode.data, pNode.rightNode);
            } else {
                //只有一个孩子结点或者只是叶子结点的情况
                pNode = (pNode.leftNode != null) ? pNode.leftNode : pNode.rightNode;
            }
    
            //更新高度值
            if (pNode != null)
                pNode.height = Math.max(height(pNode.leftNode), height(pNode.rightNode)) + 1;
            return pNode;
        }
    
        private BalancedTree findMin(BalancedTree pNode) {
            if (pNode == null)//结束条件
                return null;
            else if (pNode.leftNode == null)//如果没有左结点,那么pNode就是最小的
                return pNode;
            return findMin(pNode.leftNode);
        }

    注意,二叉树删除逻辑:

    对于二叉树来说,删除是一种比较麻烦的操作,因为涉及到了多种情况(设要删除的结点为q,其父母结点为p):

    • 如果要删除的结点q恰好是叶子结点,那么它可以立即被删除
    • 如果要删除的结点q拥有一个孩子结点,则应该调整要被删除的父结点(p.left 或 p.right)指向被删除结点的孩子结点(q.left 或 q.right)
    • 如果要删除的结点q拥有两个孩子结点,则删除策略是用q的右子树的最小的数据替代要被删除结点的数据,并递归删除用于替换的结点(此时该结点已为空),此时二叉查找树的结构并不会被打乱,其特性仍旧生效。采用这样策略的主要原因是右子树的最小结点的数据替换要被删除的结点后可以满足维持二叉查找树的结构和特性,又因为右子树最小结点不可能有左孩子,删除起来也相对简单些。
       

    其中第三点,示例如下:

                           

    删除节点12后,从右子树14中遍历寻找左子树13,直到找到左子树为空的节点13,即为可替换节点。替换完成后,需要从右子树14中将该节点删除。

    测试功能代码:

    // 测试节点的插入导致旋转、删除导致旋转
    BalancedTree root = new BalancedTree(12);
    root = root.insert(10, root);
    root = root.insert(13, root);
    root = root.insert(15, root);
    root = root.insert(16, root);
    root = root.insert(17, root);
    
    //root = root.remove(17, root);
    //root = root.remove(16, root);
    root = root.remove(12, root);
    root = root.remove(13, root);
    root = root.remove(10, root);
    
    System.out.println("end");
    
    
    // 测试删除过程中需要遍历子节点进行替换的逻辑
    BalancedTree root = new BalancedTree(15);
    root = root.insert(12, root);
    root = root.insert(16, root);
    root = root.insert(17, root);
    root = root.insert(10, root);
    root = root.insert(14, root);
    root = root.insert(13, root);
    
    root = root.remove(12, root);
    
    System.out.println("end");
    
    // 以上伪代码,验证时自行调整

     

    参考:(本文涉及以下文章摘录,代码部分有经过测试后调整逻辑)

    http://www.cnblogs.com/polly333/p/4798944.html

    https://blog.csdn.net/pacosonswjtu/article/details/50522677(按图示理解旋转方式)

    https://blog.csdn.net/javazejian/article/details/53892797#右右单旋转rr情景④分析(理解旋转实现)

     

    展开全文
  • 什么是平衡二叉树? 搜索树结点不同插入次序,将导致不同的深度和平均查找长度ASL。 平衡因子(Balance Factor,简称BF): BF(T) = hL-hR,其中hL和hR分别为T的左、右子树的高度。 平衡二叉树(Balanced Binary Tree...

    什么是平衡二叉树?
    搜索树结点不同插入次序,将导致不同的深度和平均查找长度ASL。
    平衡因子(Balance Factor,简称BF): BF(T) = hL-hR,其中hL和hR分别为T的左、右子树的高度。
    平衡二叉树(Balanced Binary Tree)(AVL树)空树,或者任一结点左、右子树高度差的绝对值不超过1,即|BF(T) |≤ 1。
    在这里插入图片描述
    设 nh 高度为h的平衡二叉树的最少结点数。结点数最少时:
    在这里插入图片描述

    给定结点数为n的AVL树的最大高度为O(log2n)

    平衡二叉树的调整
    1.RR 旋转(右单旋)在这里插入图片描述
    不平衡的“发现者”是Mar,“麻烦结点”Nov 在发现者右子树的右边,因而叫 RR 插入,需要RR 旋转(右单旋)
    在这里插入图片描述
    2.LL 旋转(左单旋)
    在这里插入图片描述
    “发现者”是Mar,“麻烦结点”Apr 在发现者左子树的左边,因而叫 LL 插入,需要LL 旋转(左单旋)
    在这里插入图片描述
    3.LR 旋转(左-右双旋)
    在这里插入图片描述
    “发现者”是May,“麻烦结点”Jan在左子树的右边,因而叫 LR 插入,需要LR 旋转
    在这里插入图片描述
    4.RL 旋转(右-左双旋)
    在这里插入图片描述
    一般情况调整如下:
    在这里插入图片描述
    注意:有时候插入元素即便不需要调整结构,也可能需要重新计算一些平衡因子。

    问:在下列平衡树中插入3后,该树是否还平衡?如果不平衡应该做什么旋转进行调整?(C)
    在这里插入图片描述
    A.还是平衡的
    B.不平衡了,应该做LL旋转
    C.不平衡了,应该做RR旋转
    D.不平衡了,应该做LR旋转

    (以上笔记总结自浙江大学数据结构课程)

    展开全文
  • 平衡二叉树概念:平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构。特点:平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据,用这个树形结构的数据减少无关数据的检索,大大的...
  • 平衡二叉树

    2020-08-10 22:44:40
    平衡二叉树 概念 平衡二叉树又称AVL树,任意节点的子树的高度差都小于等于1。 性质: 它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1; 若将二叉树节点的平衡因子BF定义为该节点的...
  • 二叉树之平衡二叉树

    2019-07-03 11:36:15
    3.平衡二叉树概念    每一个节点的左右子树的高度差的绝对值不大于1,或者本身是空树。 4. 思路    剪枝,其实就是从下到上遍历,只需要遍历一次。如果采用之前计算树深的方式,会有很多重复遍历,增加开销。  ...
  • 数据结构 - 平衡二叉树(C++)

    万次阅读 多人点赞 2019-02-22 15:36:53
    平衡二叉树(Balanced Binary Tree)是具有以下性质的二叉树:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 判断一棵二叉树是否平衡(C++) /* * Cr...
  • 平衡二叉树实现

    2018-12-27 18:57:49
    实现平衡二叉树平衡二叉树概念平衡二叉树实现原理具体代码实现 平衡二叉树概念 在保持二叉树的基本原则外,任意结点左右子树高度差绝对值不超过1。 平衡二叉树实现原理 平衡二叉树相较于二叉搜索树会增加一个高度...
  • 平衡二叉树定义(AVL):它或者是一颗空树,或者具有以下性质的二叉树:它的左子树和右子树的深度之差的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。 平衡因子(bf):结点的左子树的深度减去右子树的深度...
  • 数据结构之平衡二叉树平衡二叉树概念平衡二叉树的调整LL型调整RR型调整LR型调整RL型调整代码示例 平衡二叉树概念 平衡二叉查找树:简称平衡二叉树。由前苏联的数学家Adelse-Velskil和Landis在1962年提出的高度平衡的...
  • 二叉树的概念二叉树定义五种形态二叉树与度为2的树满二叉树完全二叉树二叉排序树平衡二叉树性质存储结构静态存储结构链式存储结构 二叉树定义 每个结点至多只有两棵子树(即二叉树中不存在度>2的结点),且二叉树...
  • 二叉搜索树的结点按照不同的...平衡二叉树(AVL树):空树或者任一结点的左右子树高度差的绝对值不超过1,即|BF(T)|<=1 平衡因子:BF(T)=hL-hR hL和hR为T左右子树的高度 结点数为n的AVL树的最大高度为O(log2n) ...
  • 详解平衡二叉树

    2012-07-15 10:00:16
    详解平衡二叉树平衡二叉树概念,算法思想,程序源码
  • 平衡二叉树概念: 一棵AVL树是其每个节点的左子树和右子树的高度差最多为1的二叉查找树。(空树的高度定义为−1-1−1)。 “平衡因子”:BF(T)=hL−hRBF(T)=h_L-h_RBF(T)=hL​−hR​,其中hLh_LhL​和hRh_...
  • PAT 甲级 1066 Root of AVL Tree (25 分)平衡二叉树的创建 ...平衡二叉树概念 平衡二叉树是一种二叉排序树,将其不断调整为平衡二叉树是为了提高查找的效率。平衡二叉树的递归定义条件是: 对于...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,181
精华内容 8,872
关键字:

平衡二叉树的概念