java实现平衡二叉树 - Go语言中文社区

java实现平衡二叉树

本文参考海纳的两篇文章，需要补平衡二叉树知识的请看这里。

参照的文章是这篇文章。

可以直接去看这两篇文章，再回头看我这篇文章，所以我就去繁就简。

代码

package com.yubotao;

/**
 * @Auther: yubt
 * @Description:
 * @Date: Created in 9:23 2018/6/8
 * @Modified By:
 */
public class AVLNode {
    public int data;
    public int depth;
    public int balance;
    public AVLNode parent;
    public AVLNode left;
    public AVLNode right;

    public AVLNode(int data){
        this.data = data;
        depth = 1;
        balance = 0;
        left = null;
        right = null;
    }

    public void insert(AVLNode root, int data){
        if (data < root.data){
            if (root.left != null){
                insert(root.left, data);
            }else {
                root.left = new AVLNode(data);
                root.left.parent = root;
            }
        }else {
            if (root.right != null){
                insert(root.right, data);
            }else {
                root.right = new AVLNode(data);
                root.right.parent = root;
            }
        }

        // 从插入的过程回溯回来的时候，计算平衡因子
        root.balance = calcBalance(root);

        // 左子树高，应该右旋
        if (root.balance >= 2){
            // 右孙高，先左旋
            if (root.left.balance == -1){
                left_rotate(root.left);
            }
            right_rotate(root);
        }

        // 右子树高，左旋
        if (root.balance <= -2){
            // 左孙高，先右旋
            if (root.right.balance == 1){
                right_rotate(root.right);
            }
            left_rotate(root);
        }

        root.balance = calcBalance(root);
        root.depth = calcDepth(root);
    }

    // 右旋
    private void right_rotate(AVLNode p){
        // 一次旋转涉及到的结点包括祖父，父亲，右儿子
        AVLNode pParent = p.parent;
        AVLNode pLeftSon = p.left;
        AVLNode pRightGrandSon = pLeftSon.right;

        // 左子变父
        pLeftSon.parent = pParent;
        if (pParent != null){
            if (p == pParent.left){
                pParent.left = pLeftSon;
            }else if (p == pParent.right){
                pParent.right = pLeftSon;
            }
        }

        pLeftSon.right = p;
        p.parent = pLeftSon;

        // 右孙变左孙
        p.left = pRightGrandSon;
        if (pRightGrandSon != null){
            pRightGrandSon.parent = p;
        }

        p.depth = calcDepth(p);
        p.balance = calcBalance(p);

        pLeftSon.depth = calcDepth(pLeftSon);
        pLeftSon.balance = calcBalance(pLeftSon);
    }

    private void left_rotate(AVLNode p){
        // 一次选择涉及到的结点包括祖父，父亲，左儿子
        AVLNode pParent = p.parent;
        AVLNode pRightSon = p.right;
        AVLNode pLeftGrandSon = pRightSon.left;

        // 右子变父
        pRightSon.parent = pParent;
        if (pParent != null){
            if (p == pParent.right){
                pParent.right = pRightSon;
            }else if (p == pParent.left){
                pParent.left = pRightSon;
            }
        }

        pRightSon.left = p;
        p.parent = pRightSon;

        // 左孙变右孙
        p.right = pLeftGrandSon;
        if (pLeftGrandSon != null){
            pLeftGrandSon.parent = p;
        }

        p.depth = calcDepth(p);
        p.balance = calcBalance(p);

        pRightSon.depth = calcDepth(pRightSon);
        pRightSon.balance = calcBalance(pRightSon);
    }

    public int calcBalance(AVLNode p){
        int left_depth;
        int right_depth;

        if (p.left != null){
            left_depth = p.left.depth;
        }else {
            left_depth = 0;
        }

        if (p.right != null){
            right_depth = p.right.depth;
        }else {
            right_depth = 0;
        }

        return left_depth - right_depth;
    }

    public int calcDepth(AVLNode p){
        int depth = 0;
        if (p.left != null){
            depth = p.left.depth;
        }

        if (p.right != null && depth < p.right.depth){
            depth = p.right.depth;
        }

        depth++;
        return depth;
    }

}

这里阐述几个概念：

平衡因子：该结点左右子树的深度（高度）差。

深度（高度）：树的层数。

如图
这里写图片描述
四棵树的深度依次为：4，3，4，3.

这两个概念理解好才能更加快速的理解上面的代码。

插入原理讲解

我们先看第一种情况：
这里写图片描述

c节点也就是黄色节点是我们新插入的节点，此时树不平衡，需要进行操作。根据各节点平衡因子判断（可参照代码），我们需要先右旋后左旋。这里已经把每个节点都做了相应的标记了，相关步骤就是代码的执行顺序。

