文档章节

数据算法之二叉树平衡(BinTreeNode Rotate)的Java实现

C
 Claroja
发布于 2017/05/08 23:22
字数 629
阅读 9
收藏 0

  本文的代码来自于《数据结构与算法(JAVA语言版)》,是笔者在网上找到的资料,非正式出刊版物。笔者对代码一些比较难以理解的部分添加了注释和图解,欢迎大家来讨论。
  二叉树平衡的基本思想是通过旋转使得平衡因子的绝对值小于1。
  如图所示:


二叉树平衡


输入:失衡的结点z
输出:平衡后子树的根结点

private BinTreeNode rotate(BinTreeNode z){
    BinTreeNode y = higherSubT(z); //取y 为z 更高的孩子
    BinTreeNode x = higherSubT(y); //取x 为y 更高的孩子
    boolean isLeft = z.isLChild(); //记录:z 是否左孩子
    BinTreeNode p = z.getParent(); //p 为z 的父亲
    BinTreeNode a, b, c; //自左向右,三个节点
    BinTreeNode t0, t1, t2, t3; //自左向右,四棵子树
    // 以下分四种情况重命名
    if (y.isLChild()) { //若y 是左孩子,则
        c = z; t3 = z.getRChild();
        if (x.isLChild()) { //若x 是左孩子(左左失衡)
            b = y; t2 = y.getRChild();
            a = x; t1 = x.getRChild(); t0 = x.getLChild();
        } else { //若x 是右孩子(左右失衡)
            a = y; t0 = y.getLChild();
            b = x; t1 = x.getLChild(); t2 = x.getRChild();
        }
    } else { //若y 是右孩子,则
        a = z; t0 = z.getLChild();
        if (x.isRChild()) { //若x 是右孩子(右右失衡)
            b = y; t1 = y.getLChild();
            c = x; t2 = x.getLChild(); t3 = x.getRChild();
        } else { //若x 是左孩子(右左失衡)
            c = y; t3 = y.getRChild();
            b = x; t1 = x.getLChild(); t2 = x.getRChild();
        }
    }
    //摘下三个节点
    z.sever();
    y.sever();
    x.sever();
    //摘下四棵子树
    if (t0!=null) t0.sever();
    if (t1!=null) t1.sever();
    if (t2!=null) t2.sever();
    if (t3!=null) t3.sever();
    //重新链接
    a.setLChild(t0); a.setRChild(t1);
    c.setLChild(t2); c.setRChild(t3);
    b.setLChild(a); b.setRChild(c);
    //子树重新接入原树
    if (p!=null)
        if (isLeft) p.setLChild(b);
        else p.setRChild(b);
    return b;//返回新的子树根
}
//返回结点v 较高的子树
private BinTreeNode higherSubT(BinTreeNode v){
    if (v==null) return null;
    int lH = (v.hasLChild()) ? v.getLChild().getHeight():-1;
    int rH = (v.hasRChild()) ? v.getRChild().getHeight():-1;
    if (lH>rH) return v.getLChild();
    if (lH<rH) return v.getRChild();
    if (v.isLChild()) return v.getLChild();
    else return v.getRChild();
}

输入:待插元素ele
输出:在AVL 树中插入ele
代码:

public void insert(Object ele){
    super.insert(ele);
    root = reBalance(startBN);
}
//从v 开始重新平衡AVL 树
private BinTreeNode reBalance(BinTreeNode v){
    if (v==null) return root;
    BinTreeNode c = v;
    while (v!=null) { //从v 开始,向上逐一检查z 的祖先
        if (!isBalance(v)) v = rotate(v); //若v 失衡,则旋转使之重新平衡
        c = v;
        v = v.getParent(); //继续检查其父亲
    }//while
    return c;
}
//判断一个结点是否失衡
private boolean isBalance(BinTreeNode v){
    if (v==null) return true;
    int lH = (v.hasLChild()) ? v.getLChild().getHeight():-1;
    int rH = (v.hasRChild()) ? v.getRChild().getHeight():-1;
    return (Math.abs(lH - rH)<=1);
}

输入:待删元素ele
输出:在AVL 树中删除ele
代码:

public Object remove(Object ele){
    Object obj = super.remove(ele);
    root = reBalance(startBN);
    return obj;
}

© 著作权归作者所有

C
粉丝 0
博文 128
码字总数 44892
作品 0
南京
私信 提问
一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb
2018/05/08
0
0
数据结构知识学习与面试 一点课堂(多岸学院)

Queue 什么是队列 队列是数据结构中比较重要的一种类型,它支持 FIFO,尾部添加、头部删除(先进队列的元素先出队列),跟我们生活中的排队类似。 队列的种类 单队列(单队列就是常见的队列,...

程伟鑫
09/11
22
0
如何理解并掌握 Java 数据结构

一说起“数据结构”可能很多同学都又交给老师了。但是实际工作中如果做得深入一些,特别是越往上发展,越大公司越离不开数据结构。本场 Chat 作者将带领大家重温《Java 数据结构》,讲解的内...

valada
2018/04/12
0
0
二叉树算法笔记:二叉排序树(二叉搜索树) in java

本内容仅贴出三链二叉树的操作(在二叉树的两篇文章里已经有了如下代码,完全相同,只是这里把二叉排序树的代码提取出来而已)。 二叉树算法笔记:二叉树基础操作(三链二叉树) in java http:...

CheN_exe
2014/01/26
1K
0
1-玩转数据结构-欢迎学习数据结构

欢迎大家学习新课程: 玩转数据结构 为什么要学习数据结构? 数据结构是所有计算机专业的同学必学的课程 数据结构研究的是数据如何在计算机中进行组织和存储,使得我们可以高效的获取数据或者...

天涯明月笙
2018/08/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

从零基础到拿到网易Java实习offer,我做对了哪些事

作为一个非科班小白,我在读研期间基本是自学Java,从一开始几乎零基础,只有一点点数据结构和Java方面的基础,到最终获得网易游戏的Java实习offer,我大概用了半年左右的时间。本文将会讲到...

Java技术江湖
昨天
5
0
程序性能checklist

程序性能checklist

Moks角木
昨天
7
0
VUE 计算属性

本文转载于:专业的前端网站▶VUE 计算属性 1、示例代码 <!DOCTYPE html><html lang="zh"> <head> <meta charset="UTF-8" /> <title>vue示例</title> </hea......

前端老手
昨天
6
0
快速搭建LNMT平台和环境部署 Tomcat详解

Tomcat部署的基本概念 1. CATALINA_HOME与CATALINA_BASE分别指什么?     CATALINA_HOME指的是Tomcat的安装目录     bin:\\Tomcat一些脚本存放目录,比如启动脚本startup.bat/start...

网络小虾米
昨天
7
0
float浮动

float浮动 float浮动概念及原理: 文档流:文档流是文档中可显示对象在排列时所占用的位置。 加浮动的元素,会脱离文档流,会沿父容器靠左或靠右排列,如果之前已经有浮动的元素,会挨着浮动...

studywin
昨天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部