关于java:我所知道数据结构之平衡二叉树

43次阅读

共计 12184 个字符，预计需要花费 31 分钟才能阅读完成。

前言需要介绍

咱们从一个 数列(1,2,3,4,5,6)，来阐明形成二叉排序树的一些问题

1. 左子树全副为空，从模式图所看，更像一个单链表
2. 查问速度明显降低(因为须要顺次比拟)，不能施展 BST
的劣势，因为每次还须要比拟左子树，其查问速度比单链表还慢

那么怎么办？

那么像这样的数列咱们能够是用解决方案 —>均衡二叉树(AVL)

一、什么是均衡二叉树

根本介绍

1. 均衡二叉树也叫均衡二叉搜寻树 (Self balancing binary searchtree) 又被称为AVL 树，能够保障查问效率较高。

有以下特点:
1. 它是一颗空树或它的左右两个子树的高度差相对超过 1
2. 左右两个子树都是一棵均衡二叉树。

均衡二叉树的罕用实现:红黑树、AVL(算法)、替罪羊树、Treap、舒展树 等。

哪些树是 AVL 树？为什么?

联合后面咱们介绍的 AVL 树特点剖析看看，当初你晓得了吗？

简略说来

均衡二叉树之所以将二叉排序树，调整为均衡状态，是为了在二叉排序树近似为链的状况下，加强其查找性能，升高工夫复杂度。

常见调整形式

常见的二叉均衡树调整均衡办法有：LL、LR、RR、RL

RR 型介绍

以后这种状况图三，链式就须要均衡调整，否则则影响到查问的效率

均衡调整：一个根节点与两左右子节点的 二叉排序树（如下图）

原本 Mar 节点再插入 May 时，还保持平衡：满足右子节点大于根节点

当插入 麻烦节点 Nov时平衡点被毁坏，且Nov 节点是在根节点的右子树的右子树上

依据二叉排序的个性：右子树节点比以后节点大

咱们找到Mar、May、Nov 的两头数，它们的大小关系是Mar<May<Nov

此时 将 May 作为根节点 ，Mar 作为左子树、Nov 作为右子树 进行调整

这时，这种 插入即称说为 RR 插入，均衡调整也成为RR 旋转（右单转）


LL 型介绍

当插入 麻烦节点 Apr时平衡点被毁坏，且Apr 节点是在 Mar 节点的左子树的左子树上

咱们找到Mar、Aug、Apr 的两头数，它们的大小关系是Apr<Aug<Mar

此时 将 Aug 作为根节点 ，Apr 作为左子树、Mar 作为右子树 进行调整

这时，这种 插入即称说为 LL 插入，均衡调整也成为LL 旋转（左单转）

当然 插入的节点也可能是左子节点或者右子节点

咱们发现其实进行旋转调整的时候呢

不肯定是根节点才进行旋转。在两头的节点 Mar 也是能够的

LR 介绍

当插入 麻烦节点 Jan时平衡点被毁坏，且Jan 节点是在 May 节点的左子树的右子树上

咱们找到May、Aug、Mar 的两头数，它们的大小关系是Aug<Mar<May

此时 将 Mar 作为根节点，Aug 作为左子树、May 作为右子树

且 Mar>Aug、Jan<Mar 依据个性Jan 作为 Aug 右子树 进行调整

这时，这种 插入即称说为 LR 插入，均衡调整也成为LR 旋转

RL 介绍

当插入 麻烦节点 Feb时平衡点被毁坏，且Feb 节点是在 Aug 节点的右子树的左子树上

咱们找到Jan、Aug、Dec 的两头数，它们的大小关系是Aug<Dec<Jan

此时 将 Dec 作为根节点，Aug 作为左子树、Jan 作为右子树

且 Jan>Dec、Feb>Dec 依据个性Feb 作为 Jan 左子树 进行调整

这时，这种 插入即称说为 RL 插入，均衡调整也成为RL 旋转

LL、RR、LR、RL 四种模式办法怎么判断？

即看插入节点把谁毁坏了，跟被毁坏节点是什么关系？

是右边的右边？左边的左边？还是右边的左边？左边的右边？

然而须要留神的是：均衡调整后仍为二叉排序树

二、通过示例意识均衡二叉树的右旋转

