【code】java赤黒樹
13843 ワード
import java.util.*;
public class RedBlackTree<T extends Comparable>
{
//
private static final boolean RED = false;
private static final boolean BLACK = true;
static class Node
{
Object data;
Node parent;
Node left;
Node right;
//
boolean color = BLACK;
public Node(Object data , Node parent
, Node left , Node right)
{
this.data = data;
this.parent = parent;
this.left = left;
this.right = right;
}
public String toString()
{
return "[data=" + data
+ ", color=" + color + "]";
}
public boolean equals(Object obj)
{
if (this == obj)
{
return true;
}
if (obj.getClass() == Node.class)
{
Node target = (Node)obj;
return data.equals(target.data)
&& color == target.color
&& left == target.left
&& right == target.right
&& parent == target.parent;
}
return false;
}
}
private Node root;
//
public RedBlackTree()
{
root = null;
}
public RedBlackTree(T o)
{
root = new Node(o , null , null , null);
}
//
public void add(T ele)
{
// null
if (root == null)
{
root = new Node(ele , null , null , null);
}
else
{
Node current = root;
Node parent = null;
int cmp = 0;
// ，
do
{
parent = current;
cmp = ele.compareTo(current.data);
//
if (cmp > 0)
{
//
current = current.right;
}
//
else
{
//
current = current.left;
}
}
while (current != null);
//
Node newNode = new Node(ele , parent , null , null);
//
if (cmp > 0)
{
//
parent.right = newNode;
}
//
else
{
//
parent.left = newNode;
}
//
fixAfterInsertion(newNode);
}
}
//
public void remove(T ele)
{
//
Node target = getNode(ele);
// 、
if (target.left != null && target.right != null)
{
// target
//s target
Node s = target.left;
// target
while (s.right != null)
{
s = s.right;
}
// s p
target.data = s.data;
target = s;
}
// ， null
Node replacement = (target.left != null ? target.left : target.right);
if (replacement != null)
{
// replacement parent target parent
replacement.parent = target.parent;
// target parent null， target
if (target.parent == null)
{
root = replacement;
}
// target
else if (target == target.parent.left)
{
// target left replacement
target.parent.left = replacement;
}
// target
else
{
// target right replacement
target.parent.right = replacement;
}
// target
target.left = target.right = target.parent = null;
//
if (target.color == BLACK)
{
fixAfterDeletion(replacement);
}
}
//target
else if (target.parent == null)
{
root = null;
}
else
{
//target ， 。
//
if (target.color == BLACK)
{
fixAfterDeletion(target);
}
if (target.parent != null)
{
// target
if (target == target.parent.left)
{
// target left null
target.parent.left = null;
}
// target
else if (target == target.parent.right)
{
// target right null
target.parent.right = null;
}
// target parent null
target.parent = null;
}
}
}
//
public Node getNode(T ele)
{
//
Node p = root;
while (p != null)
{
int cmp = ele.compareTo(p.data);
// p
if (cmp < 0)
{
//
p = p.left;
}
// p
else if (cmp > 0)
{
//
p = p.right;
}
else
{
return p;
}
}
return null;
}
//
public List<Node> breadthFirst()
{
Queue<Node> queue = new ArrayDeque<Node>();
List<Node> list = new ArrayList<Node>();
if( root != null)
{
// “ ”
queue.offer(root);
}
while(!queue.isEmpty())
{
// “ ” List
list.add(queue.peek());
Node p = queue.poll();
// null， “ ”
if(p.left != null)
{
queue.offer(p.left);
}
// null， “ ”
if(p.right != null)
{
queue.offer(p.right);
}
}
return list;
}
//
private void fixAfterInsertion(Node x)
{
x.color = RED;
// x ， x
while (x != null && x != root
&& x.parent.color == RED)
{
// x
if (parentOf(x) == leftOf(parentOf(parentOf(x))))
{
// x
Node y = rightOf(parentOf(parentOf(x)));
// x
if (colorOf(y) == RED)
{
// x
setColor(parentOf(x), BLACK);
// x
setColor(y, BLACK);
// x
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
}
// x
else
{
// x
if (x == rightOf(parentOf(x)))
{
// x x
x = parentOf(x);
rotateLeft(x);
}
// x
setColor(parentOf(x), BLACK);
// x
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
}
// x
else
{
// x
Node y = leftOf(parentOf(parentOf(x)));
// x
if (colorOf(y) == RED)
{
// x 。
setColor(parentOf(x), BLACK);
// x
setColor(y, BLACK);
// x
setColor(parentOf(parentOf(x)), RED);
// x x
x = parentOf(parentOf(x));
}
// x
else
{
// x
if (x == leftOf(parentOf(x)))
{
// x x
x = parentOf(x);
rotateRight(x);
}
// x
setColor(parentOf(x), BLACK);
// x
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
//
root.color = BLACK;
}
//
private void fixAfterDeletion(Node x)
{
// x ， x
while (x != root && colorOf(x) == BLACK)
{
// x
if (x == leftOf(parentOf(x)))
{
// x
Node sib = rightOf(parentOf(x));
// sib
if (colorOf(sib) == RED)
{
// sib
setColor(sib, BLACK);
// x
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
// sib x
sib = rightOf(parentOf(x));
}
// sib
if (colorOf(leftOf(sib)) == BLACK
&& colorOf(rightOf(sib)) == BLACK)
{
// sib
setColor(sib, RED);
// x x
x = parentOf(x);
}
else
{
// sib
if (colorOf(rightOf(sib)) == BLACK)
{
// sib
setColor(leftOf(sib), BLACK);
// sib
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
// sib x
setColor(sib, colorOf(parentOf(x)));
// x
setColor(parentOf(x), BLACK);
// sib
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
}
// x
else
{
// x
Node sib = leftOf(parentOf(x));
// sib
if (colorOf(sib) == RED)
{
// sib
setColor(sib, BLACK);
// sib
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
// sib
if (colorOf(rightOf(sib)) == BLACK
&& colorOf(leftOf(sib)) == BLACK)
{
// sib
setColor(sib, RED);
// x x
x = parentOf(x);
}
else
{
// sib
if (colorOf(leftOf(sib)) == BLACK)
{
// sib
setColor(rightOf(sib), BLACK);
// sib
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
// sib x
setColor(sib, colorOf(parentOf(x)));
// x
setColor(parentOf(x), BLACK);
// sib
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
//
private boolean colorOf(Node p)
{
return (p == null ? BLACK : p.color);
}
//
private Node parentOf(Node p)
{
return (p == null ? null: p.parent);
}
//
private void setColor(Node p, boolean c)
{
if (p != null)
{
p.color = c;
}
}
//
private Node leftOf(Node p)
{
return (p == null) ? null: p.left;
}
//
private Node rightOf(Node p)
{
return (p == null) ? null: p.right;
}
/**
*
* p r
* r p
* q q
*/
private void rotateLeft(Node p)
{
if (p != null)
{
// p
Node r = p.right;
Node q = r.left;
// r p
p.right = q;
// r parent p
if (q != null)
{
q.parent = p;
}
r.parent = p.parent;
// p
if (p.parent == null)
{
root = r;
}
// p
else if (p.parent.left == p)
{
// r p
p.parent.left = r;
}
else
{
// r p
p.parent.right = r;
}
r.left = p;
p.parent = r;
}
}
/**
*
* p l
* l p
* q q
*/
private void rotateRight(Node p)
{
if (p != null)
{
// p
Node l = p.left;
Node q = l.right;
// l p
p.left = q;
// l parent p
if (q != null)
{
q.parent = p;
}
l.parent = p.parent;
// p
if (p.parent == null)
{
root = l;
}
// p
else if (p.parent.right == p)
{
// l p
p.parent.right = l;
}
else
{
// l p
p.parent.left = l;
}
l.right = p;
p.parent = l;
}
}
//
public List<Node> inIterator()
{
return inIterator(root);
}
private List<Node> inIterator(Node node)
{
List<Node> list = new ArrayList<Node>();
//
if (node.left != null)
{
list.addAll(inIterator(node.left));
}
//
list.add(node);
//
if (node.right != null)
{
list.addAll(inIterator(node.right));
}
return list;
}
public static void main(String[] args)
{
RedBlackTree<Integer> tree
= new RedBlackTree<Integer>();
//
tree.add(5);
tree.add(20);
tree.add(10);
tree.add(3);
tree.add(8);
tree.add(15);
tree.add(30);
System.out.println(tree.breadthFirst());
//
tree.remove(20);
System.out.println(tree.breadthFirst());
// System.out.println(tree.inIterator());
}
}