devbox
AllinToyou
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

平衡二叉树（Java实现）_高度平衡二叉树 java

作者：AllinToyou | 2024-05-27 13:24:52

赞

踩

高度平衡二叉树 java

1、什么是平衡二叉树

平衡因子（Balance Factor）

简称BF：BF(T) = h(l) - h(r），其中 h(l)和 h(r）分别是T的左、右子树的高度。

平衡二叉树（Balance Binary Tree）（AVL树）

空树，或者任一节点左、右子树的高度绝对值不超过1，|BF(T)|<=1。本质是一颗改进后的二叉搜索树。

2、平衡二叉树的调整

RR旋转
在这里插入图片描述

RR旋转代码实现：
	//必须要有一个右节点
	//将A和B做右单旋，且更新A和B的树高度
	//返回新的根节点B
	private AVLNode singleRightRotation(AVLNode A) {
		AVLNode B = A.right;
        A.right = B.left;
        B.left = A;
        A.height = Math.max(getHeight(A.left),getHeight(A.right))+1;
        B.height = Math.max(getHeight(B.right),A.height)+1;
        return B;
   }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

LL旋转
在这里插入图片描述

LL旋转代码实现：
	private AVLNode singleLeftRotation(AVLNode A) {
		AVLNode B = A.left;
        A.left=B.right;
        B.right=A;
        A.height = Math.max(getHeight(A.left),getHeight(A.right))+1;
        B.height = Math.max(getHeight(B.left),A.height)+1;
        return B;
   }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

LR旋转
在这里插入图片描述

LR旋转代码实现：
	//A必须有一个左节点B，而B必须有一个右节点C
	//A、B分别和C做两次单旋，返回新的根节点C
	private AVLNode DoubleLeftRightRotation(AVLNode A) {
		//B和C做单右旋，返回根节点C
        A.left = singleRightRotation(A.left);
        //A和C做但左旋，返回根节点C
        return singleLeftRotation(A);
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

RL旋转
在这里插入图片描述

RL旋转代码实现：
	public AVLNode DoubleRightLeftRotation(AVLNode A) {
        A.right = singleLeftRotation(A.right);
        return singleRightRotation(A);
    }

  • 1
  • 2
  • 3
  • 4

3、平衡二叉树的插入节点

平衡二叉树的插入和二叉搜索树的插入区别？
相同点：都是从根节点开始判断，通过递归方式往下判断，直至找到插入位置然后插入节点。
不同点：根据平衡二叉树定义，平衡因子不能超过1，所以对于插入后的平衡二叉树需要判断是否需要平衡调整。判断时机是在递归结束返回的过程中，判断当前节点的平衡因子绝对值是否等于2，如果是的话，做平衡调整。最后跟新当前节点的树高度。（从树的叶子节点开始一直往上判断、调整直至平衡）

插入代码实现：
public AVLNode insert(AVLNode node,int value) {
        if (node==null) {
            node = new AVLNode(value);
        }else {
            if (value<node.value) {
            node.left = insert(node.left, value);
            if(getHeight(node.left)-getHeight(node.right)==2) {
                if (value<node.left.value) {
                    node = singleLeftRotation(node);
                }else if (value>node.left.value) {
                    node = DoubleLeftRightRotation(node);
                }
            }
            }else if (value>node.value) {
                node.right = insert(node.right, value);
                if (getHeight(node.left) - getHeight(node.right) == -2) {
                    if (value > node.right.value) {
                        node = singleRightRotation(node);
                    } else if (value < node.right.value) {
                        node = DoubleRightLeftRotation(node);
                    }
                }
            }
            //跟新当前节点树高度
            updateHeight(node);
        }
        return node;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

4、平衡二叉树的删除节点

1、删除节点
平衡二叉树删除节点存在三种情况

  1. 删除的节点为叶子节点
  2. 删除的节点只存在左子树或者只存在右子树
  3. 删除的节点同时存在左子树和右子树

2、在递归返回过程中做平衡调整

删除节点代码实现：
  private AVLNode delete(int value) {
        //删除节点
        return delete(this, value);
   
    }

  • 1
  • 2
  • 3
  • 4
  • 5

删除节点代码

 /**
     * 递归查找后删除节点,并且在递归返回过程中做平衡调整
     * @param node
     * @param value
     * @return
     */
    private AVLNode delete(AVLNode node,int value) {
       if (node.value == value) {
           node = removeNode(node);
       }else {
           if (value < node.value) {
               node.left = delete(node.left, value);
               //实际上删除左子树上节点导致不平衡只有两种情况‘
               // 1、删除后当前节点要单右旋
               //2、删除后当前节点要左右旋
               if (getHeight(node.left) - getHeight(node.right) == -2) {
                   if (node.right.left == null) {
                       node = singleRightRotation(node);
                   } else {
                       node = DoubleRightLeftRotation(node);
                   }
               }
           } else if (value > node.value) {
               node.right = delete(node.right, value);
               //同理可以推断出
               if (getHeight(node.left) - getHeight(node.right) == 2) {
                   if (node.left.right == null) {
                       node = singleLeftRotation(node);
                   } else {
                       node = DoubleLeftRightRotation(node);
                   }
               }
           }
           updateHeight(node);
       }
       return node;
    }

    /**
     * 节点删除的三种情况
     * @param node
     * @return
     */
    private AVLNode removeNode(AVLNode node) {
        //删除的节点为叶子节点
        if (node.left==null && node.right==null) {
            node =null;
        } else if (node.left==null || node.right==null){ //删除的节点只有左子树或者是右子树
            if (node.left==null) {
                node = node.right;
            }else {
                node = node.left;
            }
        } else { //删除的节点既有左子树又有右子树（需要获取左子树的最大节点或者右子树的最小节点替换）
            /**
             * 1、此处获取左子树最大节点的父节点
             * 2、获取父节点的右节点
             * 3、如果没有右节点，那么取父节点未左子树最大节点
             */
            AVLNode leftChrildMaxParent = getLeftChrildMax(node.left);
            AVLNode leftChrildMax = leftChrildMaxParent.right;
            if (leftChrildMax == null) {
                leftChrildMax = leftChrildMaxParent;
                leftChrildMax.right = node.right;
            }else {
                leftChrildMax.left = node.left;
                leftChrildMax.right = node.right;
                leftChrildMaxParent.right = null;
            }
            node = leftChrildMax;
        }
        return node;
    }
    private AVLNode getLeftChrildMax(AVLNode node) {
        if (node==null) {
            return null;
        }
        AVLNode parentNode = node;
        AVLNode chrildNode = parentNode.right;
        while (chrildNode!=null) {
            if (chrildNode.right!=null) {
                parentNode = chrildNode;
                chrildNode = chrildNode.right;
            }else {
                break;
            }
        }
        return parentNode;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89

平衡二叉树调整方法

  /**
     * 平衡二叉树调整方法
     * @param node
     * @return
     */
    private AVLNode reviseNode(AVLNode node) {
        if (node==null) {
            return null;
        }else {
            node.left = reviseNode(node.left);
            node.right = reviseNode(node.right);
            if(getHeight(node.left)-getHeight(node.right)==2) {
                if (node.left.right==null) {
                    node = singleLeftRotation(node);
                }else  {
                    node = DoubleLeftRightRotation(node);
                }
            }else if (getHeight(node.left)-getHeight(node.right)==-2) {
                if (node.right.left==null) {
                    node = singleRightRotation(node);
                }else {
                    node = DoubleRightLeftRotation(node);
                }
            }
            updateHeight(node);
            return node;
        }
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

5、 平衡二叉树全部代码

/**
 * 平衡二叉树实现
 */
public class AVLNode {
    private AVLNode left;

    private AVLNode right;

    private Integer value;

   private int height;

    public AVLNode() {}
    public AVLNode(Integer value) {
        this(value,null,null,0);
    }
    public AVLNode(AVLNode node) {
        this.value = node.value;
        this.left = node.left;
        this.right = node.right;
        this.height = node.height;
    }

    public AVLNode(Integer value,AVLNode left,AVLNode right,int height) {
        this.value = value;
        this.left = left;
        this.right = right;
        this.height = height;
    }


    public AVLNode insert(AVLNode node,int value) {
        if (node==null) {
            node = new AVLNode(value);
        }else {
            if (value<node.value) {
            node.left = insert(node.left, value);
            if(getHeight(node.left)-getHeight(node.right)==2) {
                if (value<node.left.value) {
                    node = singleLeftRotation(node);
                }else if (value>node.left.value) {
                    node = DoubleLeftRightRotation(node);
                }
            }
            }else if (value>node.value) {
                node.right = insert(node.right, value);
                if (getHeight(node.left) - getHeight(node.right) == -2) {
                    if (value > node.right.value) {
                        node = singleRightRotation(node);
                    } else if (value < node.right.value) {
                        node = DoubleRightLeftRotation(node);
                    }
                }
            }
            updateHeight(node);
        }
        return node;
    }

    public AVLNode find(int value) {
        if (this == null) return null;
        AVLNode node = this;
        while (node!=null) {
            if (node.value == value) {
                return node;
            }else if (value<node.value) {
                node = node.left;
            }else {
                node = node.right;
            }
        }
        return node;
    }

    private AVLNode delete(int value) {
        return delete(this, value);
    }

    /**
     * 递归查找后删除节点
     * @param node
     * @param value
     * @return
     */
    private AVLNode delete(AVLNode node,int value) {
       if (node.value == value) {
           node = removeNode(node);
       }else {
           if (value < node.value) {
               node.left = delete(node.left, value);
               //实际上删除左子树上节点导致不平衡只有两种情况‘
               // 1、删除后当前节点要单右旋
               //2、删除后当前节点要左右旋
               if (getHeight(node.left) - getHeight(node.right) == -2) {
                   if (node.right.left == null) {
                       node = singleRightRotation(node);
                   } else {
                       node = DoubleRightLeftRotation(node);
                   }
               }
           } else if (value > node.value) {
               node.right = delete(node.right, value);
               if (getHeight(node.left) - getHeight(node.right) == 2) {
                   if (node.left.right == null) {
                       node = singleLeftRotation(node);
                   } else {
                       node = DoubleLeftRightRotation(node);
                   }
               }
           }
           updateHeight(node);
       }
       return node;
    }

    /**
     * 节点删除
     * @param node
     * @return
     */
    private AVLNode removeNode(AVLNode node) {
        //删除的节点为叶子节点
        if (node.left==null && node.right==null) {
            node =null;
        } else if (node.left==null || node.right==null){ //删除的节点只有左子树或者是右子树
            if (node.left==null) {
                node = node.right;
            }else {
                node = node.left;
            }
        } else { //删除的节点既有左子树又有右子树（需要获取左子树的最大节点或者右子树的最小节点替换）
            /**
             * 1、获取左子树最大节点的父节点
             * 2、获取父节点的右节点
             * 3、如果没有右节点，那么取父节点未左子树最大节点
             */
            AVLNode leftChrildMaxParent = getLeftChrildMax(node.left);
            AVLNode leftChrildMax = leftChrildMaxParent.right;
            if (leftChrildMax == null) {
                leftChrildMax = leftChrildMaxParent;
                leftChrildMax.right = node.right;
            }else {
                leftChrildMax.left = node.left;
                leftChrildMax.right = node.right;
                leftChrildMaxParent.right = null;
            }
            node = leftChrildMax;

        }
        return node;
    }
    private AVLNode getLeftChrildMax(AVLNode node) {
        if (node==null) {
            return null;
        }
        AVLNode parentNode = node;
        AVLNode chrildNode = parentNode.right;
        while (chrildNode!=null) {
            if (chrildNode.right!=null) {
                parentNode = chrildNode;
                chrildNode = chrildNode.right;
            }else {
                break;
            }

        }
        return parentNode;
    }

    /**
     * 平衡二叉树调整方法
     * @param node
     * @return
     */
    private AVLNode reviseNode(AVLNode node) {
        if (node==null) {
            return null;
        }else {
            node.left = reviseNode(node.left);
            node.right = reviseNode(node.right);
            if(getHeight(node.left)-getHeight(node.right)==2) {
                if (node.left.right==null) {
                    node = singleLeftRotation(node);
                }else  {
                    node = DoubleLeftRightRotation(node);
                }
            }else if (getHeight(node.left)-getHeight(node.right)==-2) {
                if (node.right.left==null) {
                    node = singleRightRotation(node);
                }else {
                    node = DoubleRightLeftRotation(node);
                }
            }
            updateHeight(node);
            return node;
        }
    }

    private AVLNode DoubleLeftRightRotation(AVLNode A) {
        A.left = singleRightRotation(A.left);
        return singleLeftRotation(A);
    }

    public AVLNode DoubleRightLeftRotation(AVLNode A) {
        A.right = singleLeftRotation(A.right);
        return singleRightRotation(A);
    }

    private AVLNode singleLeftRotation(AVLNode A) {
        AVLNode B = A.left;
        A.left=B.right;
        B.right=A;
        A.height = Math.max(getHeight(A.left),getHeight(A.right))+1;
        B.height = Math.max(getHeight(B.left),A.height)+1;
        return B;
    }
    private AVLNode singleRightRotation(AVLNode A) {
        AVLNode B = A.right;
        A.right = B.left;
        B.left = A;
        A.height = Math.max(getHeight(A.left),getHeight(A.right))+1;
        B.height = Math.max(getHeight(B.right),A.height)+1;
        return B;
    }

    /**
     * 前序遍历
     * @return
     */
    public void toString(AVLNode node) {
        if (node==null) {
            return ;
        }
        System.out.print(node.value+" ");
        toString(node.left);
        toString(node.right);
    }

    private int getHeight(AVLNode node) {
        if(node==null) {
            return -1;
        }else {
            int leftH = getHeight(node.left);
            int rightH = getHeight(node.right);
            return Math.max(leftH,rightH)+1;
        }
    }
    private void updateHeight(AVLNode node) {
        node.height = getHeight(node);
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/632218
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号