Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
TwoThreeTree
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* 2-3树实现/仅供学习使用
*
* @author yangtianrui
*/
public class TwoThreeTree {
public static void main(String[] args) {
TwoThreeTree tree = new TwoThreeTree();
tree.put(1);
tree.put(2);
tree.put(3);
tree.put(4);
tree.put(5);
tree.put(6);
tree.put(7);
tree.put(8);
tree.put(9);
}
/**
* 2-3树节点,这里把2-节点和3-节点都放在一起了
*/
private static class Node {
private Node parent = null;
// 该节点保存的数据
private final List<Integer> keys = new ArrayList<>();
// 子节点
private final List<Node> children = new ArrayList<>();
/**
* 向节点中插入元素,2-3树无法向下增长,需要在当前节点插入后向上分裂
*
* @param num
*/
public void insert(int num) {
keys.add(num);
Collections.sort(keys);
}
public boolean isLeaf() {
return children.isEmpty();
}
/**
* 需要分裂
*
* @return true/false
*/
public boolean needSplit() {
return keys.size() > 2;
}
@Override
public String toString() {
return "Node{" +
"keys=" + keys +
'}';
}
}
private Node mRoot;
public TwoThreeTree() {
}
/**
* 向2-3树中插入节点
*
* @param key key
* @return true 成功 false 失败
*/
public boolean put(int key) {
if (mRoot == null) {
mRoot = new Node();
mRoot.insert(key);
return true;
}
final Node insertNode = findInsertNode(mRoot, key);
if (insertNode == null) {
return false;
}
insertNode.insert(key);
if (insertNode.needSplit()) {
split(insertNode);
}
return true;
}
/**
* 当前节点向上分裂,2-3树保持平衡的核心
*
* @param pivot 需要分裂的节点
*/
private void split(Node pivot) {
if (pivot == null) {
return;
}
Node parent = pivot.parent;
// 中间键
int middle = pivot.keys.get(1);
// 新分裂的节点
Node n2 = new Node();
// 开始分裂
if (pivot.isLeaf()) {
/*
此时是叶子节点分裂,初始分裂状态一定是根节点
*/
// n2 获取右键
n2.keys.add(pivot.keys.get(2));
// 原节点删除右键和中键
pivot.keys.remove(2);
pivot.keys.remove(1);
} else {
/*
此时是中间节点分裂,这个状态一般是叶子节点分裂完后出现的。
*/
// n2 获取后两个键,注意添加顺序
n2.children.add(pivot.children.get(2));
n2.children.add(pivot.children.get(3));
// 删除两个孩子
pivot.children.remove(3);
pivot.children.remove(2);
n2.keys.add(pivot.keys.get(2));
n2.children.get(0).parent = n2;
n2.children.get(1).parent = n2;
// 原节点删除右键和中键
pivot.keys.remove(2);
pivot.keys.remove(1);
}
// 分裂根节点
if (parent == null) {
mRoot = new Node();
mRoot.parent = null;
mRoot.children.add(pivot);
mRoot.children.add(n2);
// root 节点取中间键
mRoot.keys.add(middle);
pivot.parent = mRoot;
n2.parent = mRoot;
} else {
// 把当前分类的n2插入到父节点的孩子节点中
int indexInParent = pivot.parent.children.indexOf(pivot);
pivot.parent.children.add(indexInParent + 1, n2);
pivot.parent.insert(middle);
n2.parent = parent;
if (parent.needSplit()) {
split(parent);
}
}
}
/**
* 根据当前key查找到应该插入的位置
*
* @param start 初始节点
* @param key key
* @return null key已经存在/Node 可以在此插入
*/
private Node findInsertNode(Node start, int key) {
if (mRoot == null) {
return null;
}
if (start.keys.contains(key)) {
return null;
}
if (start.isLeaf()) {
return start;
}
int keyCount = start.keys.size();
if (key < start.keys.get(0)) {
// 查找左节点
return findInsertNode(start.children.get(0), key);
} else if (key > start.keys.get(keyCount - 1)) {
// 查找右节点
// 根据2-3树的定义,右节点一定是keyCount
return findInsertNode(start.children.get(keyCount), key);
} else {
// 查找中间节点
// 这个时候1代表的是2-3树的中间节点
return findInsertNode(start.children.get(1), key);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.