引子

上一篇文章结束的时候，我亲手立下了flag，要手写2-3树。经过卧薪尝胆半个月后，终于放弃了。因为2-3树只是B树的某个状态，写了半天就写某个类的一个状态貌似很没有什么可吹嘘的。为了能够在一群老不要脸的80年程序员中吹吹牛，所以花了好几天的时间，写了一棵B树出来。现在终于可以放心的说：我心里还是有点B树的。

B树

B树的全名 是Balance Tree

特点

1. 每个节点可用拥有超过2个元素
2. 每个节点可以拥有超过2个子节点
3. 依然有二叉搜索树的性质
4. 平衡。每个节点的所有子树高度都是一致的。
5. 高度不会特别高

性质

1. m阶B树，是说一个节点最多拥有m个子节点，也就是拥有m-1个元素
2. 根节点的元素个数x必须满足 x >= 1 && x <= m - 1
3. 非根节点的元素个数x必须满足 x<= m - 1 && x >= [m/2] -1 [m/2]表示向上取整
   非根节点的子子节点个数y为 y>=[m/2] && y <= m

操作

业余时间真的不多，所以我只写了添加与删除的逻辑。

添加

新添加的元素必然添加到叶子节点

上溢

1 上溢节点中元素个数必须是m
2 求得中间位置k
3 将k位元素移动到父节点中k'
4 将k左右的节点分别作为k'的左右节点
5 如果k'所在的节点仍然上溢，则仍然需要做相同的处理

看图

假设我们当前的树的m值为3，也就是说当前树是2-3树，添加节点过程如下图所示

添加节点.jpg

删除

1. 如果删除的元素是叶子节点元素，则直接删除
2. 如果删除的元素是中间节点元素，则需要找到前驱节点的最大值，或者后稷节点的最小值。将最大值或最小值覆盖当前节点，然后把最大值最小值删除掉（所以，真正的删除都是发生在叶子节点上）

下溢

节点中元素个数小于[m/2]-1时，是下溢状态（元素个数必然是[m/2]-2，特殊的对于root节点来说，下溢状态是元素个数为0
下溢的处理过程分两种情况

借元素

可以从兄弟节点中借到元素时，步骤如下：
1.找到临近的兄弟节点中元素个数是>=[m/2]（左或右选兄弟节点一个即可），注意从左兄弟中借的是最大的元素，从右兄弟中借的是最小的元素。
2.将父节点元素放入当前节点，把借到的元素放到父元素中的位置。
3.如果是从左兄弟节点借到的元素，此元素有右子节点，则把此右子节点放到当前节点的子节点中第一的位置。
4.如果是从右兄弟节点借到的元素，此元素右左子节点，则把此左子节点放到当前节点的子节点中最后的位置

合并节点

当兄弟节点都无法借给当前节点元素的时候，选择将 左兄弟节点 与 父节点中的元素，以及当前节点合并为一个新节点，放到当前的位置

Talk is cheap

代码还没写注释，后面补吧

Tree类

public class Tree<T extends Comparable> {

    private int degree;

    private Node<T> root;

    public Tree(int degree){
        this.degree = degree;
    }


    public void add(T value){
        if(this.root == null){
            List<T> elementList = new ArrayList<>();
            elementList.add(value);
            this.root = new Node<>(this.degree, elementList);
            this.root.setRoot(true);
        }else{
            Fission<T> fission = this.innerAdd(this.root, value);
            if(fission != null){
                List<T> elementList = new ArrayList<>();
                elementList.add(fission.getValue());
                this.root = new Node<T>(this.degree, elementList);
                List<Node<T>> subNodeList = new ArrayList<>();
                subNodeList.add(fission.getLeftPart());
                subNodeList.add(fission.getRightPart());
                this.root.setSubNodeList(subNodeList);
                this.root.setRoot(true);
            }
        }
    }

    private Fission<T> innerAdd(Node<T> node, T value) {

        if(node.isLeaf()){
            node.insertElement(value);
            if(node.overflow()){
                return node.fission();
            }else{
                return null;
            }
        }else{
            int index = node.bisect(value);
            Node<T> subNode = node.getSubNodeList().get(index);
            Fission<T> fission = this.innerAdd(subNode, value);
            if(fission != null){
                node.merge(fission);
                if(node.overflow()){
                    return node.fission();
                }else{
                    return null;
                }
            }

            return null;
        }
    }

    public void remove(T value){
        if(this.root != null){
            this.innerRemove(this.root, value);
            if(this.root.underflow()){
                this.underflowRoot();
            }
        }
    }

    private void innerRemove(Node<T> node, T value){
        if(node.hasElement(value)){
            if(node.isLeaf()){
                node.removeElement(value);
            }else{
                int index = node.bisect(value);
                T deletedValue = this.deleteLeftLargest(node.getSubNodeList().get(index));
                node.replaceElement(index, deletedValue);
                this.underflowSubTree(node, node.getSubNodeList().get(index), index);
            }
        }else{
            if(node.isLeaf() == false){
                int index = node.bisect(value);
                Node<T> subNode = node.getSubNodeList().get(index);
                this.innerRemove(subNode, value);
                if(subNode.underflow()){
                    this.underflow(node, subNode, index);
                }
            }
        }
    }

    private boolean underflowSubTree(Node<T> parentNode, Node<T> node, int inParentIndex){
        boolean underflow = false;
       if(node.isLeaf()){
           if(node.underflow()){
               this.underflow(parentNode, node, inParentIndex);
               underflow = true;
           }
       }else{
           int subIndex = node.getSubNodeList().size() - 1;
           underflow = this.underflowSubTree(node, node.getSubNodeList().get(subIndex), subIndex);
           if(underflow && node.underflow()){
               this.underflow(parentNode, node, inParentIndex);
               underflow = true;
           }
       }
       return underflow;
    }

    private T deleteLeftLargest(Node<T> node){
        T leftLargest = null;
        if(node.isLeaf()){
            leftLargest = node.removeLastElement();
        }else{
            Node<T> lastNode = node.getSubNodeList().get(node.getSubNodeList().size() - 1);
            leftLargest = this.deleteLeftLargest(lastNode);
        }
        return leftLargest;
    }


    private void underflowRoot(){
        Node<T> newRoot = new Node<T>(this.degree);
        for(Node<T> subNode : this.root.getSubNodeList()){
            newRoot.appendElement(subNode.getElementList());
            newRoot.appendSubNodeList(subNode.getSubNodeList());
        }
        newRoot.setRoot(true);
        this.root = newRoot;
    }

    private void underflow(Node<T> parentNode, Node<T> node, int inParentIndex){

        Node<T> leftBro = null;
        Node<T> rightBro = null;

        if(inParentIndex > 0){
            leftBro = parentNode.getSubNodeList().get(inParentIndex - 1);
        }

        if(inParentIndex < parentNode.getSubNodeList().size() - 1){
            rightBro = parentNode.getSubNodeList().get(inParentIndex + 1);
        }

        if(leftBro != null && leftBro.isRich()){
            T lastElement = leftBro.removeLastElement();
            T fromParent = parentNode.replaceElement(inParentIndex - 1, lastElement);
            node.insertElement(fromParent);
            if(leftBro.isLeaf() == false){
                Node<T> leftBroLastNode = leftBro.removeLastSubNode();
                node.insertSubNode(0, leftBroLastNode);
            }
        }else if(rightBro != null && rightBro.isRich()){
            T firstElemnt = rightBro.removeFirstElement();
            T fromParent = parentNode.replaceElement(inParentIndex, firstElemnt);
            node.insertElement(fromParent);
            if(rightBro.isLeaf() == false){
                Node<T> rightBroFirstNode = rightBro.removeFirstSubNode();
                node.insertSubNode(node.getSubNodeList().size(), rightBroFirstNode);
            }
        }else{
            if(leftBro != null){
                T parentValue = parentNode.removeElement(inParentIndex - 1);

                List<T> moreElementList = new ArrayList<>();
                moreElementList.add(parentValue);
                moreElementList.addAll(node.getElementList());
                leftBro.appendElement(moreElementList);
                parentNode.removeSubNode(inParentIndex);
                if(node.isLeaf() == false){
                    leftBro.appendSubNodeList(node.getSubNodeList());
                }
            }else if(rightBro != null){
                T parentValue = parentNode.removeElement(inParentIndex);
                List<T> moreElementList = new ArrayList<>();
                moreElementList.add(parentValue);
                moreElementList.addAll(rightBro.getElementList());
                node.appendElement(moreElementList);
                parentNode.removeSubNode(inParentIndex + 1);
                if(node.isLeaf() == false){
                    node.appendSubNodeList(rightBro.getSubNodeList());
                }
            }else{
                throw new IllegalStateException();
            }
        }
    }
}

Node类

public class Node <T extends Comparable>{

    private int maxElementNum;

    private int minElementNum;

    private List<T> elementList;

    private List<Node<T>> subNodeList;

    private boolean root;

    public Node(int degree){
        this(degree, null);
    }

    public Node(int degree, List<T> elements){
        this.maxElementNum = degree - 1;
        this.minElementNum = new BigDecimal(degree).divide(new BigDecimal(2), RoundingMode.CEILING).intValue() - 1;
        this.elementList = elements;
        this.subNodeList = new ArrayList<>();
        this.root = false;
    }

