首先创建树结构
class Node {
final boolean RED = true;
final boolean BLACK = false;
int key;
boolean color;
Node left, right, parent;
public Node(int key) {
this.key = key;
this.color = RED;
}
@Override
public String toString() {
String str = "[";
if (this.color == RED) {
str += "红色";
} else {
str += "黑色";
}
return str + "," + this.key + "]";
}
}
创建红黑树类
public class RBTree {
final boolean RED = true;
final boolean BLACK = false;
Node root = null;
}
插入方法
public void insertNode(int key){
Node node = new Node(key);
if(root == null){ //判断根节点是否为空，如果为空，当前节点即为根节点，并把颜色赋成黑色
root = node;
root.color = BLACK;
}else{ //不是根节点，寻找可以当做父节点的节点
Node cur = root;
Node parent = null;
do {
parent = cur;
if(parent.key >= key){
cur = cur.left;
}else{
cur = cur.right;
}
}while (cur != null); //找到父节点之后，判断是在左边还是右边
node.parent = parent;
if(parent.key >= key){
parent.left = node;
}else{
parent.right = node;
}
}
balanceSelf(node); //每次插入要进行自平衡
}
在插入的时候，要进行自平衡，那么就要涉及到几个原子操作：左旋/右旋，变色
左旋
图中的左旋，我们注意到，只有3个地方变了(不要纠结颜色，原子操作互不干扰)
①X的父亲变成了Z的父亲
②Z的左子树从A变成了X
③X的右子树变成了A
左旋方法就很简单了
public void rotateToLeft(Node node) {//把node看成X
Node x = node;
Node z = x.right;
if (z.left != null) {
// 如果z的左子树不为空
z.left.parent = x;
}
x.right = z.left;
if (x.parent == null) {//如果是根节点
root = z;
} else if (x.parent.left == x) {//如果x是x父亲的左子树
x.parent.left = z;
} else {
x.parent.right = z;
}
z.parent = x.parent;
//建立z和x之间的父子关系
x.parent = z;
z.left = x;
}
右旋和左旋相左就是
右旋
右旋
public void rotateToRight(Node node) {
Node x = node;
Node y = node.left;
if (y.right != null) {
y.right.parent = x;
}
x.left = y.right;
if (x.parent == null) {
root = y;
} else if (x.parent.left == x) {
x.parent.left = y;
} else {
x.parent.right = x;
}
y.parent = x.parent;
x.parent = y;
y.right = x;
}
能左旋右旋变色，就可以进行自平衡了
private void balanceSelf(Node node) {
Node parent,grandParent;
//父存在并红色，因为刚插入的数据是红色，所以形成了红 红，要进行自平衡
while((parent = node.parent)!= null && parent.color == RED){
grandParent = parent.parent;
//判断父是祖父的左子树还是右子树，目的是为了找出叔叔节点
if(parent == grandParent.left){
Node uncle = grandParent.right;
//case 1 : 叔叔存在并红色
if(null != uncle && uncle.color == RED){
uncle.color = BLACK;
parent.color = BLACK;
grandParent.color = RED;
node = grandParent; //把祖父又当成X向上回溯
continue;
}
//case 2 : 叔叔黑，当前节点是右孩子
if(parent.right == node){
rotateToLeft(parent);
Node temp = parent;
parent = node;
node = temp;
}
//case 3 : 叔叔黑，当前是左孩子
parent.color = BLACK;
grandParent.color = RED;
rotateToRight(grandParent);
}else{
Node uncle = grandParent.left;
//case 1 : 叔叔存在并红色
if(null != uncle && uncle.color == RED){
uncle.color = BLACK;
parent.color = BLACK;
grandParent.color = RED;
node = grandParent; //把祖父又当成X向上回溯
continue;
}
//case 2 : 叔叔黑，当前节点是左孩子
if(parent.left == node){
rotateToRight(parent);
Node temp = parent;
parent = node;
node = temp;
}
//case 3 : 叔叔黑，当前是右孩子
parent.color = BLACK;
grandParent.color = RED;
rotateToLeft(grandParent);
}
}
root.color = BLACK; // 根节点黑色
}
删除------
全代码
public class RBTree {
final boolean RED = true;
final boolean BLACK = false;
Node root = null;
public void insertNode(int key) {
Node node = new Node(key);
if (root == null) { //判断根节点是否为空，如果为空，当前节点即为根节点，并把颜色赋成黑色
root = node;
root.color = BLACK;
} else { //不是根节点，寻找可以当做父节点的节点
Node cur = root;
Node parent = null;
do {
parent = cur;
if (parent.key >= key) {
cur = cur.left;
} else {
cur = cur.right;
}
} while (cur != null); //找到父节点之后，判断是在左边还是右边
node.parent = parent;
if (parent.key >= key) {
parent.left = node;
} else {
parent.right = node;
}
}
balanceSelf(node);
}
public void rotateToLeft(Node node) {//把node看成X
Node x = node;
Node z = x.right;
if (z.left != null) {
// 如果z的左子树不为空
z.left.parent = x;
}
x.right = z.left;
if (x.parent == null) {//如果是根节点
root = z;
} else if (x.parent.left == x) {//如果x是x父亲的左子树
x.parent.left = z;
} else {
x.parent.right = z;
}
z.parent = x.parent;
//建立z和x之间的父子关系
x.parent = z;
z.left = x;
}
public void rotateToRight(Node node) {
Node x = node;
Node y = node.left;
if (y.right != null) {
y.right.parent = x;
}
x.left = y.right;
if (x.parent == null) {
root = y;
} else if (x.parent.left == x) {
x.parent.left = y;
} else {
x.parent.right = x;
}
y.parent = x.parent;
x.parent = y;
y.right = x;
}
private void balanceSelf(Node node) {
Node parent, grandParent;
//父存在并红色，因为刚插入的数据是红色，所以形成了红 红，要进行自平衡
while ((parent = node.parent) != null && parent.color == RED) {
grandParent = parent.parent;
//判断父是祖父的左子树还是右子树，目的是为了找出叔叔节点
if (parent == grandParent.left) {
Node uncle = grandParent.right;
//case 1 : 叔叔存在并红色
if (null != uncle && uncle.color == RED) {
uncle.color = BLACK;
parent.color = BLACK;
grandParent.color = RED;
node = grandParent; //把祖父又当成X向上回溯
continue;
}
//case 2 : 叔叔黑，当前节点是右孩子
if (parent.right == node) {
rotateToLeft(parent);
Node temp = parent;
parent = node;
node = temp;
}
//case 3 : 叔叔黑，当前是左孩子
parent.color = BLACK;
grandParent.color = RED;
rotateToRight(grandParent);
} else {
Node uncle = grandParent.left;
//case 1 : 叔叔存在并红色
if (null != uncle && uncle.color == RED) {
uncle.color = BLACK;
parent.color = BLACK;
grandParent.color = RED;
node = grandParent; //把祖父又当成X向上回溯
continue;
}
//case 2 : 叔叔黑，当前节点是左孩子
if (parent.left == node) {
rotateToRight(parent);
Node temp = parent;
parent = node;
node = temp;
}
//case 3 : 叔叔黑，当前是右孩子
parent.color = BLACK;
grandParent.color = RED;
rotateToLeft(grandParent);
}
}
root.color = BLACK; // 根节点黑色
}
public void inOrder() {
this.inOrder(root);
}
public void inOrder(Node node) {
if (node == null) {
return;
}
inOrder(node.left);
System.out.println(node);
inOrder(node.right);
}
}
class Node {
final boolean RED = true;
final boolean BLACK = false;
int key;
boolean color;
Node left, right, parent;
public Node(int key) {
this.key = key;
this.color = RED;
}
@Override
public String toString() {
String str = "[";
if (this.color == RED) {
str += "红色";
} else {
str += "黑色";
}
return str + "," + this.key + "]";
}
}
网友评论