数据结构--平衡二叉树

程序员文章站 2022-06-23 18:58:00

平衡二叉树又叫AVL树1. 性质 :可以是空树任意一个节点的左子树和右子树都是平衡二叉树且高度之差的绝对值 <=12.失衡的4种情况在结点的左子树的左子树插入元素,LL 插入；在结点的左子树的右子树插入元素,LR 插入；在结点的右子树的左子树插入元素,RL 插入；在结点的右子树的右子树插入元素,RR 插入;3.解决方法代码实现定义节点类和一些基本方法public class AVLTree { //当前树 private AvlNo....

平衡二叉树又叫AVL树

1. 性质 :

可以是空树
任意一个节点的左子树和右子树都是平衡二叉树且高度之差的绝对值 <=1

2.失衡的4种情况

在结点的左子树的左子树插入元素,LL 插入；
在结点的左子树的右子树插入元素,LR 插入；
在结点的右子树的左子树插入元素,RL 插入；
在结点的右子树的右子树插入元素,RR 插入;

3.解决方法代码实现

定义节点类和一些基本方法

public class AVLTree {
    //当前树
    private AvlNode tree;

    //获取节点高度
    public int hight(AvlNode node) {
        return node == null ? 0 : node.hight;
    }

    //获取树的高度
    public int hight() {
        return hight(tree);
    }

    //获取高度最大值
    private int getMaxHeight(int height1, int height2) {
        return height1 > height2 ? height1 : height2;
    }

    /**
     * 中序遍历
     * 先打印左子树
     * 然后打印自身
     * 最后打印右子树
     * @param node
     */
    public void inOrder(AvlNode node){
        if(node == null ){
            return;
        }
        inOrder(node.left);
        System.out.print(node.getValue()+"->");
        inOrder(node.right);
    }

    /**
     * 前序遍历
     * 先打印自身
     * 然后打印左子树
     * 最后打印右子树
     * @param node
     */
    public void preOrder(AvlNode node){
        if(node == null){
            return;
        }
        System.out.print(node.getValue()+"->");
        preOrder(node.left);
        preOrder(node.right);
    }
    /**
     * 后续遍历
     * 先打印左子树
     * 然后打印右子树
     * 最后打印自身
     * @param node
     */
    public void postOrder(AvlNode node){
        if(node == null){
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.getValue()+"->");
    }

    //avl树节点类
    private static class AvlNode {
        private int value;
        private AvlNode left;
        private AvlNode right;
        private int hight;//定义节点高度

        public AvlNode(int value, AvlNode left, AvlNode right, int hight) {
            this.value = value;
            this.left = left;
            this.right = right;
            this.hight = hight;
        }

        public AvlNode(int value, AvlNode left, AvlNode right) {
            this(value, left, right, 0);
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public AvlNode getLeft() {
            return left;
        }

        public void setLeft(AvlNode left) {
            this.left = left;
        }

        public AvlNode getRight() {
            return right;
        }

        public void setRight(AvlNode right) {
            this.right = right;
        }

        public int getHight() {
            return hight;
        }

        public void setHight(int hight) {
            this.hight = hight;
        }
    }
}

3.1LL : 左左旋转

数据结构--平衡二叉树

/**
     * LL
     *
     * @param node 失衡节点
     * @return 左旋后的根节点
     */
    public AvlNode llRotaing(AvlNode node) {
        AvlNode avl_lift = node.left;//失衡节点的左子树节点 旋转后的根节点
        //把失衡节点左子树的右子树节点挂到失衡节点的左子树上
        node.left = avl_lift.right;
        //把失衡节点作为该节点左子树的右子树
        avl_lift.right = node;
        //重新计算失衡节点和失衡节点左子树(即旋转后的根节点)旋转后的节点高度
        node.hight = getMaxHeight(hight(node.left), hight(node.right)) + 1;
        avl_lift.hight = getMaxHeight(hight(avl_lift.left), hight(avl_lift.right)) + 1;//得到左子树和右子树中最大的高度 + 1
        return avl_lift;
    }

3.2RR 右右旋转

数据结构--平衡二叉树

 /**
     * RR
     *
     * @param node 失衡节点
     * @return 右旋后的根节点
     */
    public AvlNode rrRotaing(AvlNode node) {
        AvlNode avl_right = node.right;//失衡节点的右子树节点 旋转后的根节点
        //把失衡节点右子树的左子树节点挂到失衡节点的右子树上
        node.right = avl_right.left;
        //把失衡节点作为该节点右子树的左子树
        avl_right.left = node;
        //重新计算失衡节点和失衡节点右子树(即旋转后的根节点)旋转后的节点高度
        node.hight = getMaxHeight(hight(node.left), hight(node.right)) + 1;
        avl_right.hight = getMaxHeight(hight(avl_right.left), hight(avl_right.right)) + 1;//得到左子树和右子树中最大的高度 + 1
        return avl_right;
    }

3.3 LR 左右旋转

数据结构--平衡二叉树

    /**
     * LR
     *  1. 先把失衡节点的左子树做一次rr旋转
     *  2. 把该数做一次ll旋转
     * @param node 失衡节点
     * @return
     */
    public AvlNode lrRotaing(AvlNode node){
        node.left = rrRotaing(node.left);
        AvlNode avlNode = llRotaing(node);
        return avlNode;
    }

3.4RL 右左旋转

数据结构--平衡二叉树

    /**
     * RL
     *  1. 先把失衡节点的右子树做一次ll旋转
     *  2. 把该数做一次rr旋转
     * @param node 失衡节点
     * @return
     */
    public AvlNode rlRotaing(AvlNode node){
        node.right = llRotaing(node.right);
        AvlNode avlNode = rrRotaing(node);
        return avlNode;
    }

3.5 添加方法

    /**
     * 添加方法
     *
     * @param value
     */
    public void insert(int value){
        this.tree = insert(tree,value);
    }

    private AvlNode insert(AvlNode node,int value){
        AvlNode p;//最左边或者最右边的节点  用于判断数是RR RL LL LR的那种失衡
        if (node == null){
            node = createNode(value,0);
        }else {
            if (value > node.value){
                node.right = insert(node.right, value);
                if (Math.abs(hight(node.right) - hight(node.left)) > 1) {//失衡类型为 RR or RL
                    p = node;
                    while (p.right != null){
                        p = p.right;
                    }
                    if (value == p.value) {//说明是RR
                        node = rrRotaing(node);
                    } else {
                        node = rlRotaing(node);
                    }
                }
            }else if (value < node.value){
                node.left = insert(node.left,  value);
                if (Math.abs(hight(node.right) - hight(node.left)) > 1) {//失衡类型为 LL or LR
                    p = node;
                    while (p.left != null){
                        p = p.left;
                    }
                    if (value == p.value) {//说明是LL
                        node = llRotaing(node);
                    } else {//否则为LR
                        node = lrRotaing(node);
                    }
                }
            }
        }
        node.hight = getMaxHeight(hight(node.left), hight(node.right)) + 1;
        return node;
    }

3.5 断点测试

    public static void main(String[] args) {
        AVLTree avlTree = new AVLTree();
        avlTree.insert(10);
        avlTree.insert(8);
        avlTree.insert(3);
        avlTree.insert(12);
        avlTree.insert(9);
        avlTree.insert(4);
        avlTree.insert(5);
        avlTree.insert(7);
        avlTree.insert(1);
        avlTree.insert(11);
        avlTree.insert(17);

    }

4.完整代码

public class AVLTree {

    public static void main(String[] args) {
        AVLTree avlTree = new AVLTree();
        avlTree.insert(10);
        avlTree.insert(8);
        avlTree.insert(3);
        avlTree.insert(12);
        avlTree.insert(9);
        avlTree.insert(4);
        avlTree.insert(5);
        avlTree.insert(7);
        avlTree.insert(1);
        avlTree.insert(11);
        avlTree.insert(17);

    }

    //根节点
    private AvlNode tree;

    private int i;

    /**
     * 添加方法
     *
     * @param value
     */
    public void insert(int value){
        this.tree = insert(tree,value);
    }

    private AvlNode insert(AvlNode node,int value){
        AvlNode p;
        if (node == null){
            node = createNode(value,0);
        }else {
            if (value > node.value){
                node.right = insert(node.right, value);
                if (Math.abs(hight(node.right) - hight(node.left)) > 1) {//失衡类型为 RR or RL
                    p = node;
                    while (p.right != null){
                        p = p.right;
                    }
                    if (value == p.value) {//说明是RR
                        node = rrRotaing(node);
                    } else {
                        node = rlRotaing(node);
                    }
                }
            }else if (value < node.value){
                node.left = insert(node.left,  value);
                if (Math.abs(hight(node.right) - hight(node.left)) > 1) {//失衡类型为 LL or LR
                    p = node;
                    while (p.left != null){
                        p = p.left;
                    }
                    if (value == p.value) {//说明是LL
                        node = llRotaing(node);
                    } else {//否则为LR
                        node = lrRotaing(node);
                    }
                }
            }
        }
        node.hight = getMaxHeight(hight(node.left), hight(node.right)) + 1;
        return node;
    }


    /**
     * LL
     *
     * @param node 失衡节点
     * @return 左旋后的根节点
     */
    public AvlNode llRotaing(AvlNode node) {
        AvlNode avl_lift = node.left;//失衡节点的左子树节点 旋转后的根节点
        //把失衡节点左子树的右子树节点挂到失衡节点的左子树上
        node.left = avl_lift.right;
        //把失衡节点作为该节点左子树的右子树
        avl_lift.right = node;
        //重新计算失衡节点和失衡节点左子树(即旋转后的根节点)旋转后的节点高度
        node.hight = getMaxHeight(hight(node.left), hight(node.right)) + 1;
        avl_lift.hight = getMaxHeight(hight(avl_lift.left), hight(avl_lift.right)) + 1;//得到左子树和右子树中最大的高度 + 1
        return avl_lift;
    }

    /**
     * RR
     *
     * @param node 失衡节点
     * @return 右旋后的根节点
     */
    public AvlNode rrRotaing(AvlNode node) {
        AvlNode avl_right = node.right;//失衡节点的右子树节点 旋转后的根节点
        //把失衡节点右子树的左子树节点挂到失衡节点的右子树上
        node.right = avl_right.left;
        //把失衡节点作为该节点右子树的左子树
        avl_right.left = node;
        //重新计算失衡节点和失衡节点右子树(即旋转后的根节点)旋转后的节点高度
        node.hight = getMaxHeight(hight(node.left), hight(node.right)) + 1;
        avl_right.hight = getMaxHeight(hight(avl_right.left), hight(avl_right.right)) + 1;//得到左子树和右子树中最大的高度 + 1
        return avl_right;
    }

    /**
     * LR
     * 1. 先把失衡节点的左子树做一次rr旋转
     * 2. 把该数做一次ll旋转
     *
     * @param node 失衡节点
     * @return
     */
    public AvlNode lrRotaing(AvlNode node) {
        node.left = rrRotaing(node.left);
        AvlNode avlNode = llRotaing(node);
        return avlNode;
    }

    /**
     * RL
     * 1. 先把失衡节点的右子树做一次ll旋转
     * 2. 把该数做一次rr旋转
     *
     * @param node 失衡节点
     * @return
     */
    public AvlNode rlRotaing(AvlNode node) {
        node.right = llRotaing(node.right);
        AvlNode avlNode = rrRotaing(node);
        return avlNode;
    }

    //获取节点高度
    public int hight(AvlNode node) {
        return node == null ? 0 : node.hight;
    }

    //获取树的高度
    public int hight() {
        return hight(tree);
    }

    //获取高度最大值
    private int getMaxHeight(int height1, int height2) {
        return height1 > height2 ? height1 : height2;
    }

    /**
     * 中序遍历
     * 先打印左子树
     * 然后打印自身
     * 最后打印右子树
     *
     * @param node
     */
    public void inOrder(AvlNode node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.print(node.getValue() + "->");
        inOrder(node.right);
    }

    /**
     * 前序遍历
     * 先打印自身
     * 然后打印左子树
     * 最后打印右子树
     *
     * @param node
     */
    public void preOrder(AvlNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.getValue() + "->");
        preOrder(node.left);
        preOrder(node.right);
    }

    /**
     * 后续遍历
     * 先打印左子树
     * 然后打印右子树
     * 最后打印自身
     *
     * @param node
     */
    public void postOrder(AvlNode node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.getValue() + "->");
    }

    public static AvlNode createNode(int value, AvlNode left, AvlNode right, int hight) {
        return new AvlNode(value, left, right, hight);
    }

    public static AvlNode createNode(int value, int hight) {
        return new AvlNode(value, null, null, hight);
    }

    public static AvlNode createNode(int value, AvlNode left, AvlNode right) {
        return new AvlNode(value, left, right);
    }

    public static AvlNode createNode(int value) {
        return new AvlNode(value, null, null);
    }

    //avl树节点类
    private static class AvlNode {
        private int value;
        private AvlNode left;
        private AvlNode right;
        private int hight;//定义节点高度

        public AvlNode(int value, AvlNode left, AvlNode right, int hight) {
            this.value = value;
            this.left = left;
            this.right = right;
            this.hight = hight;
        }

        public AvlNode(int value, AvlNode left, AvlNode right) {
            this(value, left, right, 0);
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public AvlNode getLeft() {
            return left;
        }

        public void setLeft(AvlNode left) {
            this.left = left;
        }

        public AvlNode getRight() {
            return right;
        }

        public void setRight(AvlNode right) {
            this.right = right;
        }

        public int getHight() {
            return hight;
        }

        public void setHight(int hight) {
            this.hight = hight;
        }
    }
}

本文地址：https://blog.csdn.net/weixin_45690436/article/details/109988508

上一篇：进程控制

下一篇： dos命令 cd命令使用说明[图文说明]

数据结构--平衡二叉树

1. 性质 :

2.失衡的4种情况

3.解决方法代码实现

3.1LL : 左左旋转

3.2RR 右右旋转

3.3 LR 左右旋转

3.4RL 右左旋转

3.5 添加方法

3.5 断点测试

4.完整代码

C#数据结构与算法揭秘五栈和队列

杨辉三角 | 回形数 | 复制 | 赋值数据结构介绍

java数据结构实现机器人行走

C#数据结构之循环链表的实例代码

JavaScript 处理树数据结构的方法示例

C#数据结构与算法揭秘三链表

C#数据结构揭秘一

C#数据结构与算法揭秘四双向链表

JS中数据结构与算法---排序算法(Sort Algorithm)实例详解

C#数据结构与算法揭秘二线性结构

数据结构--平衡二叉树

1. 性质 :

2.失衡的4种情况

3.解决方法 代码实现

3.1**LL : 左左旋转 **

3.2RR 右右旋转

3.3 LR 左右旋转

3.4RL 右左旋转

3.5 添加方法

3.5 断点测试

4.完整代码

C#数据结构与算法揭秘五 栈和队列

杨辉三角 | 回形数 | 复制 | 赋值数据结构介绍

java数据结构实现机器人行走

C#数据结构之循环链表的实例代码

JavaScript 处理树数据结构的方法示例

C#数据结构与算法揭秘三 链表

C#数据结构揭秘一

C#数据结构与算法揭秘四 双向链表

JS中数据结构与算法---排序算法(Sort Algorithm)实例详解

C#数据结构与算法揭秘二 线性结构

3.解决方法代码实现

3.1LL : 左左旋转

C#数据结构与算法揭秘五栈和队列

C#数据结构与算法揭秘三链表

C#数据结构与算法揭秘四双向链表

C#数据结构与算法揭秘二线性结构