(三)树结构---平衡二叉树的实现

导语

  • 平衡二叉树的概念之前已经介绍过，这里不做累述，可以参考树结构-基础,这里主要考虑代码实现和思路原理
  • 平衡二叉树基于二分搜索树，所以需要了解二分搜索树的实现过程和复用其中的代码
  • 注意文中出现的名词：
    1. 添加元素和添加结点是指一个行为，添加元素是在使用者的角度，因为使用者往树里面只是添加一个一个的元素值，不管你的结点如何变化。添加结点是站在树的变化角度，我们知道每个元素其实在一个结点中包裹着，就是我们的私有类Node结点的一个变量存储着，所以使用者添加元素的行为对于树来说就是在添加包裹元素和其他信息的一个结点。
    2. 某个结点的左子树(左孩子)和右子树(右孩子)，是指该结点的左侧的所有子代和右侧的所有子代，一直到叶子结点都是它的孩子。而采用某个结点的左儿子和右儿子是指该结点左边连接的一个结点和右边连接的一个节点，只代指一个后代。所以左儿子的右儿子就很清楚了(该定义仅是文中需要所作定义，图片中注解除外)。
    3. 双亲和父亲都是指该结点所连接的上一个结点，并非双就是两个。

1.平衡二叉树的意义

  • 平衡二叉树的时间复杂度维持在O(log n),不会出现在极端情况下退化成链表的情况，而使二分搜索树的时间复杂度变为O(n)
  • 使用平衡二叉树实现一个映射，即K-V键值对，此时键应该满足可以通过比较判断键的大小
public class AVLTree<K extends Comparable<K>, V> {

    private class Node {
        //保存的key
        public K key;
        //保存的value
        public V value;
        //该结点的左儿子，右儿子
        public Node left, right;
        //该结点的高度，默认添加的叶子节点高度为1
        public int height;
       //结点构造方法
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            left = null;
            right = null;
            height = 1;
        }
    }
    //默认创建的根结点
    private Node root;
    //保存的结点数量
    private int size;
    //该平衡二叉树构造方法
    public AVLTree() {
        root = null;
        size = 0;
    }

    /**
     * 获取结点数量
     *
     * @return ：
     */
    public int getSize() {
        return size;
    }

    /**
     * 判断当前映射是否为空
     *
     * @return ：
     */
    public boolean isEmpty() {
        return size == 0;
    }
}

2.维护平衡二叉树参数

2.1.每个结点的高度

  • 每添加一个结点都会放到叶子结点，定义叶子结点的高度为1，空结点的高度为0
  • 每个结点的双亲结点的高度 = max(左子树高度，右子树高度) + 1
     /**
     * 获取node结点的高度值
     * 叶子结点的高度为1，空结点为0
     * 每一个结点的高度 等于 其左子树和右子树中最大的高度 + 1
     *
     * @return ：
     */
    private int getHeight(Node node) {
        return node == null ? 0 : node.height;
    }

2.2.每个结点的平衡因子

  • 该结点的平衡因子 = 其左子树的高度 - 其右子树的高度
  • 若结点的平衡因子的绝对值大于1，(由于每添加一个结点都会判断每个节点的平衡因子，所以被破坏平衡时，也是平衡因子为2的情况)，此时通过旋转树的操作完成树的平衡
  /**
     * 获取node结点的平衡因子
     * 若平衡因子大于1，则该二分搜索树的品平衡被破坏，不再为平衡二叉树
     * node结点的平衡因子 = node.left.height - node.right.height
     * node结点的平衡因子 为 node左子树的高度 减 node右子树的高度
     *
     * @param node ：结点
     * @return ：平衡因子
     */
    private int getBalanceFactor(Node node) {
        if (node == null) {
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }

3.旋转维护平衡二叉树

  • 上述的代码和上一章二分搜索树的实现代码基本上是一致的，只是上一章实现的是集合，这一章是映射，而唯一多出来的就是维护每个结点的高度和平衡因子这两个概念。
  • 需要维护平衡，说明平衡二叉树发生了改变，也就是说只有在增删的时候才需要维护平衡，先以添加元素为例子详细介绍，删除同理。

3.1.LL

  • 当新添加一个结点，此时添加结点在不平衡结点的左儿子的左子树上
    我们需要将不平衡结点进行右旋 
  /**
     * 对结点Y进行右旋转操作，返回旋转后的新的根节点
     *          y                                x
     *        /  \                            /     \
     *       x    T4      向右旋转(y)         Z       y
     *     /   \        --------------->   /  \    /   \
     *    Z    T3                        T1   T2  T3   T4
     *  /   \
     * T1   T2
     * 1.x的右儿子变成y
     * 2.y的左儿子变成T3
     *
     * @param y ：不平衡结点
     * @return ：旋转后的新的根节点
     */
    private Node rightRotate(Node y) {
        //保存y的左儿子结点x
        Node x = y.left;
        //保存x的右儿子
        Node t3 = x.right;
        //向右旋转过程
        //y变成x的右儿子
        x.right = y;
        //t3变成y的左儿子
        y.left = t3;

        //更新y,x结点的高度值
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
        return x;
    }

1.当我们递归到底增加某一个叶子结点后，回溯到根结点的过程中，需要重新计算所有为了添加这个叶子结点所走过的此结点的父类(双亲和祖先)结点的高度和平衡因子，以维护平衡二叉树的性质。
2.若其中一些结点出现平衡因子大于1，说明该结点不再平衡，而这个不平衡结点的左儿子高度大于大于右儿子高度，说明添加操作发生在不平衡结点的左儿子的左子树上


AVL-LL-右旋

3.2.RR

  • 当新添加一个结点，此时添加结点在不平衡结点的右儿子的右子树上
    我们需要将不平衡结点进行左旋 
  /**
     * 对结点Y进行左旋转操作，返回旋转后的新的根节点
     *            y                                  x
     *          /  \                               /     \
     *        T4    x           向左旋转(y)       y        Z
     *            /   \      --------------->   /  \    /   \
     *          T3     Z                       T4  T3   T1   T2
     *               /   \
     *              T1   T2
     * <p>
     * 1. x的左儿子变成y
     * 2. y的右儿子变成T3
     *
     * @param y ：不平衡结点
     * @return ：旋转后的新的根节点
     */
    private Node leftRotate(Node y) {
        //保存y的右儿子为X
        Node x = y.right;
        //保存x的左儿子为t3
        Node t3 = x.left;
        //左旋
        //y变成x的左儿子
        x.left = y;
        //ts变成y的右儿子
        y.right = t3;

        //重新计算y,x的高度
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

        return x;
    }

左旋的过程：
不平衡结点的右儿子为后继节点，且不平衡节点变成后继节点的左儿子
后继节点的原本的左儿子，变成不平衡结点的右儿子


AVL-RR-左旋

3.3.LR

  • 当新添加一个新结点，此时添加结点在不平衡结点的左儿子的右子树上
    我们需要将先进行左旋，再进行右旋

1.先对不平衡节点的左儿子进行左旋，变成LL的形式
2.再对不平衡结点进行右旋


AVL-LR-先左旋再右旋

3.4.RL

  • 当新添加一个新结点，此时添加结点在不平衡结点的右儿子的左子树上
    我们需要将先进行右旋，再进行左旋

1.先对不平衡节点的右儿子进行右旋，变成RR的形式
2.再对不平衡结点进行左旋


AVL-RL-先右旋再左旋

3.5.旋转总结

场景：平衡二叉树在添加或删除一个结点后，出现不平衡情况

情况 新结点在不平衡结点的位置 修正平衡方式 后继结点位置 记忆方式
LL 在左儿子的左子树上 右旋 左儿子 左左-右
RR 在右儿子的右子树上 左旋 右儿子 右右-左
LR 在左儿子的右子树上 先左旋再右旋 左儿子的右儿子、左儿子 左右-左右
RL 在右儿子的左子树上 先右旋再左旋 右儿子的左儿子、右儿子 右左-右左

1.当叠词即(LL、RR)的时候，旋转方式正好相反
2.当一左一右的时候，旋转方式按顺序来

3.6.添加方法代码实现

  • 添加方法的思路和二分搜索树是一致的，只是在递归遍历添加新结点结束后，回溯到上层结点的过程中，计算和维护每个结点的高度和平衡因子，若出现不平衡点则开始使用旋转的方式进行维护平衡二叉树。
   /**
     * 添加一个结点
     */
    public void add(K key, V value) {
        root = add(root, key, value);
    }

    /**
     * 向以node为根的二分搜索树中添加一个结点，(若该结点已存在，则更新值)
     * 并返回这个二分搜索树的根结点
     *
     * @param node  ：根结点
     * @param key   ：添加的键
     * @param value ：添加的值
     * @return ：新的二分搜索树的根结点
     */
    private Node add(Node node, K key, V value) {
        //********   递归添加新结点部分   ********  
        if (node == null) {
            size++;
            return new Node(key, value);
        }
        if (key.compareTo(node.key) < 0) {
            node.left = add(node.left, key, value);
        } else if (key.compareTo(node.key) > 0) {
            node.right = add(node.right, key, value);
        } else {
            node.value = value;
        }

        //********   回溯维护平衡二叉树部分   ******** 
        //计算每个结点的高度
        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
        //获取该结点的平衡因子
        int balanceFactor = getBalanceFactor(node);
      
        //开始调整树为平衡二叉树
        //LL：添加结点在不平衡结点的左孩子的左孩子上
        if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
            return rightRotate(node);
        }

        //LR :添加结点在不平衡结点的左孩子的右孩子上
        if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        //RR：添加结点在不平衡结点的右孩子的右孩子
        if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
            return leftRotate(node);
        }

        //RL：添加结点在不平衡结点的右孩子的左孩子上
        if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }

