JavaDataStructures/Heap/LLRB.java at master · benaich/JavaDataStructures · GitHub

History

108 lines (90 loc) · 2.78 KB

Raw

100

101

102

103

104

105

106

107

108

package Heap;

public class LLRB<T extends Comparable<? super T>> {

public static boolean RED = true;

public static boolean BLACK = false;

public class Node {

public Node left;

public Node right;

public T key;

public boolean color;

public Node(T key, Node left, Node right, boolean color) {

this.key = key;

this.left = left;

this.right = right;

this.color = color;

}

public Node rotateLeft() {

return build(right.key, build(key, left, right.left, RED), right.right, color);

}

public Node rotateRight() {

return build(left.key, left.left, build(key, left.right, right, RED), color);

}

public void sand() {

color = RED;

left.color = BLACK;

right.color = BLACK;

}

public Node balance() {

if (isRed(right) && !isRed(left)) {

return rotateLeft().balance();

}

if (isRed(left) && isRed(left.left)) {

return rotateRight();

}

return this;

}

public Node build(T key, Node left, Node right, boolean color) {

return new Node(key, left, right, color);

}

public Node build(T key) {

return new Node(key, null, null, RED);

}

public Node put(Node p, T x) {

if (p == null) {

return build(x);

}

if (isRed(p.left) && isRed(p.right)) {

p.sand();

}

if (p.key.compareTo(x) > 0) {

return build(p.key, put(p.left, x), p.right, p.color).balance();

} else {

return build(p.key, p.left, put(p.right, x), p.color).balance();

}

public boolean isRed(Node p) {

return (p != null) && p.color == RED;

}

public void printNice(Node root, int level) {

if (root == null) {

return;

}

printNice(root.right, level + 1);

if (level != 0) {

for (int i = 0; i < level - 1; i++) {

System.out.print("| ");

}

if (isRed(root)) {

System.out.println("|===" + root.key);

} else {

System.out.println("|---" + root.key);

}

} else {

System.out.println(root.key);

}

printNice(root.left, level + 1);

}

public static void main(String[] args) {

LLRB<Integer> app = new LLRB<>();

LLRB.Node root = app.build(2);

root = app.put(root, 4);

root = app.put(root, 1);

root = app.put(root, 3);

root = app.put(root, 5);

root = app.put(root, 6);

root = app.put(root, 8);

root = app.put(root, 9);

app.printNice(root, 1);

}

JavaDataStructures/Heap/LLRB.java at master · benaich/JavaDataStructures · GitHub

Expand file tree

Breadcrumbs

LLRB.java

Latest commit

History

Breadcrumbs

LLRB.java

File metadata and controls