用java代码实现红黑树
时间: 2023-03-14 10:23:50 浏览: 69
用Java代码实现红黑树可以使用以下代码: class RedBlackTree {
private Node root;
private static final int BLACK = 0;
private static final int RED = 1; class Node {
int data;
Node left;
Node right;
int color;
} public void insert(int data) {
Node node = new Node();
node.data = data;
if (root == null) {
root = node;
root.color = BLACK;
} else {
Node parent, x = root;
while (x != null) {
parent = x;
if (data < x.data) {
x = x.left;
} else {
x = x.right;
}
}
if (data < parent.data) {
parent.left = node;
} else {
parent.right = node;
}
node.color = RED;
balanceTree(node);
}
} private void balanceTree(Node node) {
while (node != root && node.color != BLACK && node.parent.color == RED) {
if (node.parent == node.parent.parent.left) {
Node uncle = node.parent.parent.right;
if (uncle != null && uncle.color == RED) {
node.parent.color = BLACK;
uncle.color = BLACK;
node.parent.parent.color = RED;
node = node.parent.parent;
} else {
if (node == node.parent.right) {
node = node.parent;
leftRotate(node);
}
node.parent.color = BLACK;
node.parent.parent.color = RED;
rightRotate(node.parent.parent);
}
} else {
Node uncle = node.parent.parent.left;
if (uncle != null && uncle.color == RED) {
node.parent.color = BLACK;
uncle.color = BLACK;
node.parent.parent.color = RED;
node = node.parent.parent;
} else {
if (node == node.parent.left) {
node = node.parent;
rightRotate(node);
}
node.parent.color = BLACK;
node.parent.parent.color = RED;
leftRotate(node.parent.parent);
}
}
}
root.color = BLACK;
} private void leftRotate(Node x) {
Node y = x.right;
x.right = y.left;
if (y.left != null) {
y.left.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
root = y;
} else if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
y.left = x;
x.parent = y;
} private void rightRotate(Node x) {
Node y = x.left;
x.left = y.right;
if (y.right != null) {
y.right.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
root = y;
} else if (x == x.parent.right) {
x.parent.right = y;
} else {
x.parent.left = y;
}
y.right = x;
x.parent = y;
}
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)