3.7.删除方法实现

  • 删除结点的时候也会使平衡二叉树发生变化，此时也需要维护平衡二叉树的性质
    删除也分成两部分，先删除节点，再维护平衡，其中删除结点的代码会有一些微小的变化。
    1.在二分搜索树的时候，删除结点分成三种情况，而每次删除后，会直接开始回溯，并返回根节点，现在执行任意一种情况后，先不返回，待判断此二叉树是否平衡修正后再返回。
    2.删除的结点可能为叶子结点，此时不需要对该空返回结点进行平衡判断。
    3.在删除节点分别进入其左右子树的进行删除，也会直接返回，此时也许要在判断是否平衡后再返回。
    /**
     * 删除key为键的结点
     *
     * @param key ：
     * @return ：
     */
    public V remove(K key) {
        Node node = getNode(root, key);
        if (node != null) {
            root = remove(root, key);
        }
        return null;
    }

    /**
     * 删除以node为根结点的平衡二叉树中键为key的结点
     * 并返回删除节点后的平衡二叉树的根
     *
     * @param node ：
     * @param key  :
     * @return :
     */
    private Node remove(Node node, K key) {
        if (node == null) {
            return null;
        }
        Node retNode;
        if (key.compareTo(node.key) < 0) {
            node.left = remove(node.left, key);
            retNode = node;
        } else if (key.compareTo(node.key) > 0) {
            node.right = remove(node.right, key);
            retNode = node;
        } else {
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                retNode = rightNode;
            } else if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                retNode = leftNode;
            } else {

                //若左右子树都不为空
                //寻找后继节点：即为待删除结点的右子树中的最小结点
                Node successor = getSuccessorNode(node.right);
                //从待删除结点的右子树中删除后继节点，并返回右子树的根，并成为后继结点的右子树
                successor.right = remove(node.right, successor.key);
                //待删除结点的左子树成为后继结点的左子树
                successor.left = node.left;

                //清空待删除结点的左右子树
                node.left = node.right = null;
                //后继结点继承待删除结点位置
                retNode = successor;
            }
        }
        if (retNode == null) {
            return null;
        }
        //更新每个结点的高度
        retNode.height = Math.max(getHeight(retNode.left), getHeight(retNode.right)) + 1;
        //计算平衡因子
        int balanceFactor = getBalanceFactor(retNode);

        //维护二分搜索树的平衡二叉树的性质
        //LL
        if(balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0){
            return rightRotate(retNode);
        }
        //LR
        if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0){
            retNode.left = leftRotate(retNode.left);
            return rightRotate(retNode);
        }
        //RR
        if(balanceFactor < -1 && getBalanceFactor(retNode.right)>= 0){
            return leftRotate(retNode);
        }
        //RL
        if(balanceFactor < -1 && getBalanceFactor(retNode.right) < 0){
            retNode.right = rightRotate(retNode.right);
            return leftRotate(retNode);
        }
        return retNode;
    }

   /**
     * 获取以node为根结点的平衡二叉树中最小的结点，并返回。
     *
     * @param node ：
     * @return ：
     */
    private Node getSuccessorNode(Node node) {
        if (node.left != null) {
            return getSuccessorNode(node.left);
        }
        return node;
    }

   /**
     * 获取以node为根结点的平衡二叉树中键为key的结点，并返回该结点
     *
     * @param node ：
     * @param key  :
     * @return :
     */
    private Node getNode(Node node, K key) {
        if (node == null) {
            return null;
        }
        if (key.compareTo(node.key) < 0) {
            return getNode(node.left, key);
        } else if (key.compareTo(node.key) > 0) {
            return getNode(node.right, key);
        } else {
            return node;
        }
    }

4.验证平衡二叉树性质

