2-3 tree
19089 ワード
package com.leon.cc;
import com.leon.util.Stack;
/**
* @author : Leon
* @since : 2013-10-9
* @see :
*/
public class Tree {
Node root = new Node();
public void insert(String str) {
Node node = search_node(root, str);
node.insert(str);
while (need_split(node)) {
if (node == root) {
node = node.split();
root = node;
}
else {
node = node.split();
}
}
}
public void delete(String str) {
Node node = contain(str);
Node leaf = null;
if (!node.is_leaf()) {
leaf = tree_successor(node, str);
int index = node.index_item(str);
String temp = node.values[index];
node.values[index] = leaf.values[0];
leaf.values[0] = temp;
}
else {
leaf = node;
}
leaf.delete(str);
if (leaf.item_size == 0) {
fix(leaf);
}
}
private void fix(Node n) {
if (n.parent == null) {
root = n.disConnect(0);
}
else {
Node p = n.parent;
int[] ary = new int[3];
int index = p.index_child(n);
if (has_2item_sibling(n, ary)) {
if (p.item_size == 2) {
if (index == 0) {
if (ary[1] == 2) {
leftRotate(0, n);
}
else {
leftRotate(0, n);
leftRotate(1, n.parent.childs[1]);
}
}
else if (index == 1) {
if (ary[2] == 2) {
leftRotate(1, n);
}
else {
rightRotate(1, n);
}
}
else {
if (ary[1] == 2) {
rightRotate(2, n);
}
else {
rightRotate(2, n);
rightRotate(1, n.parent.childs[1]);
}
}
}
else {
if (index == 0) {
leftRotate(0, n);
}
else {
rightRotate(1, n);
}
}
}
else {
if (p.item_size == 2) {
if (index == 0) {
mergeRight(0, n);
}
else if (index == 1) {
mergeLeft(1, n);
}
else {
mergeLeft(2, n);
}
}
else {
if (index == 0) {
mergeRight(0, n);
}
else {
mergeLeft(1, n);
}
fix(p);
}
}
}
}
private void mergeLeft(int i, Node n) {
Node child = null;
Node p = n.parent;
if (!n.is_leaf()) {
child = n.childs[0];
n.delete_child(0);
}
p.delete_child(i);
if (i == 1) {
p.childs[0].insert(p.values[0]);
p.delete(p.values[0]);
if (child != null) {
p.childs[0].insert_child(2, child);
}
}
else {
int sibling_size = p.item_size;
p.childs[1].insert(p.values[sibling_size - 1]);
p.delete(p.values[sibling_size - 1]);
if (child != null) {
p.childs[1].insert_child(2, child);
}
}
}
private void mergeRight(int i, Node n) {
Node child = null;
Node p = n.parent;
if (!n.is_leaf()) {
child = n.childs[0];
n.delete_child(0);
}
p.delete_child(0);
p.childs[0].insert(p.values[0]);
p.delete(p.values[0]);
if (child != null) {
p.childs[0].insert_child(0, child);
}
}
private boolean has_2item_sibling(Node n, int[] ary) {
Node p = n.parent;
ary[0] = p.childs[0].item_size;
ary[1] = p.childs[1].item_size;
if (p.item_size == 2) {
ary[2] = p.childs[2].item_size;
}
for (int i = 0; i < ary.length; i++) {
if (ary[i] == 2) {
return true;
}
}
return false;
}
private void leftRotate(int index, Node n) {
if (index == 0) {
n.insert(n.parent.values[0]);
n.parent.delete(n.parent.values[0]);
n.parent.insert(n.parent.childs[1].values[0]);
n.parent.childs[1].delete(n.parent.childs[1].values[0]);
if (!n.is_leaf()) {
Node node = n.parent.childs[1].delete_child(0);
n.insert_child(1, node);
}
}
else {
n.insert(n.parent.values[1]);
n.parent.delete(n.parent.values[1]);
n.parent.insert(n.parent.childs[2].values[0]);
n.parent.childs[2].delete(n.parent.childs[2].values[0]);
if (!n.is_leaf()) {
Node node = n.parent.childs[2].delete_child(0);
n.insert_child(1, node);
}
}
}
private void rightRotate(int index, Node n) {
if (index == 2) {
n.insert(n.parent.values[1]);
n.parent.delete(n.parent.values[1]);
int sibling_size = n.parent.childs[1].item_size;
n.parent.insert(n.parent.childs[1].values[sibling_size - 1]);
n.parent.childs[1].delete(n.parent.childs[1].values[sibling_size - 1]);
if (!n.is_leaf()) {
Node node = n.parent.childs[1].delete_child(sibling_size);
n.insert_child(0, node);
}
}
else {
n.insert(n.parent.values[0]);
n.parent.delete(n.parent.values[0]);
int sibling_size = n.parent.childs[0].item_size;
n.parent.insert(n.parent.childs[0].values[sibling_size - 1]);
n.parent.childs[0].delete(n.parent.childs[0].values[sibling_size - 1]);
if (!n.is_leaf()) {
Node node = n.parent.childs[0].delete_child(sibling_size);
n.insert_child(0, node);
}
}
}
public Node tree_successor(Node node, String str) {
if (!node.is_leaf()) {
int index = node.index_item(str);
Node child = node.childs[index + 1];
return tree_mins(child);
}
return node;
}
private Node tree_mins(Node child) {
Node temp = child;
while (!temp.is_leaf()) {
temp = temp.childs[0];
}
return temp;
}
public Node contain(String str) {
Node current = root;
while (!current.contain(str)) {
if (current.item_size == 2) {
String small = current.values[0];
String large = current.values[1];
if (str.compareTo(small) < 0) {
current = current.childs[0];
}
else if (str.compareTo(small) >= 0 && str.compareTo(large) <= 0) {
current = current.childs[1];
}
else {
current = current.childs[2];
}
}
else {
String small = current.values[0];
if (str.compareTo(small) < 0) {
current = current.childs[0];
}
else {
current = current.childs[1];
}
}
}
return current;
}
public boolean need_split(Node node) {
return node.item_size > 2 ? true : false;
}
public Node search_node(Node node, String str) {
if (is_leaf(node)) {
return node;
}
else {
if (node.item_size == 2) {
String small = node.values[0];
String large = node.values[1];
if (str.compareTo(small) < 0) {
Node next = create_node(node, 0);
return search_node(next, str);
}
else if (str.compareTo(small) >= 0 && str.compareTo(large) <= 0) {
Node next = create_node(node, 1);
return search_node(next, str);
}
else {
Node next = create_node(node, 2);
return search_node(next, str);
}
}
else {
String small = node.values[0];
if (str.compareTo(small) < 0) {
Node next = create_node(node, 0);
return search_node(next, str);
}
else {
Node next = create_node(node, 1);
return search_node(next, str);
}
}
}
}
private Node create_node(Node node, int i) {
Node child = node.childs[i];
if (child == null) {
child = new Node();
node.childs[i] = child;
child.parent = node;
}
return child;
}
public boolean is_leaf(Node node) {
return node.childs[0] == null;
}
public static void main(String[] args) {
Tree t = new Tree();
String[] str = new String[] { "horse", "cow", "pig", "seal", "rat", "dog", "goat", "elephant", "fish",
"rooster", "zebra", "roach", "cat", "hen", "llama", "aardvark", "hog", "donkey", "rhino", "hippo",
"tiger", "lamb", "lion", "leopard", "lynx", "kitty", "ant", "ape", "animal" };
for (int i = 0; i < str.length; i++) {
t.insert(str[i]);
}
t.delete("animal");
t.delete("aardvark");
t.delete("cat");
t.delete("ape");
t.delete("donkey");
t.delete("ant");
t.delete("hog");
t.delete("hen");
t.delete("fish");
t.delete("goat");
t.delete("hippo");
t.delete("kitty");
t.delete("cow");
t.delete("dog");
t.delete("elephant");
t.delete("tiger");
t.delete("zebra");
t.delete("horse");
t.delete("rat");
t.delete("rhino");
t.delete("pig");
t.delete("seal");
t.delete("lynx");
t.delete("roach");
t.delete("lion");
t.delete("llama");
t.delete("lamb");
t.delete("rooster");
t.delete("leopard");
String rs = t.toString();
System.out.println(rs);
}
public String toString() {
if (root == null) {
return null;
}
StringBuilder sb = new StringBuilder();
sb.append("digraph g {
");
sb.append("\tnode[shape = record, width = .1, height = .1];
");
Stack<Node> stack = new Stack<Node>();
int k = 0;
Stack<Integer> k_stack = new Stack<Integer>();
stack.push(root);
k_stack.push(k);
sb.append("\tnode" + k + "[label = \"{<n> " + root.getName() + " }\", color = lightgray, style = filled];
");
while (!stack.is_empty()) {
Node parent = stack.pop();
String parentNode = "node" + k_stack.pop();
for (int i = 0; i < parent.childs.length; i++) {
if (parent.childs[i] != null) {
String childNode = "node" + (++k);
sb.append("\t" + childNode + "[label = \"{<n> " + parent.childs[i].getName()
+ " }\", color = lightgray, style = filled];
");
sb.append("\t" + parentNode + ":n->" + childNode + ":n;
");
stack.push(parent.childs[i]);
k_stack.push(k);
}
}
}
sb.append("}
");
return sb.toString();
}
}
class Node {
String[] values = new String[3];
int item_size;
Node[] childs = new Node[4];
Node parent;
public Node(String str) {
values[0] = str;
item_size++;
}
public String getName() {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < item_size; i++) {
sb.append(values[i] + " ");
}
return sb.toString();
}
public Node() {
}
public boolean contain(String str) {
for (int i = 0; i < item_size; i++) {
if (values[i].equals(str)) {
return true;
}
}
return false;
}
public int insert(String str) {
int pos = item_size;
for (int i = item_size - 1; i >= 0; i--) {
if (values[i].compareTo(str) > 0) {
values[i + 1] = values[i];
pos = i;
}
}
values[pos] = str;
item_size++;
return pos;
}
public void delete(String str) {
int index = index_item(str);
for (int i = index; i < item_size; i++) {
values[i] = values[i + 1];
}
item_size--;
}
public void insert_child(int index, Node node) {
for (int i = childs.length - 2; i >= index; i--) {
childs[i + 1] = childs[i];
}
childs[index] = node;
childs[index].parent = this;
}
public Node delete_child(int index) {
Node node = childs[index];
for (int i = index; i < childs.length - 1; i++) {
childs[i] = childs[i + 1];
}
node.parent = null;
return node;
}
public boolean is_leaf() {
return childs[0] == null;
}
public int index_child(Node node) {
for (int i = 0; i < childs.length; i++) {
if (childs[i].equals(node)) {
return i;
}
}
return -1;
}
public int index_item(String str) {
for (int i = 0; i < item_size; i++) {
if (values[i].equals(str)) {
return i;
}
}
return -1;
}
public Node disConnect(int index) {
Node result = childs[index];
if (result != null) result.parent = null;
childs[index] = null;
return result;
}
public void connect(int index, Node child) {
childs[index] = child;
if (child != null) child.parent = this;
}
public Node split() {
Node left = this;
String middle = values[1];
Node right = new Node(values[2]);
left.values[1] = null;
left.values[2] = null;
left.item_size = 1;
if (parent == null) {
parent = new Node(middle);
parent.connect(0, left);
parent.connect(1, right);
}
else {
int index = parent.insert(middle);
parent.insert_child(index + 1, right);
}
if (!is_leaf()) {
Node child1 = disConnect(2);
Node child2 = disConnect(3);
right.connect(0, child1);
right.connect(1, child2);
}
return parent;
}
}