1. 红黑树性质
平衡二叉树的一种
- 节点是红色或黑色。
- 根节点是黑色。
- 每个叶节点（这里的叶节点是指NULL节点，在《算法导论》中这个节点叫哨兵节点，除了颜色属性外，其他属性值都为任意。为了和以前的叶子节点做区分，原来的叶子节点还叫叶子节点，这个节点就叫他NULL节点吧）是黑色的。
- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点，或者理解为红节点不能有红孩子)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（黑节点的数目称为黑高black-height）。
2. 节点添加
2.1 二叉搜索树插入
//插入一个新值public void insert(int key,int value) {Node in = new Node(R,key,value);root = insert(null,root,in);insertFixUp(in);}//插入 核心代码private Node insert(Node parent,Node root,Node in) {if(root == null) {in.Parent = parent;return in;}if(in.key>root.key) { //如果key大于root.keyroot.Right = insert(root,root.Right,in);}else{root.Left = insert(root,root.Left,in);}return root;}
2.2 修正函数
//修正函数public void insertFixUp(Node node) {Node gparent,parent;parent = node.Parent;//如果父节点存在 并且为红色while(node.Parent != null && node.Parent.color == R) { //因为父亲为红色 则不可能为根节点，则必须有父亲节点gparent = parent.Parent;if(gparent.Left == parent){ //如果爷爷节点存在，父节点是爷爷的左孩子Node uncle = gparent.Right;if(uncle != null && uncle.color == R) { //如果叔叔节点存在 并且为红色/** 1.将叔叔和父亲设为黑色* 2.将爷爷变为红色* 3.node = 爷爷；* 4.结束*/gparent.color = R;uncle.color = B;parent.color = B;node = gparent;continue;}if(parent.Right == node) { //如果叔叔节点不存在 或者存在并且为黑色，node为父亲的右孩子/** 1.左旋（父）* 2.父节点等于node* 3.node = 原父节点* (下面步骤正是node为父亲左孩子要做的事)* 4.将父节点变为黑色* 5.爷爷变为红色* 6.右旋（爷）*/leftRotate(parent);//以上操作是为了和左孩子相匹配做条件Node tmp = parent;node = tmp;parent = node;// 结束parent.color = B;gparent.color = R;rightRotate(gparent);}else { //叔叔节点不存在，或者叔叔存在并且为黑色，node为父亲的左孩子parent.color = B;gparent.color = R;rightRotate(gparent);}}else { //如果父亲节点为爷爷的右孩子时候Node uncle = gparent.Left;if(uncle != null && uncle.color == R) { //如果叔叔节点存在，并且为红色/** 1.将叔叔和父亲设为黑色* 2.将爷爷变为红色* 3.node = 爷爷；* 4.结束*/gparent.color = R;uncle.color = B;parent.color = B;node = gparent;continue;}if(parent.Left == node) { // 如果叔叔节点不存在，如果叔叔节点存在并且为黑色，node在parent的左边时候/** 1.右旋(父亲)* 2.父节点等于node* 3.node等于父节点** 4.爷爷变为红色* 5.父亲变为黑色* 6.左旋（爷爷）*/rightRotate(parent);Node tmp = parent;parent = node;node = tmp;gparent.color = R;parent.color = B;leftRotate(gparent);}else {gparent.color = R;parent.color = B;leftRotate(gparent);}}}//如果父亲节点为黑色（有可能是root）//while循环中 叔叔也是红色 爷爷是root 则爷爷变为红色了this.root.color = B;}
3. 节点删除
3.1 获取需要删除的节点
//获取需要删除的节点
public Node getRemoveNode(Node root,int key) {
if(key == root.key || root == null) {
if(root.Right != null && root.Left != null) { // 左右孩子都不为空
//获得右孩子的最小值
Node min = minimum(root.Right);
//改变root的值 不改变root的值
root.key = min.key;
root.values = min.values;
return min;
}
return root;
}else if(key>root.key) {
return getRemoveNode(root.Right,key);
}else {
return getRemoveNode(root.Left,key);
}
}
3.2 修正红黑树
private void removeFixUp(Node node) {
Node del = node;
// 当node 不是root时候 则node必有父亲节点 修正函数
while(node != root) {
Node parent = node.Parent;
Node uncle;
//删除的节点为红色时候 则无须任何操作
if(node.color == R || node == null) {
break;
}
//当删除的节点是父节点的左孩子的时候
if(parent.Left == node) {
uncle = parent.Right;
// 1. 当删除的节点只有左孩子或者只有右孩子时候
if(node.Right != null) {
/*
* 只需要将该孩子取代即可
* 孩子变为黑色
*
* 结束函数
*/
Node R = node.Right;
R.color = B;
R.Parent = parent;
parent.Left = R;
return;
}
if(node.Left != null){
Node L = node.Left;
L.color = B;
L.Parent = parent;
parent.Left = L;
return;
}
// 2. 如果兄弟节点为红色时候
// 转换为3.3.1
//System.out.println(uncle.key);
if(uncle == null) {
break;
}
if(uncle != null && uncle.color == R) {
/*
* 该情况需要变换为
* 父亲为红色 兄弟为黑色
* 左旋（父）
* 该兄弟变为 以前兄弟的左孩子
*/
parent.color = R;
uncle.color = B;
leftRotate(parent);
}else { //3. 兄弟节点为黑色的时候
//3.1如果兄弟节点的右孩子存在时候（远侄子存在）
//该侄子只能是红色 黑色就不存在
if(uncle.Right != null) {
/*
* 将父亲和兄弟节点的颜色互换
* 将远侄子变为黑色
* 左旋（父）
*
* 可直接删除节点
*
*/
int c;
c = parent.color;
parent.color = uncle.color;
uncle.color = c;
uncle.Right.color = B;
leftRotate(parent);
//node.Parent.Left = null;
break;
}
// 3.2 如果兄弟节点的左孩子存在时候（近侄子存在）
// 转换为3.1
if(uncle.Left != null) {
/*
* 侄子变为黑色
* 兄弟变为红色
* 右旋（兄弟）
*/
uncle.Left.color = B;
uncle.color = R;
rightRotate(uncle);
}else { //3.3 没有侄子时候
// 3.3.1 父亲节点为红色时候
if(parent.color == R) {
/*
* 将兄弟变为红色
* 将父亲变为黑色
*
* 可直接结束函数
*/
uncle.color = R;
parent.color = B;
//parent.Left = null;
break;
}else {
/*
* 将兄弟变为红色
*
* node = parent 继续函数
*/
uncle.color = R;
node = parent;
}
}
}
}else { //当删除的节点是父节点的右孩子的时候
uncle = parent.Left;
//1.当该节点只有左孩子 或者只有右孩子的时候
if(node.Right != null) {
/*
* 只需要将该孩子取代即可
* 孩子变为黑色
* 并删除节点
*/
Node R = node.Right;
R.color = B;
R.Parent = parent;
parent.Right = R;
return;
}else if(node.Left != null){
Node L = node.Left;
L.color = B;
L.Parent = parent;
parent.Right = L;
return;
}
//2.当兄弟节点为红色时候
//转换为 3.3.1 父亲为红色 兄弟为黑色
if(uncle.color == R) {
/*
* 将父亲变为红色
* 将兄弟变为黑色
* 右旋(父亲)
*/
parent.color = R;
uncle.color = B;
rightRotate(parent);
}else { // 3. 当兄弟孩子为黑色时候
System.out.println("b");
// 3.1当兄弟的左孩子存在时 (节点的远侄子） 父亲任意颜色
if(uncle.Left != null) {
/*
* 将父亲和兄弟节点颜色交换
* 远侄子变为黑色
* 右旋（父）
*
* 可直接结束while循环
*/
int b;
b = parent.color;
parent.color = uncle.color;
uncle.color = b;
uncle.Left.color= B;
rightRotate(parent);
break;
}
// 3.2当兄弟左孩子不存在，右孩子存在时(节点无远侄子 只有近侄子) 父亲任意颜色
// 转 3.1
if(uncle.Right != null) {
/*
* 兄弟变为红色
* 近侄子变为黑色
* 左旋（兄弟）
*/
uncle.color = R;
uncle.Right.color = B;
leftRotate(uncle);
}else { //3.3即无左孩子也无右孩子
//3.3.1 父亲为红色时候
if(parent.color == R) {
/*
* 将父亲变为黑色
* 将兄弟变为红色
* 右旋（父亲）
*
* 可结束while循环
*/
System.out.println("c");
parent.color = B;
uncle.color = R;
rightRotate(parent);
break;
}else { // 3.3.2 父亲为黑色时
/*
* 兄弟变为红色
*
* node = parent 继续while
*/
System.out.println("d");
uncle.color = R;
node = parent;
}
}
}
}
}
//删除节点
this.root = remove(del);
}
3.3 删除节点
//删除元素 删除的是节点 只有左孩子或者只有右孩子
private Node remove(Node node) {
if(node.Parent == null) {
if(node.Right != null) {
root = node.Right;
node.Right.Parent = null;
}else if(node.Left != null){
root = node.Left;
node.Left.Parent = null;
}else {
root = null;
}
}else {
if(node.Parent.Right == node) {
if(node.Right == null && node.Left != null) {
node.Parent.Right = node.Left;
node.Left.Parent = node.Parent;
}else if(node.Left == null && node.Right != null){
node.Parent.Right = node.Right;
node.Right.Parent = node.Parent;
}else {
node.Parent.Right = null;
}
}else {
if(node.Right == null && node.Left != null) {
node.Parent.Left = node.Left;
node.Left.Parent = node.Parent;
}else if(node.Left == null && node.Right != null){
node.Parent.Left = node.Right;
node.Right.Parent = node.Parent;
}else {
node.Parent.Left = null;
}
}
}
return root;
}
4.3 删除函数
public void remove(int key) {
Node n = getRemoveNode(root,key);
if(n == null) {
return;
}
removeFixUp(n);
}
4. 辅助函数
4.1 左旋
/*
* 左旋
*
*/
public void leftRotate(Node node){ // 以node左旋
//将node的右节点赋值给y
Node y = node.Right;
if( y == null) { //如果node没有右孩子 则左旋没有任何意思
return;
}
node.Right = y.Left; //y.Left 有可能为空
if(y.Left != null) { //y.Left则有父节点
y.Left.Parent = node;
}
y.Parent = node.Parent; //y的父节点等于x的父节点
/*
* node父节点的左/右 孩子指向y
* node父节点有可能为root 则树的切入点就需要改变
*/
if(node.Parent == null) { //node为父节点
this.root = y; //切入点改为y
}else {
//如不是根节点 则需要判断node是父亲的左孩子或者右孩子
if(node.Parent.Left == node) {
node.Parent.Left = y;
}else {
node.Parent.Right =y;
}
}
node.Parent = y;
y.Left = node;
}
4.2 右旋
/*
* 右旋
*/
public void rightRotate(Node node) {
//将node左孩子赋值给y
Node y = node.Left;
if(y == null) { //如果node没有左孩子则右旋没有任何意义
return;
}
//将y的右孩子赋值node的左孩子
node.Left = y.Right; //不存在则为空，存在则为值
if(y.Right != null) { //如果y的右孩子不存在 则没有父节点
y.Right.Parent = node;
}
//如果node为root
if(node.Parent == null) {
this.root = y;
y.Parent = null;
}else {
if(node.Parent.Left == node) { //如果右旋的树为右孩子树
y.Parent = node.Parent;
node.Parent.Left = y;
}else {
y.Parent = node.Parent;
node.Parent.Right = y;
}
}
y.Right = node;
node.Parent = y;
}
4.3 获得最大最小值
//获取二叉树中最小key的节点
public Node minimum() {
return minimum(root);
}
//获取二叉树中最小key的节点
private Node minimum(Node root) {
//如果当前节点的左孩子为空
if(root.Left == null || root ==null) {
return root;
}
//如果左孩子不为空
return minimum(root.Left);
}
//删除二叉搜索树的最小值 并返回根节点
public Node removeMin() {
root = removeMin(root);
return root;
}
若有收获，就点个赞吧
0 人点赞