给你一个数列 {4,3,6,5,7,8}，让你可能 高效 的实现对 数据的查问和增加

那么依照咱们之前的思路，先构建：一颗二叉排序树

二叉排序树的特点？

非叶子节点特点：左子节点的值比以后节点的值小，右子节点的值比以后节点的值大。
特地阐明: 如果有 雷同的值 ，能够 将该节点放在左子节点或右子节点

回顾构建二叉排序树思路剖析

  • 判断左子节点的值是否比以后节点的值小
  • 否则判断右子节点的值比以后节点的值大
  • 递归判断是否合乎左子节点、右子节点的条件

那么咱们后面剖析了在二叉排序树近似为链的状况下

1. 从模式图所看，更像一个单链表
2. 查问速度明显降低(因为须要顺次比拟)，不能施展 BST 的劣势

所以咱们须要进行调整:均衡状态加强其查找性能，升高工夫复杂度

咱们发现这颗 二叉排序树左子树高度为 1，左边子树高度为 3

此时不合乎均衡二叉树的特点：它是一颗空树或它的左右两个子树的高度差相对超过 1

依据下面介绍的四种均衡调整模式介绍，目前比拟合乎的是RR 旋转

应用 RR 旋转图解案例思路剖析

咱们联合下面的图与 RR 旋转的思路一起来剖析以后的案例

未插入节点 8 时，还保持平衡：满足右子节点大于根节点

当插入 麻烦节点 8 时平衡点被毁坏，且 节点 8 是在根节点的右子树的右子树上

依据二叉排序的个性：右子树节点比以后节点大

咱们找到4、6、7 的两头数，它们的大小关系是 4 < 6 < 7

此时 将 6 作为根节点 ， 4 作为左子树、7 作为右子树 进行调整

RR 旋转代码实现思路剖析

  • 创立一个新节点 newNode 等于以后根节点 root，值相等

  • 新节点 newNode 的左子树设置为以后根节点 root 的左子树

  • 新节点 newNode 的 右子树 设置为以后根节点 root 的 右子树的左子树

  • 以后根节点 root 的值换为右子节点的值

  • 以后根节点 root 的右子树设置成根节点 root 的 右子树的右子树

  • 以后根节点 root 的左子树设置为新节点

示例代码实现

大家有没有发现，节点与子树之间的高度是要害的

并不是说退出一个节点得时候就进行旋转，而是 左右两个子树的高度差相对超过 1 才去进行均衡调整

所以须要先实现事件是：统计以后树的高度、统计与左子树、或右子树的高度

那么咱们用代码实际来统计：树的高度、左子树高度、右子树高度

(节点代码、AVL 代码可参考二叉排序树相干代码)

class Node{

    int value;
    Node left;
    Node right;

    public Node(int value) {this.value = value;}

    /**
     * @param value 心愿删除的结点的值
     * @return 如果找到返回该结点，否则返回 null
     */
    public Node search(int value) {if(value == this.value) { // 找到就是该结点
            return this;
        } else if(value < this.value) {// 如果查找的值小于以后结点，向左子树递归查找
            // 如果左子结点为空
            if(this.left == null) {return null;}
            return this.left.search(value);
        } else { // 如果查找的值不小于以后结点，向右子树递归查找
            if(this.right == null) {return null;}
            return this.right. search(value);
        }
    }

    public Node searchParent(int value){

        // 如果以后节点是须要删除节点的父节点则返回
        if((this.left!=null && this.left.value == value) ||
                (this.right!=null && this.right.value == value)){return this;}else{
            // 如果查找的值小于以后节点的值，并且以后节点的左子节点不为空
            if(value <this.value && this.left!=null){return this.left.searchParent(value);
            }else if(value >= this.value && this.right!=null){
                // 如果查找的值大于等于于以后节点的值，并且以后节点的右子节点不为空
                return  this.right.searchParent(value);
            }else {return null;// 没有找到父节点，比如说节点 7}
        }

    }

    // 增加节点办法
    // 递归形式增加节点，要满足二叉排序树的要求
    // 要求是：` 左子节点的值比以后节点的值小，右子节点的值比以后节点的值大。`
    public void add(Node node) {if (node == null) {return;}

        // 判断传入的节点的值，和以后节点值的关系

        // 增加的节点小于以后节点
        if (node.value < this.value) {if (this.left == null) {this.left = node;} else {this.left.add(node);
            }
        } else {// 增加的节点大于以后节点
            if (this.right == null) {this.right = node;} else {this.right.add(node);
            }
        }
    }

    @Override
    public String toString() {return "Node{" +"value=" + value +'}';
    }

    // 中序遍历
    public void infixOrder(){if(this.left != null){this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right != null){this.right.infixOrder();
        }
    }
}
class AVLTree {

