Created
March 31, 2014 03:31
-
-
Save JerrettDavis/9884756 to your computer and use it in GitHub Desktop.
Red Black Tree
This file contains hidden or 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
| package collections; | |
| import collections.BinarySearchTree.Node; | |
| public class RedBlackBST<E extends Comparable<E>> { | |
| private static final int RED = 0; | |
| private static final int BLACK = 1; | |
| Node root; | |
| public RedBlackBST() { | |
| root = null; | |
| } | |
| public E find(E key) { | |
| Node current = root; | |
| while (current.data.compareTo(key) != 0) { | |
| if (current.data.compareTo(key) > 0) | |
| current = current.left; | |
| else | |
| current = current.right; | |
| if (current == null) | |
| return null; | |
| } | |
| return current.data; | |
| } | |
| public void insert(E data) { | |
| Node newNode = new Node(); | |
| newNode.data = data; | |
| if (root == null) { | |
| root = newNode; | |
| } else { | |
| Node current = root; | |
| Node parent; | |
| while (true) { | |
| parent = current; | |
| if (data.compareTo(current.data) < 0) { | |
| current = current.left; | |
| if (current == null) { | |
| parent.left = newNode; | |
| newNode.parent = parent; | |
| break; | |
| } | |
| } else { | |
| current = current.right; | |
| if (current == null) { | |
| parent.right = newNode; | |
| newNode.parent = parent; | |
| break; | |
| } | |
| } | |
| } | |
| } | |
| insertCase1(newNode); | |
| } | |
| private void insertCase1(Node n) { | |
| if (n.parent==null) | |
| n.color=BLACK; | |
| else | |
| insertCase2(n); | |
| } | |
| private void insertCase2(Node n) { | |
| if(n.parent.color==BLACK) | |
| return; | |
| else | |
| insertCase3(n); | |
| } | |
| private void insertCase3(Node n) { | |
| Node u = getUncle(n); | |
| if (u!=null && u.color==RED) { | |
| n.parent.color=BLACK; | |
| u.color=BLACK; | |
| Node g = getGrandparent(n); | |
| g.color=RED; | |
| insertCase1(g); | |
| } else | |
| insertCase4(n); | |
| } | |
| private void insertCase4(Node n) { | |
| Node g = getGrandparent(n); | |
| if(n==n.parent.right && n.parent==g.left) { | |
| rotateLeft(n.parent); | |
| n=n.left; | |
| } else if (n==n.parent.left && n.parent==g.right) { | |
| rotateRight(n.parent); | |
| n=n.right; | |
| } | |
| insertCase5(n); | |
| } | |
| private void insertCase5(Node n) { | |
| Node g = getGrandparent(n); | |
| n.parent.color=BLACK; | |
| g.color=RED; | |
| if (n==n.parent.left) | |
| rotateRight(g); | |
| else | |
| rotateLeft(g); | |
| } | |
| public boolean delete(E key) { | |
| Node current = root; | |
| Node parent = root; | |
| boolean isLeftChild = true; | |
| while (current.data.compareTo(key) != 0) { | |
| parent = current; | |
| if (current.data.compareTo(key)>0) { | |
| isLeftChild = true; | |
| current = current.left; | |
| } else { | |
| isLeftChild = false; | |
| current = current.right; | |
| } | |
| if (current == null) | |
| return false; | |
| } | |
| if (current.left == null && current.right == null) { | |
| if (current == root) | |
| root = null; | |
| else if (isLeftChild) | |
| parent.left = null; | |
| else | |
| parent.right = null; | |
| } else if (current.right == null) | |
| if (current == root) | |
| root = current.left; | |
| else if (isLeftChild) | |
| parent.left = current.left; | |
| else | |
| parent.right = current.left; | |
| else if (current.left == null) | |
| if (current == root) | |
| root = current.right; | |
| else if (isLeftChild) | |
| parent.left = current.right; | |
| else | |
| parent.right = current.right; | |
| else { | |
| Node successor = getSuccessor(current); | |
| if (current == root) | |
| root = successor; | |
| else if (isLeftChild) | |
| parent.left = successor; | |
| else | |
| parent.right = successor; | |
| successor.left = current.left; | |
| } | |
| return true; | |
| } | |
| private Node getSuccessor(Node delNode) { | |
| Node successorParent = delNode; | |
| Node successor = delNode; | |
| Node current = delNode.right; | |
| while (current != null) { | |
| successorParent = successor; | |
| successor = current; | |
| current = current.left; | |
| } | |
| if (successor != delNode.right) { | |
| successorParent.left = successor.right; | |
| successor.right = delNode.right; | |
| } | |
| return successor; | |
| } | |
| private void deleteCase1(Node node) { | |
| if(node.parent==null) | |
| return; | |
| else | |
| deleteCase2(node); | |
| } | |
| private void deleteCase2(Node node) { | |
| Node sibling = getSibling(node); | |
| if (sibling.color==RED) { | |
| node.parent.color=RED; | |
| sibling.color=BLACK; | |
| if(node==node.parent.left) | |
| rotateLeft(node.parent); | |
| else | |
| rotateRight(node.parent); | |
| } | |
| deleteCase3(node); | |
| } | |
| private void deleteCase3(Node n) { | |
| Node s = getSibling(n); | |
| if(n.parent.color==BLACK && s.color==BLACK && s.left.color == BLACK && s.right.color==BLACK) { | |
| s.color=RED; | |
| deleteCase1(n.parent); | |
| } else | |
| deleteCase4(n); | |
| } | |
| private void deleteCase4(Node n) { | |
| Node s = getSibling(n); | |
| if(n.parent.color == RED && s.color==BLACK && s.left.color==BLACK && s.right.color==BLACK) { | |
| s.color=RED; | |
| n.parent.color=BLACK; | |
| } else | |
| deleteCase5(n); | |
| } | |
| private void deleteCase5(Node n) { | |
| Node s = getSibling(n); | |
| if (s.color == BLACK) { | |
| if(n==n.parent.left && s.right.color ==BLACK && s.left.color==RED) { | |
| s.color=RED; | |
| s.left.color=BLACK; | |
| rotateRight(s); | |
| } else if (n==n.parent.right && s.left.color==BLACK && s.right.color==RED) { | |
| s.color=RED; | |
| s.right.color=BLACK; | |
| rotateLeft(s); | |
| } | |
| } | |
| deleteCase6(n); | |
| } | |
| private void deleteCase6(Node n) { | |
| Node s = getSibling(n); | |
| s.color=n.parent.color; | |
| n.parent.color=BLACK; | |
| if(n==n.parent.left) { | |
| s.right.color=BLACK; | |
| rotateLeft(n.parent); | |
| } else { | |
| s.left.color=BLACK; | |
| rotateRight(n.parent); | |
| } | |
| } | |
| private Node getSibling(Node n) { | |
| if (n.parent.left == n) | |
| return n.parent.right; | |
| else | |
| return n.parent.left; | |
| } | |
| private Node getGrandparent(Node n) { | |
| if(n!=null && n.parent!=null) | |
| return n.parent.parent; | |
| else | |
| return null; | |
| } | |
| private Node getUncle(Node n) { | |
| Node g = getGrandparent(n); | |
| if(g==null) | |
| return null; | |
| if(n.parent==g.left) | |
| return g.right; | |
| else | |
| return g.left; | |
| } | |
| private void rotateLeft(Node node) { | |
| Node replacement = node.right; | |
| node.right = replacement.left; | |
| if (replacement.left!=null) | |
| replacement.left.parent = node; | |
| replacement.parent = node.parent; | |
| if (node.parent==null) | |
| root = replacement; | |
| else if (node.parent.left == node) | |
| node.parent.left = replacement; | |
| else | |
| node.parent.right = replacement; | |
| replacement.left = node; | |
| node.parent = replacement; | |
| } | |
| private void rotateRight(Node node) { | |
| Node replacement = node.left; | |
| node.left = replacement.right; | |
| if (replacement.right!=null) | |
| replacement.right.parent = node; | |
| replacement.parent = node.parent; | |
| if (node.parent==null) | |
| root = replacement; | |
| else if (node.parent.right == node) | |
| node.parent.right = replacement; | |
| else | |
| node.parent.left = replacement; | |
| replacement.right = node; | |
| node.parent = replacement; | |
| } | |
| public void inOrderTraverse(Node root){ | |
| if(root != null){ | |
| inOrderTraverse(root.left); | |
| System.out.print(" "+root.data); | |
| inOrderTraverse(root.right); | |
| } | |
| } | |
| public void traverse() { | |
| inOrderTraverse(root); | |
| } | |
| class Node { | |
| E data; | |
| Node parent; | |
| Node left; | |
| Node right; | |
| int color; | |
| public String toString() { | |
| return "{" + data + "}"; | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Dude, thanks a lot ^^