4.1.验证是否为二分搜索树

  • 思路：中序遍历存储所有该二叉树的值，依次比较相邻的两个值，若出现后一个值小于前一个值，则非二分搜索树
   /**
     * 判断当前二叉树是否为二分搜索树
     *
     * @return ：
     */
    public boolean isBST() {
        List<K> keys = new ArrayList<>();
        inOrder(root, keys);
        for (int i = 1; i < keys.size(); i++) {
            if (keys.get(i - 1).compareTo(keys.get(i)) > 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 中序遍历：存储所有的key值
     *
     * @param node ：结点
     * @param keys ：键集合
     */
    private void inOrder(Node node, List<K> keys) {
        if (node == null) {
            return;
        }
        inOrder(node.left, keys);
        keys.add(node.key);
        inOrder(node.right, keys);
    }

4.2.验证是否为平衡二叉树

  • 思路：所有的结点的平衡因子的绝对值是否满足大于1，若出现任意一个结点大于，则非平衡二叉树
   /**
     * 判断当前二叉搜索树是否为平衡二叉树
     *
     * @return ：
     */
    public boolean isBalanced() {
        return isBalanced(root);
    }

    /**
     * 判断以node为根结点的二分搜索树是否为平衡二叉树
     *
     * @param node ：
     * @return :
     */
    private boolean isBalanced(Node node) {
        if (node == null) {
            return true;
        }
        int balanceFactor = getBalanceFactor(node);
        if (Math.abs(balanceFactor) > 1) {
            return false;
        }
        return isBalanced(node.left) && isBalanced(node.right);
    }

4.3.打印当前平衡二叉树的结点

  • 思路：重写toString方法，中序遍历所有结点，以根为0的深度，依次增加，每增加一个深度，输出结点值的前面加上字符串"--",来标识不同深度的结点
    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        getAVLTreeDataStructure(root, str, 0);
        return str.toString();
    }

    /**
     * 输出以node根节点的平衡二叉树中个数据存储的键的结构
     *
     * @param node  ：根结点
     * @param str   ：输出值
     * @param depth : 以根深度为0，其孩子+1
     */
    private void getAVLTreeDataStructure(Node node, StringBuilder str, int depth) {
        if (node == null) {
            //str.append(getExpressByHeight(depth) + "null\n");
            return;
        }
        getAVLTreeDataStructure(node.left, str, depth + 1);
        str.append(getExpressByHeight(depth) + node.key + "\n");
        getAVLTreeDataStructure(node.right, str, depth + 1);
    }

    /**
     * 通过结点的高度计算输出标识高度
     *
     * @param depth :
     * @return :
     */
    private String getExpressByHeight(int depth) {
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            str.append("— —");
        }
        return str.toString();
    }

5.测试

  • 思路：
    1.我们随机生成20个值，key范围在10000以内，value随意(笔者取范围100之内整数)，添加到我们自定义的平衡二叉树，来测试添加方法同时
    2.同时使用一个list记录这些随机的值，以测试删除方法。
    3.使用文中4部分的三个测试方法，分别测试执行添加，删除后，该自定义平衡二叉树是否满足性质
 /**
 * 对以平衡二叉树实现的映射进行测试
 *
 * @author xi fu
 * @date 2019/4/25 15:35
 * @since algorithm.collection.AVL.AVKTest
 */
public class AVKTest {

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        //构建自定义平衡二叉树
        AVLTree<Integer, Integer> avlTree = new AVLTree<>();
        //随机添加20个元素，并记录元素值
        Random random = new Random();
        for (int i = 0; i < 20; i++) {
            Integer num1 = random.nextInt(10000);
            Integer num2 = random.nextInt(100);
            avlTree.add(num1, num2);
            list.add(num1);
        }
        //测试添加后的平衡二叉树
        System.out.println("数量：" + avlTree.getSize());
        System.out.println("是否为二分搜索树：" + avlTree.isBST());
        System.out.println("是否为平衡二叉树：" + avlTree.isBalanced());
        
        //输出一下平衡二叉树
        System.out.println();
        System.out.println(avlTree);
        //执行删除
        System.out.println();
        for (int i = 5; i < list.size(); i++) {
            avlTree.remove(list.get(i));
        }
        //测试删除后的平衡二叉树
        System.out.println();
        System.out.println("删除元素后的平衡二叉树结构");
        System.out.println(avlTree);
        System.out.println();
        System.out.println("数量：" + avlTree.getSize());
    }

}

  • 测试结果


    平衡二叉树测试
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,088评论 5赞 459
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,715评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,361评论 0赞 319
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,099评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 60,987评论 4赞 355
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,063评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,486评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,175评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,440评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,518评论 2赞 309
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,305评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,190评论 3赞 312
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,550评论 3赞 298
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,880评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,152评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,451评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,637评论 2赞 335