我只做一次代码解读，后面的自己看图对应一下。

首先，我们进入insert()方法，此时应该是新建一个节点c。执行到方法体中的开头部分

if (data < root.data){
            if (root.left != null){
                insert(root.left, data);
            }else {
                root.left = new AVLNode(data);
                root.left.parent = root;
            }
        }

此时走else分支，新建了一个结点，并指定c的parent结点。
然后我们这时需要执行到这步：

// 从插入的过程回溯回来的时候，计算平衡因子
        root.balance = calcBalance(root);

计算b结点的balance，为1。后续两个if判断跳过，并计算了b结点的balance为1，depth为2.

此时怎么样了呢？

我们从a结点的insert()方法中的开头部分

else {
            if (root.right != null){
                insert(root.right, data);
            }else {
                root.right = new AVLNode(data);
                root.right.parent = root;
            }
        }

if分支跳出（因为我们插入的时候，a有右子树b，所以当时进入了b结点的insert()方法）。
接下来计算a结点的balance，为-2，进入第二个if分支

 // 右子树高，左旋
        if (root.balance <= -2){
            // 左孙高，先右旋
            if (root.right.balance == 1){
                right_rotate(root.right);
            }
            left_rotate(root);
        }

并且b结点的balance为1，符合条件，开始进行右旋操作。进入方法right_rotate()中。
这时p为b结点，所以就如上图标识，按照代码顺序执行此次右旋操作。

// 右旋
    private void right_rotate(AVLNode p){
        // 一次旋转涉及到的结点包括祖父，父亲，右儿子
        AVLNode pParent = p.parent;
        AVLNode pLeftSon = p.left;
        AVLNode pRightGrandSon = pLeftSon.right;

        // 左子变父
        pLeftSon.parent = pParent; // 图中左1
        if (pParent != null){
            if (p == pParent.left){
                pParent.left = pLeftSon;  // 图中左2
            }else if (p == pParent.right){
                pParent.right = pLeftSon; 
            }
        }

        pLeftSon.right = p; // 图中左3
        p.parent = pLeftSon;  // 图中左4

        // 右孙变左孙
        p.left = pRightGrandSon;  // 图中左5
        if (pRightGrandSon != null){
            pRightGrandSon.parent = p;
        }

        p.depth = calcDepth(p);
        p.balance = calcBalance(p);

        pLeftSon.depth = calcDepth(pLeftSon);
        pLeftSon.balance = calcBalance(pLeftSon);
    }

接下来进入左旋方法left_rotate()，注意此时的p结点为a结点。
如上图右边标识，再看一下代码执行顺序：

private void left_rotate(AVLNode p){
        // 一次选择涉及到的结点包括祖父，父亲，左儿子
        AVLNode pParent = p.parent;
        AVLNode pRightSon = p.right;
        AVLNode pLeftGrandSon = pRightSon.left;

        // 右子变父
        pRightSon.parent = pParent; // 图中右1
        if (pParent != null){
            if (p == pParent.right){
                pParent.right = pRightSon;
            }else if (p == pParent.left){
                pParent.left = pRightSon;
            }
        }

        pRightSon.left = p;  // 图中右2
        p.parent = pRightSon;  // 图中右3

        // 左孙变右孙
        p.right = pLeftGrandSon;  // 图中右4
        if (pLeftGrandSon != null){
            pLeftGrandSon.parent = p;
        }

        p.depth = calcDepth(p);
        p.balance = calcBalance(p);

        pRightSon.depth = calcDepth(pRightSon);
        pRightSon.balance = calcBalance(pRightSon);
    }

此时，完成整个插入过程。

接下来我们再看两种情况。
这里写图片描述

可以看到圈出的两部分就是上面两种情况。所以就不一一赘述。

最后再看更复杂的两种情况，只贴图，可以自己跟着代码顺序捋一捋，熟悉一下这个过程，我就不一一分析了。

这里写图片描述

这里写图片描述

删除方法

这部分待续，我还没完全想好，抽个时间再来更新吧。
主要删除的时候需要考虑，如何处理待删结点有子节点的情况。
如果待删结点是叶子结点，那么很容易删除，然后向上回溯，看一下各结点的平衡因子，并执行相关的左右旋方法即可。
但是如果待删结点有左右子树时，这个时候就要考虑如何操作了，怎样将该结点删除又不影响其子节点。
我的一个想法是：将待删结点变为叶子结点，这样就好操作了，不过这个代码怎么写，如果同时有左右结点，和哪个结点互换，是不是都行呢？
有个想法是如果待删结点有左右子树，将该结点与中序遍历的前一个结点交换，如果其还有左右子树，再交换，直到结点无左右子树为止（递归），然后删除，在向上回溯，判断其平衡因子。

