- 浏览: 44828 次
- 性别:
- 来自: 武汉
最新评论
出去流浪了一段时间,现在我又回来了,内容继续更新,算法继续学习。
在最近看的是红黑树,而且在这里停留了很久,因为总是遇到NullPointerException的问题,每天都在对程序进行调试,今天终于搞定了。这里先插入出现NullPointerException的情形:
1字符串变量未初始化;
2接口类型的对象没有用具体的类初始化
3当一个对象的值为空时,你没有判断为空的情况。
这里简单介绍一下什么是红黑树:
红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 每个叶节点是黑色的。
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
上面就是红黑树的定义,可以看出红黑树是二叉查找树的扩充,所以其大多数的操作都和二叉查找树相识,只不过还需要考虑红黑树以上的5个基本性质,所以就会在二叉查找树的基础上进行一些改进和补充。下面就是具体代码:
/* * 红黑树的java实现 * @version 1.0 2012/4/25 * @author akon */ package com.akon405.www; public class RBTree { RBTreeNode nullNode=new RBTreeNode();//定义空节点 RBTreeNode RBTreeRoot=nullNode;//定义一个根节点 //初始化空节点nullNode public void init(){ nullNode.data=0; nullNode.color=null; nullNode.left=nullNode; nullNode.right=nullNode; nullNode.parent=nullNode; } //中序遍历红黑树操作(中序遍历之后便可以排序成功) public void inOrderRBTree(RBTreeNode x){ if(x!=nullNode){ inOrderRBTree(x.left);//先遍历左子树 System.out.print(x.data+",");//打印中间节点 inOrderRBTree(x.right);//最后遍历右子树 } } //红黑树的插入操作 public void insert(RBTree T,RBTreeNode k){ RBTreeNode x=T.RBTreeRoot; RBTreeNode y=nullNode; RBTreeNode node=new RBTreeNode(); node=k; while(x!=nullNode){//while语句可以找到k节点所要插入的位置的父亲节点y y=x; if(x.data>node.data){ x=x.left; }else{ x=x.right; } } node.parent=y; if(y==nullNode){//二叉查找树为空树的情况下,直接插入到根节点,这里的y为已知的k的父亲节点 T.RBTreeRoot=node; }else if(node.data<y.data){//插入到父亲节点y的左边 y.left=node; }else{//插入到父亲节点y的右边 y.right=node; } node.left=nullNode;//叶节点的子树须为null node.right=nullNode; node.color="red";//red代表红色(插入红色的结点,因为这样可以在插入过程中尽量避免对树的调整) insertFixup(node);//为了保证插入节点之后依然满足红黑树的性质,这里创建一个修复函数对红黑树的节点重新着色并旋转 } //插入修复函数(颜色的调整,左旋,右旋) private void insertFixup(RBTreeNode k) { RBTreeNode y=nullNode; while(k.parent.color=="red"){//插入节点k的父亲节点为红色的情况下(因为插入的节点是红色节点,所以它的父亲节点必须为黑色) if(k.parent==k.parent.parent.left){//(1)k父亲节点为其父亲节点的左孩子 y=k.parent.parent.right;//y的k的叔父节点 if(y.color=="red"){//case 1(k的叔父节点为红色) k.parent.color="black";//k的父亲节点置为黑 y.color="black"; k.parent.parent.color="red"; k=k.parent.parent; }else{//case 2(k的叔父节点为黑色) if(k==k.parent.right){//k为右孩子节点 k=k.parent; leftRotate(k); } k.parent.color="black"; k.parent.parent.color="red"; rightRotate(k); } }else{//(2)k父亲节点为其父亲节点的右孩子,操作和前面(1)k父亲节点为其父亲节点的左孩子一样 y=k.parent.parent.left; if(y.color=="red"){//case 1 k.parent.color="black"; y.color="black"; k.parent.parent.color="red"; k=k.parent.parent; }else{//case 2 if(k==k.parent.right){ k=k.parent; rightRotate(k); } k.parent.color="black"; k.parent.parent.color="red"; leftRotate(k); } } } RBTreeRoot.color="black"; } //红黑树的删除操作 public void delete(RBTreeNode x){//三种情况的节点 RBTreeNode y;//y为真实删除的节点(x不一定是真实被删除的节点) //下面的if..else便可确定节点y(y为x节点或者为x的后继节点) if(x.left==nullNode||x.right==nullNode){ y=x; }else{ y=successor(x); } //把x置为y的非空孩子节点 if(y.left!=nullNode){ x=y.left; }else{ x=y.right; } //删除y节点 x.parent=y.parent; if(y.parent==nullNode){ RBTreeRoot=x; }else if(y==y.parent.left){ y.parent.left=x; }else{ y.parent.left=x; } if(y!=x){ x.data=y.data; } if(y.color=="black"){//修复红黑树(删除节点为红色的时候不影响红黑树的性质) deleteFixup(x); } } //删除修复函数 public void deleteFixup(RBTreeNode x){ RBTreeNode y; while(x!=RBTreeRoot&&x.color=="black"){ if(x==x.parent.left){//x为其父亲节点的左孩子节点 y=x.parent.right;//x的兄弟节点y if(y.color=="red"){//x的兄弟节点y为红色 //第一种情况--x的兄弟节点y为红色 y.color="black"; y.parent.color="red"; rightRotate(x.parent); y=x.parent.right; }else{//x的兄弟节点y为黑色 if(y.left.color=="black"&&y.right.color=="black"){//第二种情况--x的兄弟节点y为黑色,y的孩子节点均为黑色 y.color="red"; x=x.parent; }else if(y.right.color=="black"&&y.left.color=="red"){//第三种情况--x的兄弟节点y为黑色,y的右孩子节点是黑色,左孩子是红色 y.left.color="red"; y.color="black"; leftRotate(x); y=x.parent.right; }else if(y.right.color=="red"){//第四种情况--x的兄弟节点y为黑色,y的右孩子节点为红色 y.color=x.parent.color; x.parent.color="black"; y.right.color="black"; leftRotate(x); x=RBTreeRoot; } } }else{//同样,原理一致,只是遇到左旋改为右旋,遇到右旋改为左旋,即可。其它代码不变。 y=x.parent.left;//x的兄弟节点 if(y.color=="red"){ y.color="black"; y.parent.color="red"; rightRotate(x.parent); y=x.parent.right; }else{ if(y.left.color=="black"&&y.right.color=="black"){ y.color="red"; x=x.parent; }else if(y.right.color=="black"&&y.left.color=="red"){ y.left.color="red"; y.color="black"; leftRotate(x); y=x.parent.right; }else if(y.right.color=="red"){ y.color=x.parent.color; x.parent.color="black"; y.right.color="black"; rightRotate(x); x=RBTreeRoot; } } } } x.color="black"; } //查找节点的后继节点 public RBTreeNode successor(RBTreeNode x){ if(x.right!=nullNode){ return searchMinNode(x.right);//右子树的最小值 } RBTreeNode y=x.parent; while(y!=nullNode&&x==y.right){//向上找到最近的一个节点,其父亲节点的左子树包涵了当前节点或者其父亲节点为空 x=y; y=y.parent; } return y; } //查找最小节点 public RBTreeNode searchMinNode(RBTreeNode x){ while(x.left!=nullNode){ x=x.left; } return x; } //从r节点开始查找x节点 public RBTreeNode search(RBTreeNode r,RBTreeNode x){ if(r==nullNode||r.data==x.data){ return r; } if(x.data<r.data){ return search(r.left,x); }else{ return search(r.right,x); } } //红黑树的左旋操作(选择的节点必须右孩子节点不为空) public void leftRotate(RBTreeNode x){ //左旋分为三个步骤,每个步骤有两个操作,因为每个节点既有孩子节点又有父亲节点 RBTreeNode y=x.right;//把x节点的右孩子节点赋给我们定义的y节点 //第一步,y的左孩子节点转变为x的右孩子节点 x.right=y.left; y.right.parent=x; //第二步,把x的父亲节点转变为y的父亲节点 y.parent=x.parent; if(x.parent==nullNode){//x为根节点的情况下 RBTreeRoot=y; }else if(x==x.parent.left){//x的父亲节点不为空并且x为其父亲节点的左孩子节点 x.parent.left=y; }else{//x的父亲节点不为空并且x为其父亲节点的右孩子节点 x.parent.right=y; } //第三步,把x节点转变为y的左孩子节点 y.left=x; x.parent=y; //左旋完成 } //红黑树的右旋操作(选择的节点必须左孩子节点不为空) public void rightRotate(RBTreeNode x){ //右旋和左旋步骤基本一样,也分为三个步骤 RBTreeNode y=x.left; //第一步,把y的右孩子节点转变为x的左孩子节点 x.left=y.right; y.left.parent=x; //第二步,把x的父亲节点转变为y的父亲节点 y.parent=x.parent; if(x.parent==nullNode){ RBTreeRoot=y; }else if(x.parent.left==x){ x.parent.left=y; }else{ x.parent.right=y; } //第三步,把x节点转变为y的左孩子节点 y.left=x; x.parent=y; //右旋完成 } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] A={20,8,16,34,73,17,32,89}; RBTree rb=new RBTree(); rb.init(); //通过循环插入构造红黑树 for(int i=0;i<A.length;i++){ RBTreeNode x=new RBTreeNode(); x.data=A[i]; x.color=null; x.left=rb.nullNode; x.right=rb.nullNode; x.parent=rb.nullNode; rb.insert(rb,x); } rb.inOrderRBTree(rb.RBTreeRoot);//中序遍历红黑树 } } //红黑树的节点类 class RBTreeNode{ int data; String color; RBTreeNode left; RBTreeNode right; RBTreeNode parent; }
结果:17,32,34,73,89,
发表评论
-
2012/5/12---求100以内的质数
2012-05-12 17:31 1361这是很久以前写的代码。代码很简洁,也很简单。 但是今天再做一 ... -
2012年5月7日---基于斐波那契数列的时间复杂度分析
2012-05-07 19:53 15641在算法中,时间复杂度 ... -
2012
2012-04-12 19:11 0/* * 红黑树的java实现 * @version ... -
2012/4/9----二叉查找树(二叉排序树)的各种操作
2012-04-09 22:43 3870不知不觉都快5天没更新 ... -
2012/4/4----随机选择法
2012-04-04 21:20 1144写算法之前先吐槽一下,今天实在是不适合骑车。昨晚花了一个小时洗 ... -
2012/4/3----桶排序
2012-04-03 12:18 1152清明假期第一天休息,今天继续来一个算法。今天写的是桶排序的算法 ... -
2012/4/1----基数排序
2012-04-01 18:03 1297基数排序的核心思想是:把待排序的数组N中的数据分解成为个位,十 ... -
2012/3/31----计数排序
2012-03-31 10:23 889计数排序的核心思想是:对需要排序的数组A,计算出A中各个元素在 ... -
2012/3/30----冒泡排序
2012-03-30 12:42 987冒泡排序的核心思想:把数组中的相邻两个数进行比较,然后把较大的 ... -
2012/3/29----快速排序
2012-03-29 11:48 923前面用到了分治算法所演变出来的一种排序---归并排序。这里,我 ... -
2012/3/28----堆排序
2012-03-28 16:45 918堆排序是一种基于二叉 ... -
2012/3/27----归并排序
2012-03-27 11:35 1152通过使用分治算法的思想来对数组进行排序(这里叫做归并排序),分 ... -
2012/3/26----插入排序
2012-03-26 21:32 1085从今天开始系统的学习算法,争取每天用java实现一个算法,然后 ... -
2012/3/26----插入排序
2012-03-26 21:32 0从今天开始系统的学习算法,争取每天用java实现一个算法,然后 ...
相关推荐
- **出版信息**:此书出版于2012年10月1日,作者刘汝佳。 - **核心知识点**: - 训练计划:如何制定有效的训练计划。 - 实战技巧:在竞赛中的实用技巧。 - 知识点梳理:帮助读者系统掌握算法知识。 - 模拟竞赛:...
那些年,与你同分同位次的同学都去了哪里?全国各大学在辽宁2020-2024年各专业最低录取分数及录取位次数据,高考志愿必备参考数据
下单系统的Spnigboot和微信小程序实现(全栈微信小程式下单)
该项目是一款基于Java的智能文件管家设计源码,涵盖102个文件,包括29个Java源文件、27个类文件、19个XML配置文件、10个YAML文件、8个列表文件、4个属性文件、4个JAR包文件以及1个Git忽略文件。该系统旨在提供高效便捷的文件管理解决方案。
基于YoloV8的简单目标检测和跟踪,使用KMNET进行鼠标移动(处理多目标移动抖动,处理鼠标平滑移动)
本项目是一款基于Vue和JavaScript开发的心旅途个性化推荐旅游平台设计源码,整合了513个Java文件、76个PNG图片、70个XML配置文件、62个JavaScript文件、42个Vue组件文件、28个CSS样式文件、22个HTML文件、18个YAML配置文件、16个属性文件、11个Vue模板文件,总计919个文件。平台采用现代化前端技术堆栈,旨在为用户提供个性化的旅游推荐服务。
AutoLine是一个基于Python的通用自动化测试开源平台,包含了657个文件,涵盖228个PNG图片、209个CSS样式、95个JavaScript脚本、39个Python源代码、21个HTML文件、19个XML文件、14个GIF图片、6个DS_Store文件、5个文本文件、4个Markdown文件。该平台的设计源码由多种编程语言编写,旨在提供灵活高效的自动化测试解决方案。
微信小程序图像裁剪工具_ e-cropper
【作品名称】:基于MATLAB的答题卡识别系统。带一个GUI可视化界面,通过输入答题卡旋转校正,边缘检测,霍夫曼变换检测答题卡填涂区域 【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【项目介绍】: 传统的阅卷方式为流水线的手工作业方式。这样的方式存在很多的问题,因为很容易受到阅卷者的主观因素的影响,从而产生一定的偏差。所以很多人就讨论如何将人为的因素降低到最低,来确保考生的考试成绩的公平公正和准确。 基于MATLAB的答题卡识别系统。带一个GUI可视化界面,通过输入答题卡旋转校正,边缘检测,霍夫曼变换检测答题卡填涂区域,分割,识别属于ABCD等,通过和实现设置好的标准答案excel对比,从而得出最终分数 【资源声明】:本资源作为“参考资料”而不是“定制需求”,代码只能作为参考,不能完全复制照搬。需要有一定的基础能够看懂代码,能够自行调试代码并解决报错,能够自行添加功能修改代码。
那些年,与你同分同位次的同学都去了哪里?全国各大学在辽宁2020-2024年各专业最低录取分数及录取位次数据,高考志愿必备参考数据
本项目深入解析并实现了基于Java核心技术的Nacos配置中心,包含2707个文件,涵盖2180个Java源文件、177个JavaScript文件、52个XML文件、35个SCSS文件、22个PEM文件、20个属性文件、18个Markdown文件、16个Protocol Buffers文件、12个JSON文件、11个字体文件。项目涉及多种语言和技术,旨在提供一个全面的配置中心解决方案。
枝晶生长Comsol仿真模型。 锂枝晶生长过程的 枝晶生长Comsol仿真模型。 锂枝晶生长过程的枝晶形貌,温度场耦合,应力场,浓度场,电势场。 C++程序,基于元胞自动机法模拟枝晶生长,能实现任意角度(偏心正方算法),同时采用LBM考虑了对流作用对枝晶生长的影响
本项目为apple_pro客户关系管理系统的组件化开发源码,采用Python、CSS、HTML和JavaScript等多种语言编写,总计包含1078个文件。其中,Python源文件254个,Python编译后文件244个,CSS样式文件65个,HTML模板61个,JavaScript脚本40个,以及其他类型文件如LESS、SCSS、XML、PNG等。该系统通过组件化设计,旨在提升客户关系管理的效率与用户体验。
微信小程序日历插件_Calendar
那些年,与你同分同位次的同学都去了哪里?全国各大学在辽宁2020-2024年各专业最低录取分数及录取位次数据,高考志愿必备参考数据
另一个小型购物中心。Litemall=Spring Boot后端+Vue管理员前端+微信小程序用户前端+Vue用户移动端_stemall
该项目为基于GitHub的ESPnet语音处理工具包设计源码,包含10633个文件,涵盖Shell脚本、Python、MATLAB、C++等多种编程语言。文件类型包括2872个shell脚本、2303个YAML配置文件、1662个Python脚本、1567个配置文件、306个Markdown文件、223个Perl脚本、39个文本文件、35个Bash脚本、27个PNG图片、21个补丁文件。该项目定期更新,适用于语音处理领域的研究与开发。
该项目是一款基于Python开发的pyecharts可视化图表库源码,包含166个文件,涵盖了121个Python源文件、12个HTML文件、9个JSON文件、6个PNG图片文件、4个Markdown文件、3个文本文件、2个YAML文件以及少量配置和管理文件。该库旨在提供强大的数据可视化解决方案,适用于各种数据分析与展示需求。
STM32软件学习资料GPS与GPRSSTM32软件学习资料GPS与GPRS
那些年,与你同分同位次的同学都去了哪里?全国各大学在辽宁2020-2024年各专业最低录取分数及录取位次数据,高考志愿必备参考数据