6.5测试类
添加测试类1TreeOperation
package com.ccc.util.treemap;
public class TreeOperation {
/*
树的结构示例：
1
/ \
2 3
/ \ / \
4 5 6 7
*/
// 用于获得树的层数
public static int getTreeDepth(RBTree.RBNode root) {
return root == null ? 0 : (1 + Math.max(getTreeDepth(root.getLeft()), getTreeDepth(root.getRight())));
}
private static void writeArray(RBTree.RBNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
// 保证输入的树不为空
if (currNode == null) return;
// 0、默认无色
// res[rowIndex][columnIndex] = String.valueOf(currNode.getValue());
//1、颜色表示
if(currNode.isColor()){//黑色，加色后错位比较明显
res[rowIndex][columnIndex] = ("\033[30;3m" + currNode.getValue()+"\033[0m") ;
}else {
res[rowIndex][columnIndex] = ("\033[31;3m" + currNode.getValue()+"\033[0m") ;
}
//2、R,B表示
// res[rowIndex][columnIndex] = String.valueOf(currNode.getValue()+"-"+(currNode.isColor()?"B":"R")+"");
// 计算当前位于树的第几层
int currLevel = ((rowIndex + 1) / 2);
// 若到了最后一层，则返回
if (currLevel == treeDepth) return;
// 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
int gap = treeDepth - currLevel - 1;
// 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
if (currNode.getLeft() != null) {
res[rowIndex + 1][columnIndex - gap] = "/";
writeArray(currNode.getLeft(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
}
// 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
if (currNode.getRight() != null) {
res[rowIndex + 1][columnIndex + gap] = "\\";
writeArray(currNode.getRight(), rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
}
}
public static void show(RBTree.RBNode root) {
if (root == null) System.out.println("EMPTY!");
// 得到树的深度
int treeDepth = getTreeDepth(root);
// 最后一行的宽度为2的（n - 1）次方乘3，再加1
// 作为整个二维数组的宽度
int arrayHeight = treeDepth * 2 - 1;
int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
// 用一个字符串数组来存储每个位置应显示的元素
String[][] res = new String[arrayHeight][arrayWidth];
// 对数组进行初始化，默认为一个空格
for (int i = 0; i < arrayHeight; i ++) {
for (int j = 0; j < arrayWidth; j ++) {
res[i][j] = " ";
}
}
// 从根节点开始，递归处理整个树
// res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
writeArray(root, 0, arrayWidth/2, res, treeDepth);
// 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
for (String[] line: res) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < line.length; i ++) {
sb.append(line[i]);
if (line[i].length() > 1 && i <= line.length - 1) {
i += line[i].length() > 4 ? 2: line[i].length() - 1;
}
}
System.out.println(sb.toString());
}
}
}
2添加测试类2RBTreeTest
package com.ccc.util.treemap;
import java.util.Scanner;
public class RBTreeTest {
public static void main(String[] args) {
//新增节点
// insertOpt();
//删除节点
deleteOpt();
}
/**
* 插入操作
*/
public static void insertOpt(){
Scanner scanner=new Scanner(System.in);
RBTree<String,Object> rbt=new RBTree<>();
while (true){
System.out.println("请输入你要插入的节点:");
String key=scanner.next();
System.out.println();
//这里代码最多支持3位数，3位以上的话红黑树显示太错位了，这里就不重构代码了,大家可自行重构
if(key.length()==1){
key="00"+key;
}else if(key.length()==2){
key="0"+key;
}
rbt.put(key,null);
TreeOperation.show(rbt.getRoot());
}
}
/**
* 删除操作
*/
public static void deleteOpt(){
RBTree<String,Object> rbt=new RBTree<>();
//测试1：预先造10个节点（1-10）
String keyA=null;
for (int i = 1; i <11 ; i++) {
if((i+"").length()==1){
keyA="00"+i;
}else if((i+"").length()==2){
keyA="0"+i;
}
rbt.put(keyA,null);
}
//测试2：包含2位数和3位数的测试代码 1 2 3 4 5 66 77 88 99 100 101
rbt.put("001",null);
rbt.put("002",null);
rbt.put("003",null);
rbt.put("004",null);
rbt.put("005",null);
rbt.put("066",null);
rbt.put("077",null);
rbt.put("088",null);
rbt.put("099",null);
rbt.put("100",null);
rbt.put("101",null);
TreeOperation.show(rbt.getRoot());
//以下开始删除
Scanner scanner=new Scanner(System.in);
while (true){
System.out.println("请输入你要删除的节点:");
String key=scanner.next();
System.out.println();
//这里代码最多支持3位数，3位以上的话红黑树显示太错位了，这里就不重构代码了,大家可自行重构
if(key.length()==1){
key="00"+key;
}else if(key.length()==2){
key="0"+key;
}
//1 2 3 88 66 77 100 5 4 101
rbt.remove(key);
TreeOperation.show(rbt.getRoot());
}
}
}
3, RBTree
package com.ccc.util.treemap;
public class RBTree<K extends Comparable<K>, V> {
//红色用false来表示
private static final boolean RED = false;
private static final boolean BLACK = true;
//红黑树的root节点
private RBNode root;
public RBNode getRoot() {
return root;
}
public void setRoot(RBNode root) {
this.root = root;
}
/**
* 实现左旋
* p pr
* /\ /\
* pl pr ==> p rr
* /\ /\
* rl rr pl rl
* 左旋操作:
* 不用变的: p-pl , pr-rr
* 需要调整: 1. pr-rl 调整为 p-rl ,
* 将rl调整为p的右子节点
* 将p调整为rl的父节点
* 2.判断p是否有父节点
* 有: 把pr.parent = p.parent
* p为p.parent的子节点, 到底是 左还是右呢
* if p.parent.left == p
* p.parent.left = pr
* else
* p.parent.right = pr
* 没有: 直接把pr设置成root节点
* 3.最后 把p 和 pr交换
* p.parent = pr; pr.left = p
*
* @param p, 需要旋转的节点
*/
//左旋方法
private void leftRotate(RBNode p){
if ( p != null ){
//获取到pr节点
RBNode pr = p.right;
//获取到pr的左子节点 rl
p.right =pr.left;
// pr = rl;
if ( pr.left != null ) {
//将rl调整为p的右子节点
// p.right = rl;
//将p调整为rl的父节点
pr.left.parent = p;
}
//2,判断p是否有父节点
pr.parent = p.parent; //不管p是否有父节点, 都设置为pr的父节点
if ( p.parent == null ){
//如果p.parent 为空, 说明p为root节点, 把root改为pr
root = pr ;
//如果p是p.parent的左子节点, 就变更为p.parent.left = pr
}else if ( p.parent.left == p ){
p.parent.left = pr;
}else {//如果p是p.parent的右子节点, 就变更为p.parent.right = pr
p.parent.right = pr;
}
//3 最后 把p父节点设置为pr, pr的左子节点设置为p
pr.left = p;
p.parent = pr;
}
}
/**
* 右旋实现
* p pl
* /\ /\
* pl pr ==> ll p
* /\ /\
* ll lr lr pr
* 不变的 p-pr , pl-lr, 两个2节点的右字节点不变
* 步骤1: p-pl 变成 p-lr
* 步骤2: 判断p是否有父节点 , pl-lr 变成 pr-p
* 步骤3: p-pl 变成 pl-p
* @param p
*/
//右旋方法
private void rightRotate(RBNode p){
if (p != null) {
RBNode pl = p.left;
p.left = pl.right;
//步骤1: p-pl 变成 p-lr , lr的父节点 = p
if (pl.right != null) {
// p.left = lr;
pl.right.parent = p;
}
//步骤2: 判断p是否有父节点,
pl.parent = p.parent ;
if (p.parent == null) {
root = pl;
}else if ( p.parent.left == p ){
p.parent.left = pl;
}else {
p.parent.right = pl;
}
//步骤3: p-pl 变成 pl-p
pl.right = p;
p.parent = pl;
}
}
//插入操作
public void put(K key,V value){
//1, 找到插入的父节点
RBNode t = root;
if ( t == null ){ //这种情况说明是第一次插入
root = new RBNode(null,key,value==null?key:value);
return;
}
//记录比较情况
int cmp;
RBNode parent;
if (key == null){
System.out.println("put 命令里 key 为空了");
throw new NullPointerException();
}
do {
parent = t;
//比较当前根节点与传入的key大小来决定从哪边开始查找
cmp = key.compareTo((K) t.key);
if ( cmp > 0){ //从右侧查找
t = t.right ;
}else if ( cmp < 0 ){//从左侧查找
t = t.left ;
}else {// cmp =0 说明key相等了
//如果value为空就设置为key
t.setValue( value == null ? key:value);
return;
}
}while (t != null);
//2, 将新节点添加到父节点的子节点中
// a 创建要插入的节点
RBNode node = new RBNode(parent, key, value == null ? key : value);
if ( cmp > 0 ){
//如果比父节点大, 就放到右边
parent.right = node;
}else {
parent.left = node;
}
//旋转和变色 调整红黑树的平衡
fixAfterPut(node);
}
//获取父节点
private RBNode getParent(RBNode node){
return node != null ? node.parent : null;
}
//获取爷节点
private RBNode getGrandfather(RBNode node){
return node != null ? node.parent.parent : null;
}
//获取左节点
private RBNode getLeft(RBNode node){
return node != null ? node.left : null;
}
//获取右节点
private RBNode getRight(RBNode node){
return node != null ? node.right : null;
}
//获取父节点
private boolean getColor(RBNode node){
//如果传过来的节点是空的, 就返回黑色, ----------------Treemap里删除的时候会用到这个表达式
return node == null ? BLACK : node.color;
}
//设置颜色
private void setColor(RBNode node, boolean color){
if (node != null) {
node.color = color;
}
}
/**
* 插入放点后的调整操作
* 2-3-4对应的操作
* 2书点: 新插入一个元素直接2节点合并不用调整
* 红黑树:新增一个红色 放点在黑色节点下不需要调整
* 3节点: 新插入一个元素在3节点下, 那么会出现6中情况(2两种不需要调整，4种需要调整)
* 红黑树: 插入的节点是 插入在上黑下红的结构中，插入在红色节点
* 4节点:新插入一个元素在4节点下，那么会出现4中情况都需要调整
* 红黑树:新增的节点是红色, 爷爷节点是黑色，父亲节点和叔叔节点是红色
* @param x
*/
private void fixAfterPut(RBNode<K,Object> x){
//插入的节点 肯定是红色
x.color = RED;
//2节点不用调整, 3, 4 节点才需要调整, 把2节点过滤了
while ( x !=null && x != root && x.parent.color ==RED ){ //为空为root都不需要调整, 只有2节点的父节点是黑色,其他都是红色, 所以这里把2节点排除了
//这里分为了两种情况,
if ( getParent(x) == getLeft(getGrandfather(x)) ){ //x的父节点在x爷爷左子节点时 对应 图1 , 2 ,5, 6
//需调整的变成了4种, 有叔叔节点: 图1,2 没有叔叔节点: 图5,6
//找到右叔叔节点, 1,2找到4 , 5,6 找到null
RBNode uncleR = getRight(getGrandfather(x));
//如果右叔叔的颜色是RED, 说明不为空 : 图 1,2
if (getColor(uncleR) == RED) {
//叔叔跟父亲变为黑色, 爷爷变成红色
//但是还有一种情况是爷爷节点上面还有元素, 这下就把(下面这个整体)爷爷节点当成x ,再来一遍 如图9
//变色+ 递归
setColor(uncleR,BLACK); //把右叔叔设置成黑色
setColor( getParent(x) , BLACK ); //把父节点设置成黑色
setColor(getGrandfather(x),RED);//把爷爷设置成红色
//递归处理, 就是先保证自身平衡, 再把这部分当做新元素和上面的节点变色处理
x = getGrandfather(x);
}else {
//说明没有右叔叔节点: 图 5,6
//判断x是父节点的左子节点还是右子节点
if ( x == getRight(getParent(x))) { //是父节点的右子节点: 图6
x = getParent(x);//现在x就转移到了2 , 如图10
leftRotate(x); // 旋转之后, 下面5, 和10 可以一起处理了
}
//把父节点变为黑色, 爷爷节点变为红色, 再根据爷爷节点右旋即可
setColor(getParent(x),BLACK);//父黑
setColor(getGrandfather(x),RED);//爷红
rightRotate(getGrandfather(x));//爷右旋
}
}else {//x的父节点在x爷爷右子节点时 对应 图3,4,7,8
//需调整的变成了4种, 有叔叔节点: 图3,4 没有叔叔节点: 图7,8 , 和上面的情况左右相反
//找到左叔叔节点, 图3,4找到2 , 7,8 找到null
RBNode uncleL = getLeft(getGrandfather(x));
//如果左叔叔的颜色是RED, 说明不为空 : 图 3,4
if (getColor(uncleL) == RED) {
//叔叔跟父亲变为黑色, 爷爷变成红色
//但是还有一种情况是爷爷节点上面还有元素, 这下就把(下面这个整体)爷爷节点当成x ,再来一遍 如图9
//变色+ 递归
setColor(uncleL,BLACK); //把左叔叔设置成黑色
setColor( getParent(x) , BLACK ); //把父节点设置成黑色
setColor(getGrandfather(x),RED);//把爷爷设置成红色
//递归处理, 就是先保证自身平衡, 再把这部分当做新元素和上面的节点变色处理
x = getGrandfather(x);
}else {
//说明没有左叔叔节点: 图 7,8
//判断x是父节点的左子节点还是右子节点
if ( x == getLeft(getParent(x))) { //是父节点的右子节点: 图7
x = getParent(x);//现在x就转移到了3
rightRotate(x); // 旋转之后, 下面7, 和8 可以一起处理了
}
//把父节点变为黑色, 爷爷节点变为红色, 再根据爷爷节点右旋即可
setColor(getParent(x),BLACK);//父黑
setColor(getGrandfather(x),RED);//爷红
leftRotate(getGrandfather(x));//爷右旋
}
}
}
// root 节点肯定为黑色
setColor(root , BLACK);
}
//红黑树对象
//继承Comparable接口, 可以做比较
static class RBNode<K extends Comparable<K>,V>{
//父节点
private RBNode parent;
//左子节点
private RBNode left;
//右子节点
private RBNode right;
//颜色, 这里定义的是 黑--true 红--false
private boolean color;
private K key;
private V value;
public RBNode() {
}
public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {
this.parent = parent;
this.left = left;
this.right = right;
this.color = color;
this.key = key;
this.value = value;
}
//为了操作简化, 再添加一个parent,key,value
public RBNode(RBNode parent, K key, V value) {
this.parent = parent;
this.key = key;
this.value = value;
}
public RBNode getParent() {
return parent;
}
public void setParent(RBNode parent) {
this.parent = parent;
}
public RBNode getLeft() {
return left;
}
public void setLeft(RBNode left) {
this.left = left;
}
public RBNode getRight() {
return right;
}
public void setRight(RBNode right) {
this.right = right;
}
public boolean isColor() {
return color;
}
public void setColor(boolean color) {
this.color = color;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}
/**
* 找到前驱节点
* @param node
* @return
*/
private RBNode getPrecursor(RBNode node){
if (node == null ) {
return null;
} else if (getLeft(node) != null) {
//如果他的左节点不为空, 就循环找他的左节点的右子节点
RBNode p = getLeft(node);
while ( getRight(p) != null){
p = getRight(p);
}
return p;
}else {
//如果这个node没有左节点, 那么就向上找前驱节点
//这种情况在 红黑树 ,2-3-4树中不会出现
RBNode p = node.parent;
RBNode n1 = node;
while ( p!= null && n1 == getLeft(p)){
n1 = p;
p = getParent(p);
}
return p;
}
}
/**
* 找到后继节点
* @param node
* @return
*/
private RBNode getSuccessor(RBNode node){
if (node == null ) {
return null;
} else if (getRight(node) != null) {
//如果他的左节点不为空, 就循环找他的左节点的右子节点
RBNode p = getRight(node);
while ( getLeft(p) != null){
p = getLeft(p);
}
return p;
}else {
//如果这个node没有左节点, 那么就向上找前驱节点
//这种情况在 红黑树 ,2-3-4树中不会出现
RBNode p = node.parent;
RBNode n1 = node;
while ( p!= null && n1 == getRight(p)){
n1 = p;
p = getParent(p);
}
return p;
}
}
/**
* 删除节点
* 1, 节点删除(可以看做普通的二叉树删除)
* 2, 删除后调整
* @param key
* @return
*/
public V remove(K key){
//1. 根据需要删除的key, 找到对应的node节点
RBNode node = getNode(key);
if ( node == null ){
return null;
}
V oldValue = (V) node.value;
//具体删除节点的方法
deleteNode(node);
return oldValue;
}
/**
* 根据key找到删除的对应node
* @param key
* @return
*/
private RBNode getNode(K key) {
// if ( key == null ){
// return null;
// }
RBNode node = root;
while ( node != null ){
//int cmp1 = node.key.compareTo(key);
int cmp = key.compareTo((K) node.key);
if (cmp > 0) {
node = node.right ;
} else if (cmp < 0) {
node = node.left;
}else {
//找到了对应的节点
return node;
}
}
return null;
}
/**
* 删除节点
* 1.删除节点(普通的二叉树相同)
* a. 删除叶子节点, 直接删除
* b. 删除的节点有一个子节点, 用子节点来替代
* c. 删除的节点有两个子节点, 把这个节点赋值给前驱或后继节点, 再删除掉前去后继节点
* 将情况c转换成情况a, b
* 2.调整
* @param node
*/
private void deleteNode(RBNode node) {
//1, 先处理情况3
if (getLeft(node) != null && getRight(node) != null) {
//有两个子节点的情况
// RBNode pNode = getSuccessor(node);//找到后继或前驱节点,这里使用后继
RBNode pNode = getPrecursor(node);//前驱
//用后继节点的值, 覆盖给删除节点
node.key = pNode.key;
node.value = pNode.value;
//这时要删除的节点就变成了 后继节点, 也就变成了情况2 ,或1了
node = pNode;
}
//找到后继节点的子节点(替代节点)
RBNode replacement = node.left==null ? node.right:node.left;
//2, 再情况2, 情况2 可能是情况3 转换来的
if (replacement != null) { //如果后继节点有子节点说明是情况2
replacement.parent = node.parent;
if ( getParent(node) == null ){//说明我们删除的节点是根节点
root = replacement;
} else if (getLeft(getParent(node)) == node) { //如果是node父节点的左节点, 就换成replacement
getParent(node).left = replacement;
}else { //如果是node父节点的右节点, 就换成replacement
getParent(node).right = replacement;
}
//要删除的node节点全部设置成空 , GC
node.right = node.parent = node.right = null ;
if (getColor(node) == BLACK) { //如果删除的节点是红色, 不需要调整
//做调整操作
fixAfterRemove(replacement);
}
}else if (node.parent == null){ // node 没有父节点说明是root节点
root = null;
}else { //就是情况1
//先调整再删除
if (node.color == BLACK) {
fixAfterRemove(node);
}
if(node.parent != null){//如果他没有父节点再把指向关系去掉
if(node == node.parent.left){
node.parent.left = null;
}else{
node.parent.right = null;
}
node = null;
}
}
}
/**
* 删除节点后的调整操作
* 2-3-4数操作
* 1. 删除3,4 节点, 自己能搞定
* 2. 删除2 节点, 自己搞不定, 需要兄弟借, 兄弟借
* 父亲下来, 兄弟找一个节点替换父亲节点位置
* 3. 删除2 节点, 自己搞不定, 兄弟不借
*
* @param node
*/
private void fixAfterRemove(RBNode node) {
// 情况2 和3
//如果是root节点直接改为黑色就可以了, 替换的节点是红色就不需要调整了
while (node != root && getColor(node) == BLACK ){
//判断node是父节点的左节点还是有节点
if ( node == getLeft(getParent(node))){
//1. 找到兄弟节点
RBNode bro = getParent(node).right;
// 判断找到的是不是真的兄弟节点 ---- 2-3-4 转红黑树3节点有两种情况
if (getColor(bro) == RED) {
//如果是红色, 找到的就不是真的兄弟节点, 需要一次变色加左旋转
setColor(bro,BLACK);
setColor(getParent(node),RED);
leftRotate(getParent(node));
bro = getParent(node).right;//找到真兄弟了
}
//判断能不能借
//兄弟节点一个子节点都没有, 不借
if (getColor(getLeft(bro)) == BLACK && getColor(getRight(bro)) == BLACK) {
//2没有子节点, 不借
setColor(bro,RED);
node = getParent(node);
}else {
//2兄弟借
//如果兄弟节点的子节点是左边, 需要先变色, 右旋一次
if (getColor(getRight(bro)) == BLACK) {
//右侧子节点为空, 那就有左子节点
setColor(bro,RED);
setColor(getLeft(bro),BLACK);
rightRotate(bro);
bro = getRight(getParent(node));
}
//需要根据父节点做一次左旋操作, 变色
setColor(bro,getColor(getParent(node)));
setColor(getParent(node),BLACK);
setColor(getRight(bro),BLACK);
leftRotate(getParent(node));
node =root; //结束循环, 针对3的处理
}
}else {
//1. 找到兄弟节点
RBNode bro = getParent(node).left;
// 判断找到的是不是真的兄弟节点 ---- 2-3-4 转红黑树3节点有两种情况
if (getColor(bro) == RED) {
//如果是红色, 找到的就不是真的兄弟节点, 需要一次变色加左旋转
setColor(bro,BLACK);
setColor(getParent(node),RED);
rightRotate(getParent(node));
bro = getParent(node).left;//找到真兄弟了
}
//判断能不能借
//兄弟节点一个子节点都没有, 不借
if (getColor(getLeft(bro)) == BLACK && getColor(getRight(bro)) == BLACK) {
//2没有子节点, 不借
setColor(bro,RED);
node = getParent(node);
}else {
//2兄弟借
//如果兄弟节点的子节点是左边, 需要先变色, 右旋一次
if (getColor(getLeft(bro)) == BLACK) {
//右侧子节点为空, 那就有左子节点
setColor(bro,RED);
setColor(getRight(bro),BLACK);
leftRotate(bro);
bro = getLeft(getParent(node));
}
//需要根据父节点做一次左旋操作, 变色
setColor(bro,getColor(getParent(node)));
setColor(getParent(node),BLACK);
setColor(getLeft(bro),BLACK);
rightRotate(getParent(node));
node =root; //结束循环, 针对3的处理
}
}
}
//1. 替换的节点为红色, 只需要变色为黑色集客
setColor(node,BLACK);
}
}
put方法测试
运行结果
网站验证
Red/Black Tree Visualization (usfca.edu)
remove方法测试 (前驱)
初始状态一致
