Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement