class RBTree>{
private static final String RedColor = "red";
private static final String BlackColor = "black";
//定义一个根结点
RBNode root;
//定义结点数量
private int size = 0;
//返回总结点数量
public int getSize(){
return this.size;
}
//根据key查找对应的结点
public RBNode findData(int key){
RBNode p;
p = root;
while(p != null){
if (key > p.getKey()){
p = p.getRight();
}
else if (key < p.getKey()){
p = p.getLeft();
}
else{
return p;
}
}
return null;
}
//查询每个结点的颜色
public void findColor(RBNode node){
if (node != null) {
System.out.println("for test ==>> " + " key => " + node.getKey() + ", color => " + node.getColor() + ", data => " + node.getData() + ", left => " + node.getLeft() + ", right => " + node.getRight() + ", parent => " + node.getParent());
findColor(node.getLeft());
findColor(node.getRight());
}
}
//返回根结点
public RBNode findRoot(){
return root;
}
//查找后继结点
public RBNode findAfterNode(RBNode node){
if (node.getRight() != null) {
RBNode trbNode = node.getRight();
while (trbNode.getLeft() != null) {
trbNode = trbNode.getLeft();
}
return trbNode;
}
return null;
}
//查找前驱结点
public RBNode findBeforeNode(RBNode node){
if (node.getLeft() != null) {
RBNode trbNode = node.getLeft();
while (trbNode.getRight() != null) {
trbNode = trbNode.getRight();
}
return trbNode;
}
return null;
}
//插入数据
public T putData(int key, T data){
size ++;
RBNode node;
node = root;
//如果根结点为空，则直接新建一个结点为根结点
if (node == null){
node = new RBNode(key, data, BlackColor, null, null, null);
root = node;
return node.getData();
}
else{
RBNode p = node;
//查找插入新结点的位置
while(node != null) {
p = node;
if (key < node.getKey()) {
node = node.getLeft();
}
else if (key > node.getKey()){
node = node.getRight();
}
else{
//插入结点的key已存在，原有的红黑树已经是平衡的，则直接更新结点的data
node.setData(data);
return node.getData();
}
}
//插入新结点，新插入的结点为红色
RBNode e = new RBNode(key, data, RedColor, null, null, p);
if (key > p.getKey()){
p.setRight(e);
e.setParent(p);
}
else{
p.setLeft(e);
e.setParent(p);
}
if (p.getParent() == null){
//插入新结点时只有根结点
return e.getData();
}
else{
/**
* 插入新结点的父结点为黑结点，由于插入的结点是红色的；
* 当新插入结点的父结点为黑结点时，直接插入即可，并不会影响红黑树的平衡，无需做自平衡；
*/
if (e.getParent().getColor().equals(BlackColor)){
return e.getData();
}
/**
* 插入新结点的父结点为红结点，由于插入的结点也是红结点
* 如果插入的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点
*/
else {
/**
* 插入的新结点的父结点为红结点
* 并且叔叔结点存在并且为红结点(叔叔结点是插入新结点的父结点的兄弟结点)
*/
//当前结点的祖父结点的父结点
RBNode ttPParent = null;
//当前结点的父结点的兄弟结点
RBNode tPBrother = null;
//当前结点
RBNode t = e;
//当前结点的父结点
RBNode tParent = t.getParent();
//当前结点的祖父结点
RBNode tPParent = t.getParent().getParent();
if (tPParent != root){
// 保存当前结点祖父结点的父结点
ttPParent = tPParent.getParent();
}
while (t != null) {
// 新增结点的父结点不为空
if (tParent != null){
//判断新增结点的父结点的颜色，若为黑色直接退出
if(tParent.getColor().equals(BlackColor)){
break;
}
if (tPParent != null) {
if (tPParent != root){
// 保存当前结点祖父结点的父结点
ttPParent = tPParent.getParent();
}
else{
ttPParent = null;
}
if (tParent == tPParent.getLeft()) {
//当前结点的父结点的兄弟结点
tPBrother = tPParent.getRight();
}
else if(tParent == tPParent.getRight()){
//当前结点的父结点的兄弟结点
tPBrother = tPParent.getLeft();
}
else{
tPBrother = null;
}
if (tPBrother != null) {
//若当前结点的父结点和父结点的兄弟结点都为红色，则替换颜色
if ((tParent.getColor().equals(RedColor)) && (tPBrother.getColor().equals(RedColor))) {
/**
* 将当前结点的父结点置为黑色;
* 将父结点的兄弟结点置为黑色；
* 将祖父结点置为红色
*/
tParent.setColor(BlackColor);
tPBrother.setColor(BlackColor);
tPParent.setColor(RedColor);
}
if ((tParent.getColor().equals(RedColor)) && (tPBrother.getColor().equals(BlackColor))) {
/**
* 若当前结点的父结点为红色，父结点的兄弟结点为黑色
* 则以当前结点的祖父结点为旋转点，旋转二叉树
*/
if (tParent == tPParent.getLeft()) {
LeftRotationBalance(t, tParent, tPParent, ttPParent);
break;
}
else {
RightRotationBalance(t, tParent, tPParent, ttPParent);
break;
}
}
}
else{
if (tParent.getColor().equals(RedColor)) {
/**
* 若当前结点的父结点为红色，父结点的兄弟结点为空
* 则以当前结点的祖父结点为旋转点，旋转二叉树
*/
if (tParent == tPParent.getLeft()) {
LeftRotationBalance(t, tParent, tPParent, ttPParent);
break;
}
else {
RightRotationBalance(t, tParent, tPParent, ttPParent);
break;
}
}
}
t = tPParent;
if (t.getParent() != null){
tParent = t.getParent()
if (t.getParent().getParent() != null){
tPParent = t.getParent().getParent();
}
else{
tPParent = null;
}
}
else{
tParent = null;
tPParent = null;
}
}
else{
t = tParent;
tParent = null;
tPParent = null;
ttPParent = null;
}
}
else{
//若 t 为根结点，将根结点颜色置为黑色
if (t == root) {
t.setColor(BlackColor);
}
break;
}
}
return e.getData();
}
}
}
}
//删除数据
public boolean delData(int key){
size --;
RBNode delNode = findData(key);
if (delNode != null){
int flag = 0; //后继结点
RBNode node = null;
RBNode replaceNode = null;
//删除结点为红色结点，则直接使用 前驱 或 后继 结点替换删除结点
replaceNode = findAfterNode(delNode);
//后继结点，若后继结点查询不到则查找前驱结点
if (replaceNode == null){
flag = 1; //前驱结点
replaceNode = findBeforeNode(delNode);
}
/**
* delNode 删除结点
* replaceNode 替换结点
* delBrother 替换结点的兄弟结点
* delParent 替换结点的父结点
* delPParent 替换结点的祖父结点
* delBrotherLeft 替换结点的兄弟结点的左子结点
* delBrotherRight 替换结点的兄弟结点的右子结点
*/
while (replaceNode != null){
node = null;
//后继结点，循环查找到整颗二叉树的最后后继结点
if(flag == 0){
if (replaceNode.getRight() != null) {
//查找替换结点的后继结点
node = findAfterNode(replaceNode.getRight());
if (node != null) {
delNode.setKey(replaceNode.getKey());
delNode.setData(replaceNode.getData());
delNode = replaceNode;
replaceNode = node;
continue;
}
else{
break;
}
}
else{
break;
}
}
//前驱结点，循环查找到整颗二叉树的最后前驱结点
if (flag == 1){
if (replaceNode.getLeft() != null) {
//查找替换结点的右子结点的 前驱 或 后继 结点
node = findBeforeNode(replaceNode.getLeft());
if (node != null) {
delNode.setKey(replaceNode.getKey());
delNode.setData(replaceNode.getData());
delNode = replaceNode;
replaceNode = node;
continue;
}
else{
break;
}
}
else{
break;
}
}
}
//前驱结点、后继结点都为空，则删除结点跟替换结点相同
if (replaceNode == null){
replaceNode = delNode;
}
else{
//将替换结点的数据赋给删除结点
delNode.setData(replaceNode.getData());
delNode.setKey(replaceNode.getKey());
}
/**
* 当替换结点的颜色为红色，则直接删除替换结点，不影响平衡
* 当替换结点的颜色为红色，替换结点肯定是叶子结点，根结点不可能为红色
* 也不存在红红结点、红黑结点
* 如果替换结点有两个子结点，那肯定不是最终的后继结点或前驱结点，代码走不到这里
* 此种情况下，直接删除替换结点就好，不影响平衡
*/
if (replaceNode.getColor().equals(BlackColor)){
if (replaceNode == replaceNode.getParent().getLeft()){
if (replaceNode.getRight() != null) {
/**
* 替换结点有右子结点时：
* 若替换结点为黑色，替换结点的右子结点不可能为黑色
* 直接将替换结点的右子结点设置为替换结点，将结点置黑，并将替换结点删除即可
*/
replaceNode.getRight().setColor(replaceNode.getColor());
replaceNode.getRight().setParent(replaceNode.getParent());
replaceNode.getParent().setLeft(replaceNode.getRight());
return true;
}
}
if (replaceNode == replaceNode.getParent().getRight()){
if (replaceNode.getLeft() != null){
/**
* 替换结点有右子结点时：
* 若替换结点为黑色，替换结点的右子结点不可能为黑色
* 直接将替换结点的右子结点设置为替换结点，将结点置黑，并将替换结点删除即可
*/
replaceNode.getLeft().setColor(replaceNode.getColor());
replaceNode.getLeft().setParent(replaceNode.getParent());
replaceNode.getParent().setRight(replaceNode.getLeft());
return true;
}
}
if (replaceNode == root){
root = null;
return true;
}
else {
//替换结点没有子结点，且为黑色
boolean rbNode = delBrotherBlack(replaceNode);
if (rbNode == true){
//删除后继结点
if (replaceNode == replaceNode.getParent().getLeft()){
replaceNode.getParent().setLeft(null);
}
if (replaceNode == replaceNode.getParent().getRight()){
replaceNode.getParent().setRight(null);
}
replaceNode.setLeft(null);
replaceNode.setRight(null);
replaceNode.setParent(null);
return true;
}
}
}
}
return false;
}
//替换结点是黑色时逻辑处理
public boolean delBrotherBlack(RBNode delNode){
/**
* 若替换结点的颜色为黑色，则分以下情况：
* 1：替换结点是其父结点的左子结点：
* 1.1：替换结点的兄弟结点是红结点；
* 1.2：替换结点的兄弟结点是黑结点；
* 1.2.1：替换结点的兄弟结点的右子结点是红结点，左子结点任意颜色；
* 1.2.2：替换结点的兄弟结点的右子结点是黑结点，左子结点是红结点；
* 1.2.3：父亲结点为红色，替换结点与兄弟结点都为黑色，兄弟结点的子结点都为黑结点；
* 1.2.4：父亲结点为黑色，替换结点与兄弟结点都为黑色，兄弟结点的子结点都为黑结点；
*====================================================================
* 2：替换结点时其父结点的右子结点；
* 2.1：替换结点的兄弟结点时红结点；
* 2.2：替换结点的兄弟结点时黑结点；
* 2.2.1：替换结点的兄弟结点的左子结点是红结点，右子结点任意颜色；
* 2.2.2：替换结点的兄弟结点的左子结点是黑结点，右子结点为红结点；
* 2.2.3：父亲结点为红色，替换结点与兄弟结点都为黑色，兄弟结点的子结点都为黑结点；
* 2.2.4：父亲结点为黑色，替换结点与兄弟结点都为黑色，兄弟结点的子结点都为黑结点；
*/
RBNode delBrotherLeft = null;
RBNode delBrotherRight = null;
RBNode delParent = null;
RBNode delBrother = null;
RBNode delPParent = null;
if (delNode.getParent() != null){
delParent = delNode.getParent();
if (delParent.getParent() != null){
delPParent = delParent.getParent();
}
}
//1. 替换结点是其父结点的左子结点
if (delNode == delParent.getLeft()) {
if (delParent.getRight() != null) {
delBrother = delParent.getRight(); //保存替换结点的兄弟结点
if (delBrother.getLeft() != null){
delBrotherLeft = delBrother.getLeft();
}
if (delBrother.getRight() != null){
delBrotherRight = delBrother.getRight();
}
}
// 1.1 替换结点的兄弟结点是红结点
if (delBrother.getColor().equals(RedColor)){
delBrother.setColor(BlackColor);
delParent.setColor(RedColor);
delLeftRotation(delNode, delParent, delBrother, delPParent);
boolean rbNode1 = delBrotherBlack(delNode);
if (rbNode1 == true){
return true;
}
}
// 1.2 替换结点的兄弟结点是黑结点
else{
//1.2.1：替换结点的兄弟结点的右子结点是红结点，左子结点任意颜色；
if (delBrotherRight.getColor().equals(RedColor)){
delBrother.setColor(delParent.getColor());
delParent.setColor(BlackColor);
delBrotherRight.setColor(BlackColor);
delLeftRotation(delNode, delParent, delBrother, delPParent);
return true;
}
//1.2.2：替换结点的兄弟结点的右子结点是黑结点，左子结点为红结点；
if (delBrotherRight.getColor().equals(BlackColor)){
if (delBrotherLeft.getColor().equals(RedColor)){
//先将兄弟结点的左子结点右旋
delBrotherLeft.setParent(delParent);
delParent.setRight(delBrotherLeft);
delBrother.setParent(delBrotherLeft);
delBrotherLeft.setRight(delBrother);
delBrother.setLeft(null);
//交换兄弟结点与兄弟左子结点的颜色
delBrother.setColor(RedColor);
delBrotherLeft.setColor(BlackColor);
boolean rbNode2 = delBrotherBlack(delNode);
if (rbNode2 == true){
return true;
}
}
}
//1.2.3：父亲结点为红色，替换结点与兄弟结点都为黑色，兄弟结点的子结点都为黑结点；
if (delParent.getColor().equals(RedColor)) {
if ((delBrotherLeft.getColor().equals(BlackColor)) && (delBrotherRight.getColor().equals(BlackColor))) {
delParent.setColor(BlackColor);
delBrother.setColor(RedColor);
return true;
}
}
//1.2.4：父亲结点为黑色，替换结点与兄弟结点都为黑色，兄弟结点的子结点都为黑结点；
if (delParent.getColor().equals(BlackColor)){
if ((delBrotherLeft.getColor().equals(BlackColor)) && (delBrotherRight.getColor().equals(BlackColor))) {
delBrother.setColor(RedColor);
delNode = delParent;
if (delNode == null){
return false;
}
boolean rbNode3 = delBrotherBlack(delNode);
if (rbNode3 == true){
return true;
}
}
}
}
}
//替换结点是其父结点的右子结点
else{
if (delParent.getLeft() != null) {
delBrother = delParent.getLeft(); //保存替换结点的兄弟结点
if (delBrother.getLeft() != null) {
delBrotherLeft = delBrother.getLeft();
}
if (delBrother.getRight() != null) {
delBrotherRight = delBrother.getRight();
}
}
// 2.1 替换结点的兄弟结点是红结点
if (delBrother.getColor().equals(RedColor)){
delBrother.setColor(BlackColor);
delParent.setColor(RedColor);
delRightRotation(delNode, delParent, delBrother, delPParent);
boolean rbNode1 = delBrotherBlack(delNode);
if (rbNode1 == true){
return true;
}
}
// 2.2 替换结点的兄弟结点是黑结点
else{
//2.2.1：替换结点的兄弟结点的左子结点是红结点，右子结点任意颜色；
if (delBrotherLeft.getColor().equals(RedColor)){
delBrother.setColor(delParent.getColor());
delParent.setColor(BlackColor);
delBrotherLeft.setColor(BlackColor);
delRightRotation(delNode, delParent, delBrother, delPParent);
return true;
}
//2.2.2：替换结点的兄弟结点的左子结点是黑结点，右子结点为红结点；
if (delBrotherLeft.getColor().equals(BlackColor)){
if (delBrotherRight.getColor().equals(RedColor)){
//先将兄弟结点的右子结点左旋
delBrotherRight.setParent(delParent);
delParent.setLeft(delBrotherRight);
delBrother.setParent(delBrotherRight);
delBrotherRight.setLeft(delBrother);
delBrother.setRight(null);
//交换兄弟结点与兄弟左子结点的颜色
delBrother.setColor(RedColor);
delBrotherRight.setColor(BlackColor);
boolean rbNode2 = delBrotherBlack(delNode);
if (rbNode2 == true){
return true;
}
}
}
//2.2.3：父亲结点为红色，替换结点与兄弟结点都为黑色，兄弟结点的子结点都为黑结点；
if (delParent.getColor().equals(RedColor)) {
if ((delBrotherRight.getColor().equals(BlackColor)) && (delBrotherLeft.getColor().equals(BlackColor))) {
delParent.setColor(BlackColor);
delBrother.setColor(RedColor);
return true;
}
}
//1.2.4：父亲结点为黑色，替换结点与兄弟结点都为黑色，兄弟结点的子结点都为黑结点；
if (delParent.getColor().equals(BlackColor)){
if ((delBrotherLeft.getColor().equals(BlackColor)) && (delBrotherRight.getColor().equals(BlackColor))) {
delBrother.setColor(RedColor);
delNode = delParent;
if (delNode == null){
return false;
}
boolean rbNode3 = delBrotherBlack(delNode);
if (rbNode3 == true){
return true;
}
}
}
}
}
return false;
}
//删除结点左旋
public void delLeftRotation(RBNode delNode, RBNode delParent, RBNode delBrother, RBNode delPParent){
if (delBrother.getLeft() != null){
delBrother.getLeft().setParent(delParent);
delParent.setRight(delBrother.getLeft());
}
else{
delParent.setRight(null);
}
delParent.setParent(delBrother);
delPParent.setRight(delBrother);
delBrother.setParent(delPParent);
delBrother.setLeft(delParent);
}
//删除结点右旋
public void delRightRotation(RBNode delNode, RBNode delParent, RBNode delBrother, RBNode delPParent){
if (delBrother.getRight() != null){
delBrother.getRight().setParent(delParent);
delParent.setLeft(delBrother.getRight());
}
else{
delParent.setLeft(null);
}
delParent.setParent(delBrother);
delPParent.setLeft(delBrother);
delBrother.setParent(delPParent);
delBrother.setRight(delParent);
}
//插入结点右旋
public void LeftRotationBalance(RBNode t, RBNode tParent, RBNode tPParent, RBNode ttPParent){
//若新增结点为父结点的右子结点时
if (t == tParent.getRight()){
//先将新增结点的父结点左旋
if (t.getLeft() != null){
t.setParent(tParent);
tParent.setRight(t.getLeft());
}
else{
tParent.setRight(null);
}
t.setParent(tPParent);
tPParent.setLeft(t);
tParent.setParent(t);
tParent.setRight(null);
t.setLeft(tParent);
tParent = t;
}
//将新增结点的父结点的颜色置为黑色
if (tParent.getColor().equals(RedColor)){
tParent.setColor(BlackColor);
}
//将新增结点的祖父结点颜色置为红色
if (tPParent.getColor().equals(BlackColor)){
tPParent.setColor(RedColor);
}
//以新增结点的父结点为旋转点，右旋结点
if (tParent.getRight() != null){
tParent.getRight().setParent(tPParent);
tPParent.setLeft(tParent.getRight());
}
else{
tPParent.setLeft(null);
}
tParent.setRight(tPParent);
tPParent.setParent(tParent);
tParent.setParent(ttPParent);
if (tPParent == root){
root = tParent;
}
else{
if (tPParent == ttPParent.getLeft()){
ttPParent.setLeft(tParent);
}
if (tPParent == ttPParent.getRight()){
ttPParent.setRight(tParent);
}
}
}
//插入结点左旋
public void RightRotationBalance(RBNode t, RBNode tParent, RBNode tPParent, RBNode ttPParent){
if (t == tParent.getLeft()){
//先将新增结点的父结点右旋
if (t.getRight() != null){
t.getRight().setParent(tParent);
tParent.setLeft(t.getRight());
}
else{
tParent.setLeft(null);
}
t.setParent(tPParent);
tPParent.setRight(t);
t.setRight(tParent);
tParent.setParent(t);
tParent.setLeft(null);
tParent = t;
}
//将新增结点的父结点的颜色置为黑色
if (tParent.getColor().equals(RedColor)){
tParent.setColor(BlackColor);
}
//将新增结点的祖父结点的颜色置为红色
if (tPParent.getColor().equals(BlackColor)){
tPParent.setColor(RedColor);
}
//以新增结点的父结点为旋转点，左旋结点
if (tParent.getLeft() != null){
tParent.getLeft().setParent(tPParent);
tPParent.setRight(tParent.getLeft());
}
else{
tPParent.setRight(null);
}
tParent.setLeft(tPParent);
tPParent.setParent(tParent);
tParent.setParent(ttPParent);
if (tPParent == root){
root = tParent;
}
else{
if (tPParent == ttPParent.getLeft()){
ttPParent.setLeft(tParent);
}
if (tPParent == ttPParent.getRight()){
ttPParent.setRight(tParent);
}
}
}
}
//定义一个红黑树结点
class RBNode>{
//结点key
private int key;
//结点数据
private T data;
//结点颜色
private String color;
//结点左指针
private RBNode left;
//结点右指针
private RBNode right;
//结点父结点
private RBNode parent;
public RBNode(int key, T data, String color, RBNode left, RBNode right, RBNode parent){
this.key = key;
this.data = data;
this.color = color;
this.left = left;
this.right = right;
this.parent = parent;
}
public T getData(){
return this.data;
}
public int getKey(){
return this.key;
}
public String getColor(){
return this.color;
}
public RBNode getLeft(){
return this.left;
}
public RBNode getRight(){
return this.right;
}
public RBNode getParent(){
return this.parent;
}
public void setData(T data){
this.data = data;
}
public void setLeft(RBNode left){
this.left = left;
}
public void setRight(RBNode right){
this.right = right;
}
public void setParent(RBNode parent){
this.parent = parent;
}
public void setColor(String color){
this.color = color;
}
public void setKey(int key){
this.key = key;
}
}
如果觉得《红黑树java源代码分析_JAVA 红黑树源码》对你有帮助，请点赞、收藏，并留下你的观点哦！