先思考到这里，有兴趣的朋友可以留言，一起讨论。

终于抽时间把删除的代码写完了，调试了很久，想的时候思路挺清晰的，但是一旦写的时候就能看出之前考虑的很多地方都不是很周全。

大概耗时2个多小时。先贴一下代码

public void delete(AVLNode root, int data){
        if (data < root.data)
            delete(root.left, data);
        else if (data > root.data)
            delete(root.right, data);
        else{
            if (root.left != null)
                exchange(root, root.left);
            else if (root.right != null)
                exchange(root, root.right);

            // 当data节点为子节点时
            if (data == root.data && root.left == null && root.right == null){
                if (root.parent.left.data == root.data){
                    root.parent.left = null;
                    root.parent = null;
                }else if (root.parent.right.data == root.data){
                    root.parent.right = null;
                    root.parent = null;
                }
            }

        }

        // 回溯，计算平衡因子
        root.balance = calcBalance(root);

        // 左子树高，应该右旋
        if (root.balance >= 2){
            // 右孙高，先左旋
            if (root.left.balance == -1){
                left_rotate(root.left);
            }
            right_rotate(root);
        }

        // 右子树高，左旋
        if (root.balance <= -2){
            // 左孙高，先右旋
            if (root.right.balance == 1){
                right_rotate(root.right);
            }
            left_rotate(root);
        }

        root.balance = calcBalance(root);
        root.depth = calcDepth(root);
    }

private void exchange(AVLNode p, AVLNode pSon){
        int temp;

        temp = p.data;
        p.data = pSon.data;
        pSon.data = temp;

        // 当data节点不为子节点时
        if (pSon.left == null && pSon.right == null){
            if (pSon.parent.left.data == pSon.data){
                pSon.parent.left = null;
                pSon.parent = null;
            }else if (pSon.parent.right.data == pSon.data){
                pSon.parent.right = null;
                pSon.parent = null;
            }
            // 保证删除子节点后的p的平衡因子和深度正确，这样才能保证整体的正确
            p.depth = calcDepth(p);
            p.balance = calcBalance(p);
            return;
        }

        if (pSon.left != null){
            exchange(pSon, pSon.left);

            // 回溯时需计算平衡因子及深度，否则会出现错误
            p.depth = calcDepth(p);
            p.balance = calcBalance(p);
            // 保证递归回溯的时候不进行其他分支操作
            return;
        }
        if (pSon.right != null){
            exchange(pSon, pSon.right);

            p.depth = calcDepth(p);
            p.balance = calcBalance(p);
            return;
        }

    }

基本的坑位我都给标记出来了。

测试代码：

public class TestAVLNode {
    public static void main(String[] args) {
        AVLNode one = new AVLNode(5);
        AVLNode two = new AVLNode(3);
        AVLNode three = new AVLNode(7);
        AVLNode four = new AVLNode(2);
        AVLNode five = new AVLNode(4);
        AVLNode six = new AVLNode(6);
        AVLNode seven = new AVLNode(1);

        one.left = two;
        one.right = three;
        two.parent = one;
        three.parent = one;

        two.left = four;
        two.right = five;
        four.parent = two;
        five.parent = two;

        three.left = six;
        six.parent = three;

        four.left = seven;
        seven.parent = four;

        one.balance = 1;
        one.depth = 4;

        two.balance = 1;
        two.depth = 3;

        three.balance = 1;
        three.depth = 2;

        four.balance = 1;
        four.depth = 2;

        five.balance = 0;
        five.depth = 1;

        six.balance = 0;
        six.depth = 1;

        seven.balance = 0;
        seven.depth = 1;

        System.out.println(one);

        one.delete(one, 7);

        System.out.println(two);
    }
}

测试树长这样
这里写图片描述

说一下整个过程碰到的几个问题。

首先是交换值方法。因为被删节点如果不是子节点，就需要把它交换到子节点位置，然后再删除。所以为了写这个交换方法，我先写了一个单链表的交换，比较简单：

package com.yubotao;

/**
 * @Auther: yubt
 * @Description:
 * @Date: Created in 18:50 2018/6/21
 * @Modified By:
 */
public class TestExchange {
    private static class One{
        private One next;
        private int data;

        public One getNext(<
版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/ybt_c_index/article/details/80623974
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

你可能感兴趣的文章

精选的优质文章

0 条评论

请先 登录 后评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看

来源51CTO

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！