    private Node root;

    public Node getRoot() {return root;}

    public void setRoot(Node root) {this.root = root;}

    // 增加节点的办法
    public  void add(Node node){if(root == null){root = node;}else{root.add(node);
        }
    }
    /**
     *  @param node 传入的节点（当做新二叉排序树的根节点）*  return 返回新跟节点的最小节点的值
     */
    public int delRigthTreeMin(Node node){

        Node target = node;

        // 循环的查找左子节点，找到最小值
        while(target.left!=null) {target = target.left;}
        // 删除最小值
        delNode(target.value);
        // 返回最小值
        return target.value;
    }


    public void delNode(int value){if(root == null){System.out.println("以后根节点为空！无奈删除节点！");
            return;
        }else{
            //1. 须要先找到删除的值的对应节点
            Node targetNode = search(value);

            // 如果没有找到须要删除的节点
            if(targetNode == null){System.out.println("对不起！没有找到删除节点信息！");
                return;
            }

            // 如果咱们发现根节点没有左子节点与右子节点
            if(root.left == null && root.right == null){
                root = null;
                return;
            }

            // 找到 targetNode 的父节点
            Node  parent = searchParent(value);

            // 如果删除节点是叶子节点
            if(targetNode.left == null && targetNode.right == null){

                // 判断删除节点是父节点的左子节点还是右子节点
                if(parent.left!= null && parent.left.value == targetNode.value){parent.left = null;}else if (parent.right!= null && parent.right.value == targetNode.value){parent.right = null;}
            }else if (targetNode.left != null && targetNode.right != null){int minValue = delRigthTreeMin(targetNode.right);
                targetNode.value = minValue;// 重置值

            }else{// 删除只有一颗子树的节点

                // 如果删除节点的子节点是左子节点
                if(targetNode.left !=null){if(parent!=null){
                        // 判断删除节点是父节点的左子节点还是右子节点
                        if(parent.left.value == targetNode.value){
                            // 将原删除节点的地位给到子节点
                            parent.left = targetNode.left;
                        }else if (parent.right.value == targetNode.value){
                            // 将原删除节点的地位给到子节点
                            parent.right = targetNode.left;
                        }
                    }else{root = targetNode.left;}
                }else if (targetNode.right != null){ // 如果删除节点的子节点是右子节点

                    if(parent!=null){
                        // 判断删除节点是父节点的左子节点还是右子节点
                        if(parent.left.value == targetNode.value){
                            // 将原删除节点的地位给到子节点
                            parent.left = targetNode.right;
                        }else if (parent.right.value == targetNode.value){
                            // 将原删除节点的地位给到子节点
                            parent.right = targetNode.right;
                        }
                    }else{root = targetNode.right;}
                }
            }

        }
    }

    // 查找须要删除节点的办法
    public Node search(int value){if(root == null){return null;}else{return root.search(value);
        }
    }
    // 查找须要删除节点的父节点信息
    public Node searchParent(int value){if(root == null){return null;}else{return root.searchParent(value);
        }
    }


    // 调用中序遍历的办法
    public void infixOrder(){if(root == null){System.out.println("以后二叉排序根节点为空，无奈遍历");
            return;
        }else{root.infixOrder();
        }
    }
}

如上图所示，咱们取的该这颗树的高度是为：3，算上根节点则是 4

所以咱们求该树的高度，须要晓得左节点与右节点的高度别离是多少

class Node{
    
    //...... 省略其余要害代码   
    
    // 返回以后节点的左子树的高度
    public int leftHigth(){if(left == null){return 0;}
        return left.hight();}
    
    // 返回以后节点的右子树的高度
    public int rightHight(){if(right == null){return 0;}
        return right.hight();}
    
    // 返回以后节点的高度，若算上根节点则须要 + 1 
    public int hight(){return Math.max(left == null? 0 : left.hight(),right == null?0:right.hight()) + 1;
    }
     
}

有没有发现，咱们须要晓得左子树的高度是多少

同时也须要晓得左子树的左子树与左边子树是多少 …..

这是一个始终递归的过程。

public static void main(String[] args) {int[] arr ={4,3,6,5,7,8};

    AVLTree avlTree = new AVLTree();
    for(int i = 0; i<arr.length; i++){avlTree.add(new Node(arr[i]));
    }

    // 遍历
    System.out.println("中序遍历");
    avlTree.infixOrder();


    // 节点高度
    System.out.println("算上跟节点高度为："+avlTree.getRoot().hight());
}

运行后果如下：中序遍历
Node{value=3}
Node{value=4}
Node{value=5}
Node{value=6}
Node{value=7}
Node{value=8}
算上跟节点高度为：4

咱们刚刚也说了，算上跟根节点高度就是 4，那么咱们看看左子树和右子树

// 节点高度
System.out.println("节点高度为："+avlTree.getRoot().hight());
// 节点高度
System.out.println("左节点高度为："+avlTree.getRoot().leftHigth());
// 节点高度
System.out.println("右节点高度为："+avlTree.getRoot().rightHight());

运行后果如下：节点高度为：4
左节点高度为：1
右节点高度为：3

咱们刚刚说到，左右两个子树的高度差相对超过 1 才去进行均衡调整，那么以后的状况则须要进行调整：右旋转

class Node{
    
    //...... 省略其余要害代码 
    //RR 旋转办法
    private void RightRotate(){

        // 创立一个新节点 newNode 等于以后根节点 root，值相等
        Node newNode = new Node(value);

        // 新节点 newNode 的左子树设置为以后根节点 root 的左子树
        newNode.left = left;

        // 新节点 newNode 的右子树设置为以后根节点 root 的右子树的左子树
        newNode.right = right.left;

        // 以后根节点 root 的值换为右子节点的值
        value = right.value;

        // 以后根节点 root 的右子树设置成根节点 root 的右子树的右子树
        right = right.right;

        // 以后根节点 root 的左子树设置为新节点
        left = newNode;
    }
    
    // 优化增加节点操作
    public void add(Node node) {if (node == null) {return;}

        // 判断传入的节点的值，和以后节点值的关系

        // 增加的节点小于以后节点
        if (node.value < this.value) {if (this.left == null) {this.left = node;} else {this.left.add(node);
            }
        } else {// 增加的节点大于以后节点
            if (this.right == null) {this.right = node;} else {this.right.add(node);
            }
        }

        // 当增加完一个节点后：如果（右子树的高度 - 左子树的高度）> 1 则执行 RR 旋转
        if(rightHight() - leftHigth() > 1){RightRotate();// 执行 RR 旋转
        }
    }
}

接下来咱们实际看看，当增加节点满足条件是否会进行均衡调整

public static void main(String[] args) {int[] arr ={4,3,6,5,7,8};

        AVLTree avlTree = new AVLTree();
        for(int i = 0; i<arr.length; i++){avlTree.add(new Node(arr[i]));
        }

        // 遍历
        System.out.println("中序遍历");
        avlTree.infixOrder();


        // 节点高度
        System.out.println("节点高度为："+avlTree.getRoot().hight());
        // 节点高度
        System.out.println("左节点高度为："+avlTree.getRoot().leftHigth());
        // 节点高度
        System.out.println("右节点高度为："+avlTree.getRoot().rightHight());
}

运行后果如下：中序遍历
Node{value=3}
Node{value=4}
Node{value=5}
Node{value=6}
Node{value=7}
Node{value=8}
节点高度为：3
左节点高度为：2
右节点高度为：2

这时咱们进行均衡调整，从左右两个子树的高度差没有超过 1 了。

三、通过示例意识均衡二叉树的左旋转

给你一个数列 {10,12,8,9,7,6}，让你可能 高效 的实现对 数据的查问和增加

那么依照咱们之前的思路，先构建：一颗二叉排序树

二叉排序树的特点？

非叶子节点特点：左子节点的值比以后节点的值小，右子节点的值比以后节点的值大。
特地阐明: 如果有 雷同的值 ，能够 将该节点放在左子节点或右子节点

回顾构建二叉排序树思路剖析

  • 判断左子节点的值是否比以后节点的值小
  • 否则判断右子节点的值比以后节点的值大
  • 递归判断是否合乎左子节点、右子节点的条件

咱们发现这颗 二叉排序树左子树高度为 3，左边子树高度为 1

此时不合乎均衡二叉树的特点：它是一颗空树或它的左右两个子树的高度差相对超过 1

依据下面介绍的四种均衡调整模式介绍，目前比拟合乎的是LL 旋转

依据咱们后面的示例教训，咱们能够间接进行实现思路剖析

  • 创立一个新节点 newNode 等于以后根节点 root，值相等

  • 新节点 newNode 的右子树设置为以后根节点 root 的右子树

  • 新节点 newNode 的 左子树 设置为以后根节点 root 的 左子树的右子树

  • 以后根节点 root 的值换为左子节点的值

  • 以后根节点 root 的左子树设置成根节点 root 的 左子树的左子树

  • 以后根节点 root 的右子树设置为新节点

示例代码实现

class Node{
    
    //...... 省略其余要害代码   
    
    //LL 旋转办法
    private void leftRotate(){

        // 创立一个新节点 newNode 等于以后根节点 root，值相等
        Node newNode = new Node(value);
        // 新节点 newNode 的右子树设置为以后根节点 root 的右子树
        newNode.right = right;
        // 新节点 newNode 的 ` 左子树 ` 设置为以后根节点 root 的 ` 左子树的右子树 `
        newNode.left = left.right;
        // 以后根节点 root 的值换为左子节点的值
        value = left.value;
        // 以后根节点 root 的左子树设置成根节点 root 的 ` 左子树的左子树 `
        left = left.left;
        // 以后根节点 root 的右子树设置为新节点
        right = newNode; 
    }
    
    // 优化增加节点操作
    public void add(Node node) {if (node == null) {return;}

        // 判断传入的节点的值，和以后节点值的关系

        // 增加的节点小于以后节点
        if (node.value < this.value) {if (this.left == null) {this.left = node;} else {this.left.add(node);
            }
        } else {// 增加的节点大于以后节点
            if (this.right == null) {this.right = node;} else {this.right.add(node);
            }
        }

        // 当增加完一个节点后：如果（右子树的高度 - 左子树的高度）> 1 则执行 RR 旋转
        if(rightHight() - leftHigth() > 1){RightRotate();// 执行 RR 旋转
        }
        // 当增加完一个节点后：如果（左子树的高度 - 右子树的高度）> 1 则执行 LL 旋转
        if(leftHigth() - rightHight() > 1){leftRotate();// 执行 LL 旋转
        }
    }
}

接下来咱们 Demo 测试一下为调整之前的高度别离是多少

public static void main(String[] args) {//int[] arr ={4,3,6,5,7,8};

    int[] arr ={10,12,8,9,7,6};

    AVLTree avlTree = new AVLTree();
    for(int i = 0; i<arr.length; i++){avlTree.add(new Node(arr[i]));
    }

    // 遍历
    System.out.println("中序遍历");
    avlTree.infixOrder();

    // 节点高度
    System.out.println("节点高度为："+avlTree.getRoot().hight());
    // 节点高度
    System.out.println("左节点高度为："+avlTree.getRoot().leftHigth());
    // 节点高度
    System.out.println("右节点高度为："+avlTree.getRoot().rightHight());
}

运行后果如下：中序遍历
Node{value=6}
Node{value=7}
Node{value=10}
Node{value=9}
Node{value=8}
Node{value=12}
节点高度为：3
左节点高度为：2
右节点高度为：2

这时咱们进行均衡调整，从左右两个子树的高度差没有超过 1 了。

四、通过示例意识均衡二叉树的双旋转

给你一个数列 {10,11,7,6,8,9}，让你可能 高效 的实现对 数据的查问和增加

那么依照咱们之前的思路，先构建：一颗二叉排序树

咱们发现这颗 二叉排序树左子树高度为 3，左边子树高度为 1

此时不合乎均衡二叉树的特点：它是一颗空树或它的左右两个子树的高度差相对超过 1

依照咱们之前思路适宜的是 LL 旋转，那么咱们执行左旋后的样子发现是

那么呈现这种问题的起因是什么呢？
剖析 1：退出节点九时，左子树（节点 7）的树高度 > 右子树 (节点 11) 的高度
剖析 2：左子树高度 – 右子树高度 >1 触发 LL 旋转，就变成下面那样了


那么咱们能够依据下面的 LR 介绍能够猜到一些思路，解决这个问题.

咱们在合乎：执行 LL 旋转时条件时
思路 1. 获取左子树的右子树（节点 8）高度，取名为：k
思路 2. 获取左子树（节点 7）的高度，取名为：J
思路 3. 如果 k > J，对左子树进行 RR 旋转
思路 4. 如果 k < J，间接进行 LL 旋转

简略的一句话：如果 K >J，则先旋转子树再旋转本人

同时咱们在合乎：执行 RR 旋转时条件时
思路 1. 获取右子树的左子树高度，取名为：U
思路 2. 获取右子树（节点 11）的高度，取名为：L
思路 3. 如果 U > L，对右子树进行 LL 旋转
思路 4. 如果 U < L，间接进行 RR 旋转

class Node{
    
