자바 구현 B 트 리
32196 단어 학습 과 실천
package tree;
public class BTree {
public static final int M = 3;
@SuppressWarnings("unused")
private static final int NODES_MIN_LENGTH = M % 2 == 0 ? M / 2 - 1 : M / 2;
protected BTree parent;
protected int count;
protected Node[] nodes = new Node[M + 1];
public static class Node {
public int key = Integer.MAX_VALUE;
public BTree child;
public Node(int key, BTree child) {
super();
this.key = key;
this.child = child;
}
public Node() {
super();
}
}
public static BTree initBTree() {
BTree btree = new BTree();
for (int i = 0; i < btree.nodes.length; i++) {
btree.nodes[i] = new Node();
}
return btree;
}
public static class Result {
public BTree node;
public boolean find;
public int position;
public Result(BTree node, boolean find, int position) {
super();
this.node = node;
this.find = find;
this.position = position;
}
public Result() {
super();
}
}
public static Result nodeSearch(BTree node, int key) {
Result result = new Result();
result.node = node;
int high = node.count;
int low = 1;
int mid = (low + high) / 2;
while (true) {
if (node.nodes[mid].key == key) {
result.find = true;
result.position = mid;
return result;
}
if (node.nodes[mid].key > key) {
high = mid;
mid = (low + high) / 2;
} else {
low = mid;
mid = (low + high) / 2;
}
if (mid == low) {
if (node.nodes[mid].key == key) {
result.find = true;
result.position = mid;
return result;
}
if (low == high) {
if (node.nodes[mid].key < key) {
result.find = false;
result.position = mid;
return result;
} else {
result.find = false;
result.position = mid - 1;
return result;
}
}
if (node.nodes[mid + 1].key == key) {
result.find = true;
result.position = mid + 1;
return result;
}
if (node.nodes[mid].key < key && node.nodes[mid + 1].key > key) {
result.find = false;
result.position = mid;
return result;
}
if (node.nodes[mid + 1].key < key) {
result.find = false;
result.position = mid + 1;
return result;
}
if (key < node.nodes[mid].key) {
result.find = false;
result.position = mid - 1;
return result;
}
}
}
}
public static Result search(BTree root, int key) {
if (root.count == 0) {
return new Result(root, false, 0);
}
BTree node = root;
Result result;
while (true) {
result = nodeSearch(node, key);
if (result.find)
break;
else {
if (result.node.nodes[result.position].child != null) {
node = result.node.nodes[result.position].child;
} else
break;
}
}
return result;
}
public static int insertBTreeNode(Result result, int key) {
for (int i = result.node.count; i > result.position; i--)
result.node.nodes[i + 1] = result.node.nodes[i];
result.node.nodes[result.position + 1] = new Node(key, null);
result.node.count++;
return result.node.count == M ? 0 : 1;
}
public static BTree insertBtree(BTree root, int key) {
Result result = search(root, key);
if (!result.find && insertBTreeNode(result, key) == 0) {
BTree tempRoot = split(result.node);
if (tempRoot != null)
root = tempRoot;
}
return root;
}
private static BTree split(BTree node) {
BTree root = null;
while (node.count == M) {
BTree leftNode = initBTree();
BTree rightNode = initBTree();
leftNode.parent = rightNode.parent = node.parent;
int leftEnd = NODES_MIN_LENGTH;
int middle = leftEnd + 1;
int rightBegin = leftEnd + 2;
leftNode.count = leftEnd;
rightNode.count = M - rightBegin + 1;
for (int i = 0; i <= leftEnd; i++) {
leftNode.nodes[i] = node.nodes[i];
if (node.nodes[i].child != null)
node.nodes[i].child.parent = leftNode;
}
for (int i = rightBegin; i <= M; i++) {
rightNode.nodes[i - rightBegin + 1] = node.nodes[i];
if (node.nodes[i].child != null)
node.nodes[i].child.parent = rightNode;
}
Node middleNode = node.nodes[middle];
if (middleNode.child != null) {
rightNode.nodes[0].child = middleNode.child;
rightNode.nodes[0].child.parent = rightNode;
}
middleNode.child = rightNode;
BTree parent = node.parent;
if (parent != null) {
int i = parent.count;
while (parent.nodes[i].key > middleNode.key) {
parent.nodes[i + 1] = parent.nodes[i];
if (--i == 0)
break;
}
parent.nodes[i].child = leftNode;
parent.nodes[i + 1] = middleNode;
parent.nodes[i + 1].child = rightNode;
parent.count++;
leftNode.parent = parent;
rightNode.parent = parent;
node = parent;
} else {
root = initBTree();
root.count = 1;
root.nodes[0].child = leftNode;
root.nodes[1].key = middleNode.key;
root.nodes[1].child = rightNode;
leftNode.parent = root;
rightNode.parent = root;
break;
}
}
return root;
}
private static void deleteInTreeNode(BTree treeNode, int position) {
for (int i = position; i < treeNode.count; i++)
treeNode.nodes[i] = treeNode.nodes[i + 1];
treeNode.count--;
}
public static void traverseBTree(BTree root) {
if (root.nodes[0].child == null) {
for (int i = 1; i <= root.count; i++)
System.out.print(root.nodes[i].key + "***");
} else {
traverseBTree(root.nodes[0].child);
for (int i = 1; i <= root.count; i++) {
System.out.print(root.nodes[i].key + "***");
traverseBTree(root.nodes[i].child);
}
}
}
public static BTree delete(BTree root, int key) {
System.out.println(key);
Result result = search(root, key);
if (result.find) {
Node node = result.node.nodes[result.position];
BTree treeNode = node.child;
if (treeNode != null) {
while (treeNode.nodes[0].child != null)
treeNode = treeNode.nodes[0].child;
result.node.nodes[result.position].key = treeNode.nodes[1].key;
deleteInTreeNode(treeNode, 1);
} else {
treeNode = result.node;
deleteInTreeNode(treeNode, result.position);
}
if (treeNode.count < NODES_MIN_LENGTH && treeNode.parent != null) {
while (treeNode.count < NODES_MIN_LENGTH) {
BTree brother;
// CTN currentTreeNode
boolean CTNIsLast = false;
int CTNInParentIndex = 0;
for (int i = 0; i <= treeNode.parent.count; i++)
if (treeNode.parent.nodes[i].child.equals(treeNode)) {
CTNInParentIndex = i;
break;
}
if (CTNInParentIndex == treeNode.parent.count) {
CTNIsLast = true;
brother = treeNode.parent.nodes[CTNInParentIndex - 1].child;
} else {
brother = treeNode.parent.nodes[CTNInParentIndex + 1].child;
}
if (!CTNIsLast) {
treeNode.nodes[++treeNode.count].key = treeNode.parent.nodes[CTNInParentIndex + 1].key;
treeNode.nodes[treeNode.count].child = brother.nodes[0].child;
if (treeNode.nodes[treeNode.count].child != null)
treeNode.nodes[treeNode.count].child.parent = treeNode;
if (brother.count > NODES_MIN_LENGTH) {
treeNode.parent.nodes[CTNInParentIndex + 1].key = brother.nodes[1].key;
deleteInTreeNode(brother, 0);
brother.nodes[0].key = Integer.MAX_VALUE;
} else {
if (brother.nodes[0].child != null) {
for (int i = 1; i <= brother.count; i++) {
treeNode.nodes[++treeNode.count] = brother.nodes[i];
treeNode.nodes[treeNode.count].child.parent = treeNode;
}
} else {
for (int i = 1; i <= brother.count; i++)
treeNode.nodes[++treeNode.count] = brother.nodes[i];
}
deleteInTreeNode(treeNode.parent, CTNInParentIndex + 1);
}
} else {
if (brother.count > NODES_MIN_LENGTH) {
for (int i = treeNode.count + 1; i >= 1; i--)
treeNode.nodes[i] = treeNode.nodes[i - 1];
treeNode.nodes[1].key = treeNode.parent.nodes[CTNInParentIndex].key;
treeNode.count++;
if (brother.nodes[brother.count].child != null) {
treeNode.nodes[0].child = brother.nodes[brother.count].child;
treeNode.nodes[0].child.parent = treeNode;
}
treeNode.parent.nodes[CTNInParentIndex].key = brother.nodes[brother.count].key;
deleteInTreeNode(brother, brother.count);
} else {
treeNode.nodes[0].key = treeNode.parent.nodes[CTNInParentIndex].key;
for (int i = treeNode.count; i >= 0; i--)
treeNode.nodes[i + 1 + brother.count] = treeNode.nodes[i];
treeNode.count += 1 + brother.count;
deleteInTreeNode(treeNode.parent, CTNInParentIndex);
treeNode.parent.nodes[CTNInParentIndex - 1].child = treeNode;
for (int i = 0; i <= brother.count; i++) {
treeNode.nodes[i] = brother.nodes[i];
if (treeNode.nodes[i].child != null)
treeNode.nodes[i].child.parent = treeNode;
}
}
}
if (treeNode.parent == null)
return treeNode;
if (treeNode.parent.count == 0 && treeNode.parent.parent == null) {
treeNode.parent = null;
return treeNode;
}
if (treeNode.parent.count < NODES_MIN_LENGTH)
treeNode = treeNode.parent;
}
}
}
return root;
}
}
좋은 웹페이지 즐겨찾기
