Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- enum Color {
- RED,
- BLACK,
- }
- class RBTree {
- private class Element {
- int value;
- Element right, left, parent;
- Color color;
- Element(int v, Color color, Element parent) {
- value = v;
- this.parent = parent;
- right = null;
- left = null;
- this.color = color;
- }
- public String toString() {
- return (color == Color.RED ? "R" : "B") + "(" + value + ")";
- }
- }
- private Element root;
- private int tempLayer;
- RBTree() {
- root = null;
- }
- private Element parentOf(int key) {
- Element current = root;
- while(current != null) {
- if(current.right != null)
- if(current.right.value == key)
- return current;
- if(current.left != null)
- if(current.left.value == key)
- return current;
- if(key < current.value) {
- current = current.left;
- } else {
- current = current.right;
- }
- }
- return null;
- }
- private void leftRotate(Element x) {
- Element 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(Element x) {
- Element 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;
- }
- private Element treePut(int key) {
- if(root == null) {
- root = new Element(key, Color.BLACK, null);
- return root;
- }
- Element current = root;
- while(true) {
- if(key < current.value) {
- if(current.left == null) {
- current.left = new Element(key, Color.RED, null);
- current = current.left;
- break;
- }
- current = current.left;
- } else {
- if(current.right == null) {
- current.right = new Element(key, Color.RED, null);
- current = current.right;
- break;
- }
- current = current.right;
- }
- }
- current.parent = parentOf(current.value);
- return current;
- }
- void add(int key) {
- Element current = treePut(key); // standardowe dodawanie do drzewa binarnego
- // to masz od ikłilsa - obracanie tak żeby było tyle samo czarnych po 2 stronach i nie było 2
- // czerwonych obok siebie
- while(current != root && current.parent.color == Color.RED) {
- if(current.parent == current.parent.parent.left) {
- Element y = current.parent.parent.right;
- if(y.color == Color.RED) {
- current.parent.color = Color.BLACK;
- y.color = Color.BLACK;
- current.parent.parent.color = Color.RED;
- current = current.parent.parent;
- } else {
- if(current == current.parent.right) {
- current = current.parent;
- leftRotate(current);
- }
- current.parent.color = Color.BLACK;
- current.parent.parent.color = Color.RED;
- rightRotate(current.parent.parent);
- }
- }
- // -------------------------------------------------------------
- if(current.parent == current.parent.parent.right) {
- Element y = current.parent.parent.left;
- if(y.color == Color.RED) {
- current.parent.color = Color.BLACK;
- y.color = Color.BLACK;
- current.parent.parent.color = Color.RED;
- current = current.parent.parent;
- } else {
- if(current == current.parent.left) {
- current = current.parent;
- leftRotate(current);
- }
- current.parent.color = Color.BLACK;
- current.parent.parent.color = Color.RED;
- rightRotate(current.parent.parent);
- }
- }
- root.color = Color.BLACK;
- }
- }
- void inorder_show() {
- System.out.print("In-order: ");
- inorder_show(root);
- System.out.println();
- }
- void preorder_show() {
- System.out.print("Pre-order: ");
- preorder_show(root);
- System.out.println();
- }
- void postorder_show() {
- System.out.print("Post-order: ");
- postorder_show(root);
- System.out.println();
- }
- private void inorder_show(Element current) {
- if(current != null) {
- inorder_show(current.left);
- System.out.print(current + " ");
- inorder_show(current.right);
- }
- }
- private void preorder_show(Element current) {
- if(current != null) {
- System.out.print(current + " ");
- preorder_show(current.left);
- preorder_show(current.right);
- }
- }
- private void postorder_show(Element current) {
- if(current != null) {
- postorder_show(current.left);
- postorder_show(current.right);
- System.out.print(current + " ");
- }
- }
- void rowprint() {
- ArrayList<ArrayList<Element>> elements = new ArrayList<>();
- rowprint(elements, root, 0);
- for(ArrayList<Element> row: elements) {
- for(Element element: row) {
- System.out.print(element + " ");
- }
- System.out.println();
- }
- }
- private void rowprint(ArrayList<ArrayList<Element>> elements, Element current, int layer) {
- if(current != null) {
- if(elements.size() == layer) {
- elements.add(new ArrayList<>());
- }
- elements.get(layer).add(current);
- rowprint(elements, current.left, layer+1);
- rowprint(elements, current.right, layer+1);
- }
- }
- boolean find(int key) {
- Element current = root;
- System.out.print("Tree contains " + key + " ? - ");
- while(current != null) {
- if(current.value == key)
- return true;
- if(key < current.value) {
- current = current.left;
- } else {
- current = current.right;
- }
- }
- return false;
- }
- int nodeCount() {
- return nodeCount(root);
- }
- private int nodeCount(Element current) {
- if(current != null) {
- return 1 + nodeCount(current.left) + nodeCount(current.right);
- }
- return 0;
- }
- int height() {
- tempLayer = 0;
- height(root, 0);
- return tempLayer;
- }
- private void height(Element current, int layer) {
- if(current != null) {
- height(current.left, layer + 1);
- height(current.right, layer + 1);
- if (tempLayer < layer) tempLayer = layer;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement