Red Black Tree (Java)
From LiteratePrograms
- Other implementations: Java | Python
Implementation
package org.presci.tree.rb;
public class Entry<K extends Comparable<? super K>> {
private K data;
private Entry<K> parent;
private Entry<K> left;
private Entry<K> right;
private boolean red = true;
public Entry(K data) {
this.data = data;
}
public Entry(K data, Entry<K> parent) {
this.data = data;
this.parent = parent;
}
public Entry(K data, Entry<K> parent, boolean red) {
this.data = data;
this.parent = parent;
this.red = red;
}
public K getData() {
return data;
}
public void setData(K data) {
this.data = data;
}
public Entry<K> getParent() {
return parent;
}
public void setParent(Entry<K> parent) {
this.parent = parent;
}
public Entry<K> getLeft() {
return left;
}
public void setLeft(Entry<K> left) {
this.left = left;
}
public Entry<K> getRight() {
return right;
}
public void setRight(Entry<K> right) {
this.right = right;
}
public boolean isRed() {
return red;
}
public void setRed(boolean red) {
this.red = red;
}
public Entry<K> getUncle() {
if (this.parent != null && this.parent.parent != null) {
if (this.parent.parent.left != this.parent) {
return this.parent.parent.left;
} else {
return this.parent.parent.right;
}
}
return null;
}
public Entry<K> getGrandParent() {
if (this.parent != null && this.parent.parent != null) {
return this.parent.parent;
}
return null;
}
@Override
public String toString() {
return data + " -> " + strLeft() + " " + (red ? "RED" : "BLACK") + " {"
+ (parent != null ? parent.toString() : "root") + "}";
}
private String strLeft(){
Boolean bool = isLeft();
if ( bool != null){
if (bool){
return "[L]";
}else {
return "[R]";
}
}
return "";
}
public Boolean isLeft() {
if ( this.parent != null){
if ( this.parent.left == this){
return true;
}
return false;
}
return null;
}
}
Implementation
package org.presci.tree.rb;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
public class RBTree<L extends Comparable<? super L>> {
private Entry<L> data;
public void add(L arg0) {
if (data == null) {
data = new Entry<L>(arg0, null, false);
return;
}
_add(arg0);
}
private void _add(L arg0) {
if (data.getData() == arg0) {
System.out.println("Duplicate Value : " + data);
return;
}
Entry<L> p = data;
Entry<L> dt = new Entry<L>(arg0);
while ( true){
int n = arg0.compareTo(p.getData());
if ( n < 0){
if ( p.getLeft() != null){
p = p.getLeft();
}else {
p.setLeft(dt);
dt.setParent(p);
break;
}
}else {
if (p.getRight() != null) {
p = p.getRight();
} else {
p.setRight(dt);
dt.setParent(p);
break;
}
}
}
rebalance( dt);
}
private void rebalance(Entry<L> dt) {
// Cond. 1
if (dt.getParent() == null) {
dt.setRed(false);
return;
}
// Cond. 2
if (!dt.getParent().isRed()) {
return;
}
// Cond. 3
if (dt.getUncle() != null && dt.getUncle().isRed()) {
dt.getUncle().setRed(false);
dt.getParent().setRed(false);
if (dt.getGrandParent() != null) {
dt.getGrandParent().setRed(true);
this.rebalance(dt.getGrandParent());
return;
}
}
this.pivot_rebalance(dt);
}
private void pivot_rebalance(Entry<L> dt) {
/* Check if the parent is right or left */
if (dt.getParent().equals(dt.getGrandParent().getLeft())) {
// the parent is left parent
/*
* True - dt is the left child, left straight line pivot around the
* parent
*/
boolean b = dt.equals(dt.getParent().getLeft());
if (b){
pivotright(dt.getParent(), b);
}else {
pivotright ( dt, b);
}
/*
* False dt is the right child pivot around the dt rearrange and
* pivot
*/
} else {
// the parent is right parent
/*
* True dt is the right child of right parent. Straight line pivot
* around the parent
*/
boolean b = dt.equals(dt.getParent().getRight());
if (b){
pivotleft(dt.getParent(), b);
}else {
pivotleft(dt, b);
}
/*
* False dt is the left child pivot around the dt rearrange and
* pivot
*/
}
}
@SuppressWarnings(value = { "unused" })
private void pivotright(Entry<L> arg0, final boolean arg1) {
// true means parent
Entry<L> y = arg0; // node
Entry<L> b = arg1? null:y.getLeft(); // left
Entry<L> c = y.getRight();// right
Entry<L> x = arg1?y.getLeft():y.getParent();
Entry<L> z = arg1? y.getParent(): y.getGrandParent();
Entry<L> gg = arg1? y.getGrandParent(): y.getGrandParent().getParent();
Boolean isroot = z.isLeft();
if (!arg1) {
x.setRight(b);
if (b != null)
b.setParent(x);
z.setLeft(y);
y.setParent(z);
y.setLeft(x);
x.setParent(y);
}
z.setLeft(c);
if (c != null)
c.setParent(z);
y.setRight(z);
z.setParent(y);
if (isroot == null) {
y.setParent(null);
this.data = y;
} else if (isroot) {
gg.setLeft(y);
y.setParent(gg);
} else {
gg.setRight(y);
y.setParent(gg);
}
z.setRed(true);
x.setRed(true);
y.setRed(false);
if ( gg != null)
rebalance(gg);
}
@SuppressWarnings(value = { "unused" })
private void pivotleft(Entry<L> arg0, final boolean arg1) {
// true means parent
Entry<L> y = arg0; // node
Entry<L> b = y.getLeft(); // left
Entry<L> c = arg1? null:y.getRight();
Entry<L> z = arg1?y.getRight():y.getParent();
Entry<L> x = arg1?y.getParent():y.getGrandParent();
Entry<L> gg = arg1?y.getGrandParent():y.getGrandParent().getParent();
Boolean isroot = x.isLeft();
if (!arg1) {
z.setLeft(c);
if (c != null)
c.setParent(z);
x.setRight(y);
y.setRight(z);
z.setParent(y);
y.setParent(x);
}
x.setRight(b);
if (b != null)
b.setParent(x);
y.setLeft(x);
x.setParent(y);
if (isroot == null) {
y.setParent(null);
this.data = y;
} else if (isroot) {
gg.setLeft(y);
y.setParent(gg);
} else {
gg.setRight(y);
y.setParent(gg);
}
x.setRed(true);
if ( z != null) z.setRed(true);
y.setRed(false);
if (gg != null)
rebalance(gg);
}
public void printInorder() {
_printInorder(data);
}
private void _printInorder(Entry<L> data2) {
if (data2.getLeft() != null) {
_printInorder(data2.getLeft());
}
System.out.println(data2);
if (data2.getRight() != null) {
_printInorder(data2.getRight());
}
}
public List<L> getList(){
Stack<Entry<L>> nodes = new Stack<Entry<L>>();
List<L> list = new LinkedList<L>();
Entry<L> node = data;
while ( !nodes.isEmpty() || null != node){
if ( null != node){
// nodes.push(node);
nodes.push(node);
node= node.getLeft();
}else {
node = nodes.pop();
// System.out.println(node.getData());
list.add( node.getData());
node = node.getRight();
}
}
return list;
}
public boolean exist(L arg0){
return _exist(data, new Entry<L>(arg0));
}
private boolean _exist(Entry<L> arg0, Entry<L> arg1){
if ( arg0 == null){
return false;
}
int n = arg1.getData().compareTo(arg0.getData());
if (n ==0){
return true;
}
if ( n <0){
return _exist( arg0.getLeft(), arg1);
}else if ( n > 0){
return _exist( arg0.getRight(), arg1);
}
return false;
}
}
Deletion BST deletion can be applied to the implementation to delete any node.
| Download code |