    public boolean isRoot() {
        return root;
    }

    public void setRoot(boolean root) {
        this.root = root;
    }

    public void setSubNodeList(List<Node<T>> subNodeList){
        this.subNodeList.clear();
        this.subNodeList.addAll(subNodeList);
    }


    public List<T> getElementList(){
        return this.elementList;
    }


    public List<Node<T>> getSubNodeList(){
        return this.subNodeList;
    }

    public boolean isLeaf(){
        return this.subNodeList.isEmpty();
    }

    public boolean isRich(){
        return this.elementList.size() > this.minElementNum;
    }

    public void insertElement(T value) {
        int index = this.bisect(value);
        this.insertElement(index, value);
    }

    public void insertElement(int index, T value){
        this.elementList.add(index, value);
    }

    public boolean overflow(){
        return this.elementList.size() > this.maxElementNum;
    }

    public boolean underflow(){
        return this.root ? this.elementList.size() < 1 : this.elementList.size() < this.minElementNum;
    }

    public Fission fission(){
        int mid = (this.elementList.size() - 1 ) / 2;
        T value = this.elementList.get(mid);
        List<T> leftElementList = new ArrayList<>();
        leftElementList.addAll(this.elementList.subList(0, mid));
        Node<T> leftPart = new Node<T>(this.maxElementNum + 1, leftElementList);
        List<T> rightElementList = new ArrayList<>();
        rightElementList.addAll(this.elementList.subList(mid + 1, this.elementList.size()));
        Node<T> rightPart = new Node<T>(this.maxElementNum + 1, rightElementList);
        if(this.isLeaf() == false){
            leftPart.setSubNodeList(this.subNodeList.subList(0, mid + 1));
            rightPart.setSubNodeList(this.subNodeList.subList(mid + 1, this.subNodeList.size()));
        }
        return new Fission(value, leftPart, rightPart);
    }

    public void merge(Fission<T> fission) {
        int index = this.bisect(fission.getValue());
        this.elementList.add(index, fission.getValue());
        this.subNodeList.set(index, fission.getLeftPart());
        this.subNodeList.add(index + 1, fission.getRightPart());
    }

    public int bisect(T value){

        if(this.elementList.isEmpty()){
            return 0;
        }

        int left = 0;
        int right = this.elementList.size() - 1;

        while(left < right){
            int mid = left + (right - left)/2;
            T midValue = this.elementList.get(mid);
            if(midValue.compareTo(value) >= 0){
                right = mid;
            }else{
                left = mid + 1;
            }
        }

        if(this.elementList.get(left).compareTo(value) >= 0){
            return left;
        }else if(this.elementList.get(right).compareTo(value) >= 0){
            return right;
        }else{
            return this.elementList.size();
        }
    }

    public boolean hasElement(T value) {
        return this.elementList.contains(value);
    }

    public void removeElement(T value){
        this.elementList.remove(value);
    }

    public T removeLastElement() {
        return this.elementList.remove(this.elementList.size() - 1);
    }

    public T removeElement(int index){
        return this.elementList.remove(index);
    }

    public T replaceElement(int index, T replaceValue){
        return this.elementList.set(index, replaceValue);
    }

    public Node<T> removeLastSubNode() {
        return this.subNodeList.remove(this.subNodeList.size() - 1);
    }

    public void insertSubNode(int index, Node<T> newNode) {
        this.subNodeList.add(index, newNode);
    }

    public T removeFirstElement() {
        return this.elementList.remove(0);
    }

    public Node<T> removeFirstSubNode() {
        return this.subNodeList.remove(0);
    }


    public void appendElement(List<T> moreElementList){
        this.elementList.addAll(moreElementList);
    }


    public void appendSubNodeList(List<Node<T>> moreNodeList){
        this.subNodeList.addAll(moreNodeList);
    }

    public Node<T> removeSubNode(int index) {
        return this.subNodeList.remove(index);
    }
}

Fission类

这个类上溢的时候存储分裂结果

public class Fission<T extends Comparable> {


    private T value;

    private Node<T> leftPart;

    private Node<T> rightPart;

    public Fission(T value, Node<T> leftPart, Node<T> rightPart) {
        this.value = value;
        this.leftPart = leftPart;
        this.rightPart = rightPart;
    }

    public T getValue() {
        return value;
    }

    public Node<T> getLeftPart() {
        return leftPart;
    }

    public Node<T> getRightPart() {
        return rightPart;
    }
}

预告

接下来我想写红黑树或者B+树