Created
March 30, 2022 10:57
-
-
Save KKcorps/98b625ab39320e7b9b9ed91bebdb222e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// generate red-black tree from a list | |
void generateRedBlackTree(){ | |
// create a red-black tree | |
// for each node in the list | |
// insert the node into the tree | |
RedBlackTree tree = new RedBlackTree(); | |
for(Node node : list){ | |
tree.insert(node); | |
} | |
} | |
public class RedBlackTree { | |
Node root; | |
public RedBlackTree(){ | |
root = null; | |
} | |
public void insert(Node node){ | |
root = insert(root, node); | |
} | |
private Node insert(Node root, Node node){ | |
if(root == null){ | |
return node; | |
} | |
if(node.key < root.key){ | |
root.left = insert(root.left, node); | |
} | |
else{ | |
root.right = insert(root.right, node); | |
} | |
return root; | |
} | |
// find the node with the given key | |
public Node find(int key){ | |
return find(root, key); | |
} | |
private Node find(Node root, int key){ | |
if(root == null){ | |
return null; | |
} | |
if(root.key == key){ | |
return root; | |
} | |
if(key < root.key){ | |
return find(root.left, key); | |
} | |
else{ | |
return find(root.right, key); | |
} | |
} | |
// balance the tree | |
public void balance(){ | |
balance(root); | |
} | |
private void balance(Node root){ | |
if(root == null){ | |
return; | |
} | |
balance(root.left); | |
balance(root.right); | |
root.balance(); | |
} | |
// print the tree | |
public void print(){ | |
print(root); | |
} | |
private void print(Node root){ | |
if(root == null){ | |
return; | |
} | |
print(root.left); | |
System.out.println(root.key); | |
print(root.right); | |
} | |
} | |
public class Node { | |
int key; | |
Node left; | |
Node right; | |
Node parent; | |
boolean color; | |
Node[] adjacent; | |
public Node(int key){ | |
this.key = key; | |
this.left = null; | |
this.right = null; | |
this.parent = null; | |
this.color = true; | |
this.adjacent = new Node[0]; | |
} | |
public void addAdjacent(Node node){ | |
Node[] newAdjacent = new Node[adjacent.length + 1]; | |
for(int i = 0; i < adjacent.length; i++){ | |
newAdjacent[i] = adjacent[i]; | |
} | |
newAdjacent[adjacent.length] = node; | |
adjacent = newAdjacent; | |
} | |
public void balance(){ | |
if(color == false){ | |
return; | |
} | |
if(parent == null){ | |
color = false; | |
return; | |
} | |
if(parent.color == false){ | |
return; | |
} | |
if(parent.parent == null){ | |
return; | |
} | |
if(parent.parent.left == parent){ | |
if(parent.right == this){ | |
rotateLeft(); | |
} | |
rotateRight(); | |
color = false; | |
parent.color = false; | |
parent.parent.color = true; | |
} | |
else{ | |
if(parent.left == this){ | |
rotateRight(); | |
} | |
rotateLeft(); | |
color = false; | |
parent.color = false; | |
parent.parent.color = true; | |
} | |
} | |
public void rotateLeft(){ | |
Node temp = right; | |
right = temp.left; | |
temp.left = this; | |
temp.parent = parent; | |
if(parent != null){ | |
if(parent.left == this){ | |
parent.left = temp; | |
} | |
else{ | |
parent.right = temp; | |
} | |
} | |
else{ | |
root = temp; | |
} | |
this.parent = temp; | |
} | |
public void rotateRight(){ | |
Node temp = left; | |
left = temp.right; | |
temp.right = this; | |
temp.parent = parent; | |
if(parent != null){ | |
if(parent.left == this){ | |
parent.left = temp; | |
} | |
else{ | |
parent.right = temp; | |
} | |
} | |
else{ | |
root = temp; | |
} | |
this.parent = temp; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment