Java实现,平衡二叉树的插入删除操作
本文最后更新于 143 天前,其中的信息可能已经有所发展或是发生改变。

一:前言

学了半个暑假,平衡二叉树算是最恶心人的一个部分了,他的各种转向的可能性的判断确实让人难受,但是还是挺过来了。。。。一部分吧。。。

二:平衡树概念简述

平衡树计算机科学中的一类数据结构,为改进的二叉查找树。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离(即深度),因此当结点的深度普遍较大时,查询的均摊复杂度会上升[1]。为了实现更高效的查询,产生了平衡树

不平衡的树结构

在这里,平衡指所有叶子的深度趋于平衡,更广义的是指在树上所有可能查找的均摊复杂度偏低。

 

1.结点代码

**
 * .
 * \* @author: xiaoyu
 * \* Date: 2021/8/27 TODO 平衡二叉树
 * \* Time: 22:28
 * \
 */
public class Node {
    //数据
    int data;
    //左指针
    Node child;
    //右指针
    Node brother;

    //当前节点高度
    int height;

    public int getHeight() {
        return height;
    }

    public void setHeight(int height) {
        this.height = height;
    }

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

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getChild() {
        return child;
    }

    public void setChild(Node child) {
        this.child = child;
    }

    public Node getBrother() {
        return brother;
    }

    public void setBrother(Node brother) {
        this.brother = brother;
    }
}

 

2.插入操作

 

/**
 * .
 * \* @author: xiaoyu
 * \* Date: 2021/8/27
 * \* Time: 22:31
 * \
 */
public class AVLTree {
    //根节点
    Node root;

    //为什么不用初始化,或者添加最大元素等数据
    /**
     * 插入操作,用户调用
     */
    public void insert(int data){
        this.root = insert(data,root);
    }
    /**
     * 插入操作 递归插入
     * @param data 要插入的结点数据
     * @param node  根节点
     * @return
     */

    public Node insert(int data,Node node){
        if (node == null){
            node = new Node(data);
        }

        if(node.getData()>data){
            node = insert(data,node.getChild());
            if (height(node.getChild()) - height(node.getBrother()) == 2){
                //判断是左孩子还是又孩子,如果是又孩子,则先右旋
                if (node.getChild().getData()>data){
                    //右旋操作
                    node = rightRotate(node);
                }else{
                    //左旋操作
                    node = leftRotate(node);
                }


            }
        }
        if (node.getData()<data){
            node = insert(data,node.getBrother());
            if (height(node.getChild()) - height(node.getBrother()) ==2){
                //
            }
        }
        //重新判断每个节点的高度
//        node.height = height(node) + 1;
        node.height = Math.max(height(node.getChild()),height(node.getBrother()));
        return node;
    }

    /**
     * 右旋操作 新增结点插入的根节点的左子树的左孩子
     * @param node  从这个结点开始 旋转
     * @return  根节点
     */


    public Node rightRotate(Node node){
        //先获取节点的左子树
        Node lefttree = node.getChild();
        //节点的左节点为子树的右节点
        node.setChild(lefttree.getBrother());
        //节点的右子树为节点
        lefttree.setBrother(node);
        //重新排序
        lefttree.height = Math.max(height(lefttree.getChild()),height(lefttree.getBrother())) + 1;
        //根节点的重新排序
        node.height = Math.max(height(node.getChild()),height(node.getBrother())) + 1;
        return lefttree;
    }
    /**
     * 左旋 新增结点插入根节点的右子树的右孩子
     * @param node 结点
     * @return  根节点
     */
    public Node leftRotate(Node node){
        //先获取节点的右子树
        Node righttree = node.getBrother();
        //节点的右节点为右子树的左孩子
        node.setBrother(righttree.getChild());
        //右子树的左节点为根节点
        righttree.setChild(node);
        //重新计算高度
        righttree.height = Math.max(height(righttree.getBrother()),height(righttree.getChild()));
        //重新计算根节点高度
        node.height = Math.max(height(node.getChild()),height(node.getBrother()));
        return righttree;
    }

    /**
     * 先左旋 在右旋
     * 左旋:找到最近的不平衡节点,对其左子树进行左旋
     * 右旋:对不平衡结点右旋
     * @return
     */
    public Node leftRightRatate(Node node){
        node.setChild(leftRotate(node.getChild()));

        return rightRotate(node);
    }
    public Node rightLeftRatate(Node node){
        node.setChild(rightRotate(node.getBrother()));
        return leftRotate(node);
    }



    /**
     * 高度的判断非常的巧妙,值得去吸收和学习
     * @param node
     * @return
     */
    public int height(Node node){
        return node == null ? -1 : node.getHeight();
    }
    /**
     * 遍历,采用前继遍历
     */
    public void preTraverse(){
        preTraverse(root);
    }
    public void preTraverse(Node node){
        if(node != null){
            System.out.println(node.data + "");
        }
        //访问左子树
        preTraverse(node.getChild());
        preTraverse(node.getBrother());
    }
}

 

75%

 

 

 

 

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