    //...... 省略其余要害代码   
    
    // 优化增加节点操作
    public void add(Node node) {if (node == null) {return;}

        // 判断传入的节点的值，和以后节点值的关系
        // 增加的节点小于以后节点
        if (node.value < this.value) {if (this.left == null) {this.left = node;} else {this.left.add(node);
            }
        } else {// 增加的节点大于以后节点
            if (this.right == null) {this.right = node;} else {this.right.add(node);
            }
        }
        // 当增加完一个节点后：如果（右子树的高度 - 左子树的高度）> 1 则执行 RR 旋转
        if(rightHight() - leftHigth() > 1){
            // 获取它的右子树的左子树的高度 取名 U，获取它的右子树高度 L
            // 如果 u > l 执行 LL 旋转
            if(right != null && right.leftHigth()> right.rightHight()){right.leftRotate();// 执行 LL 旋转
                RightRotate();// 执行 RR 旋转}else{RightRotate();
            }
            return;// 避免接着往下走
        }
        // 当增加完一个节点后：如果（左子树的高度 - 右子树的高度）> 1 则执行 LL 旋转
        if(leftHigth() - rightHight() > 1){
            // 获取左子树的右子树高度，取名为：k 获取左子树的高度，取名为：J
            // 如果 k > J，对左子树进行 RR 旋转
            if(left != null && left.rightHight() > left.leftHigth()){left.RightRotate();// 执行 RR 旋转
                leftRotate();// 执行 LL 旋转}else{leftRotate();// 执行 LL 旋转
            }
        }
    
    }
}

接下来让咱们应用 Demo 验证一下咱们的思路

public static void main(String[] args) {//int[] arr ={4,3,6,5,7,8};

    int[] arr ={10,12,8,9,7,6};

    AVLTree avlTree = new AVLTree();
    for(int i = 0; i<arr.length; i++){avlTree.add(new Node(arr[i]));
    }

    // 遍历
    System.out.println("中序遍历");
    avlTree.infixOrder();

    // 节点高度
    System.out.println("节点高度为："+avlTree.getRoot().hight());
    // 节点高度
    System.out.println("左节点高度为："+avlTree.getRoot().leftHigth());
    // 节点高度
    System.out.println("右节点高度为："+avlTree.getRoot().rightHight());
    System.out.println("右节点高度为："+avlTree.getRoot().rightHight());
    System.out.println("以后根节点为："+avlTree.getRoot());
    System.out.println("以后根节点的左节点为："+avlTree.getRoot().left);
    System.out.println("以后根节点的右节点为："+avlTree.getRoot().right);
}

运行后果如下：中序遍历
Node{value=6}
Node{value=7}
Node{value=8}
Node{value=9}
Node{value=10}
Node{value=11}
节点高度为：3
左节点高度为：2
右节点高度为：2
以后根节点为：Node{value=8}
以后根节点的左节点为：Node{value=7}
以后根节点的右节点为：Node{value=10}

正文完
java
发表至： java
2020-12-07
 0
关于java:深入理解Java的继承特性
从源码学习设计模式之模板方法
关于java:JAVA基础之java简单命令
死磕-java原子类之AtomicStampedReference源码分析