B树的 JAVA 实现

2020/04/30 11:09
阅读数 717

  因为感觉对 B 树的理解不是特别深刻,一直想手撸一个 B 树,这次终于得偿所愿,文末有完整的 B 树代码。

  代码比较长,大概六百行。

  B 树的代码使用了一百组数据进行 插入/删除 测试,结果正确。

  从生产讲,实现一棵 B 树不会有什么实际意义,但是这些代码和构建这些代码的思路,都将成为我们职业素养的一部分。

什么是B树

  在1970年,Bayer&McCreight发表的论文《ORGANIZATION AND MAINTENANCE OF LARGE ORDERED INDICES 》(大型有序索引的组织和维护)中提出了一种新的数据结构来维护大型索引,这种数据结构在论文中称为B-Tree。

  B 树是一种多路查找树,相比于二叉树来说,B 树更适合于建立存储设备中的文件索引。

  因为对于存储设备的操作,除算法的时间复杂度外,查找一个数据所需要进行 I/O 操作的次数也是性能的重要影响因素。

  对于传统的二叉树来说,其存储比较松散,树的深度较深,我们每次查找一个新节点,可能都需要进行一次 I/O 操作将其读入内存。

  而 B 树因为数据存储比较集中,一个节点内存储的数据更多,树的深度较浅,遍历整个 B 树所需 I/O 操作的次数远小于二叉树,同时因为我们的存储设备普遍适配了局部性原理,对于一个连续存储的节点来说,完全读取它所需 I/O 操作的次数也是非常少的。

  从算法时间复杂度上看,因为 B 树节点中的项都是有序存储的,我们在一个节点内寻找数据时,使用二分查找可以使时间复杂度落在 O(log2N) 内,与在二叉树中的查找相同。因此总的来看,B 树相比于二叉树更适用于在存储设备上维护文件索引。

  另外,B 树是平衡的,其维护平衡性的思路非常典型。对于普通的二叉树,是自上向下生长的,而对于B树,是自下而上生长的。

  我们的插入操作都只会将新项插入到叶子节点,叶子节点满后进行分裂,并将中间节点向上融合。整颗树高度的增加必然是由根节点的分裂带来的,而根节点的分裂不会破坏整颗树的平衡性,因为左右子树的高度均加一。

  对于一棵完全的二叉排序树,其根节点必然是整个有序链表的中点。这对于 B 树也是相通的,每次的分裂和向上融合都是向上传递了本节点的中点,所有元素组成的链表中,中间部分会集中在 B 树的上层节点中,这也保证了整棵树的平衡性。

  我们平时使用的红黑树就是 2-3树(B树的一种)的一个变种,通过为二叉树节点染色,模仿 2-3 树的节点合并/分裂等行为,为其在平衡性和性能上找到了一个妥协点。

B树的定义

  h:代表树的高度,k 是个自然数,一个B树要么是空的,要么满足以下条件:
  1.所有叶子节点到根节点的路径长度相同,即具有相同的高度;(树是平衡的)

  2.每个非叶子和根节点(即内部节点)至少有 k+1 个孩子节点,根至少有 2 个孩子;(这是关键的部分,因为节点都是分裂而来的,而每次分裂得到的节点至少有 k 个元素,也就有 k+1 个孩子;但根节点在分裂后可能只有一个元素,因为不需要向上融合,中间元素作为新的根节点,因此最少有两个孩子。而叶子节点没有孩子。)

  3.每个节点最多有 2k+1 个孩子节点。(规定了节点的最大容量)

  4.每个节点内的键都是递增的

  我们定义一个树的结构,首先定义其数据项及节点的数据结构:

/**
     * @Author Nxy
     * @Date 2020/2/23 14:06
     * @Description 内部类,B树中节点中的元素。K:键类型,V:值类型,可以是指向数据的索引,也可以是实体数据
     */
    private class Entry<K, V> {
        private K key;
        private V value;

        public void setKey(K key) {
            this.key = key;
        }

        public K getKey() {
            return this.key;
        }

        public void setValue(V value) {
            this.value = value;
        }

        public V getValue() {
            return this.value;
        }

        @Override
        public String toString() {
            return "key: " + this.key + " , ";
        }
    }

    /**
     * @Author Nxy
     * @Date 2020/2/23 14:12
     * @Description 内部类,封装搜索结果
     */
    private class SearchResult<V> {
        private boolean isExist;
        private V value;
        private int index;

        //构造方法,将查询结果封装入对象
        public SearchResult(boolean isExist, int index, V value) {
            this.isExist = isExist;
            this.index = index;
            this.value = value;
        }

        public boolean isExist() {
            return isExist;
        }

        public V getValue() {
            return value;
        }

        public int getIndex() {
            return index;
        }
    }

    /**
     * @Author Nxy
     * @Date 2020/2/23 14:28
     * @Description 树的节点
     */
    public class Node<K, V> {
        //节点内的项
        private List<Entry<K, V>> entrys;
        //节点的孩子节点们
        private List<Node<K, V>> sons;
        //是否是叶子节点
        private boolean isLeaf;
        //键值比较函数对象,如果采用倒序或者其它排序方式,传入该对象
        private Comparator<K> kComparator;

        //比较两个key,如果没有传入自定义排序方式则采用默认的升序
        private int compare(K key1, K key2) {
            return this.kComparator == null ? ((Comparable<K>) key2).compareTo(key1) : kComparator.compare(key1, key2);
        }

        //普通构造函数
        Node() {
            this.entrys = new LinkedList<Entry<K, V>>();
            this.sons = new LinkedList<Node<K, V>>();
            this.isLeaf = false;
        }

        //自定义K排序方式的构造函数
        Node(Comparator<K> kComparator) {
            this();
            this.kComparator = kComparator;
        }

        public void setIsLeaf(boolean isLeaf) {
            this.isLeaf = isLeaf;
        }

        public boolean getIsLeaf() {
            return this.isLeaf;
        }

        //返回本节点的项数
        public int nodeSize() {
            return this.entrys.size();
        }

        /**
         * @Author Nxy
         * @Date 2020/2/23 15:19
         * @Param key:待查找元素的key值
         * @Return 查找结果封装入 SearchResult
         * @Exception
         * @Description 在本节点内查找元素, 本质就是一个有序数组的二分查找
         */
        public SearchResult<V> search(K key) {
            int begin = 0;
            int end = this.nodeSize() - 1;
//            if (end == 0) {
//                return new SearchResult<V>(false, 0, null);
//            }
            int mid = (begin + end) / 2;
            boolean isExist = false;
            int index = 0;
            V value = null;
            //二分查找
            while (begin < end) {
                mid = (begin + end) / 2;
                Entry midEntry = this.entrys.get(mid);
                int compareRe = compare((K) midEntry.getKey(), key);
                //找到了
                if (compareRe == 0) {
                    break;
                } else {
                    if (compareRe > 0) {
                        //在中点右边
                        begin = mid + 1;
                    } else {
                        end = mid - 1;
                    }
                }
            }
            //二分查找结束,判断结果;三个元素以上才是正经二分,只有两个或一个元素属于边界条件要着重考虑
            if (begin < end) {
                //找到了
                isExist = true;
                index = mid;
                value = this.entrys.get(mid).getValue();
            } else if (begin == end) {
                K midKey = this.entrys.get(begin).getKey();
                int comRe = compare(midKey, key);
                if (comRe == 0) {
                    isExist = true;
                    index = begin;
                    value = this.entrys.get(mid).getValue();
                } else if (comRe > 0) {
                    isExist = false;
                    index = begin + 1;
                    value = null;
                } else {
                    isExist = false;
                    index = begin;
                    value = null;
                }
            } else {
                isExist = false;
                index = begin;
                value = null;
            }
            return new SearchResult<V>(isExist, index, value);
        }

        //删除给定索引位置的项
        public Entry<K, V> removeEntry(int index) {
            Entry<K, V> re = this.entrys.get(index);
            this.entrys.remove(index);
            return re;
        }

        //得到index处的项
        public Entry<K, V> entryAt(int index) {
            return this.entrys.get(index);
        }

        //将新项插入指定位置
        private void insertEntry(Entry<K, V> entry, int index) {
            this.entrys.add(index, entry);
        }

        //节点内插入项
        private boolean insertEntry(Entry<K, V> entry) {
            SearchResult<V> result = search(entry.getKey());
            if (result.isExist()) {
                return false;
            } else {
                insertEntry(entry, result.getIndex());
                return true;
            }
        }

        //更新项,如果项存在,更新其值并返回原值,否则直接插入
        public V putEntry(Entry<K, V> entry) {
            SearchResult<V> re = search(entry.getKey());
            if (re.isExist) {
                Entry oldEntry = this.entrys.get(re.getIndex());
                V oldValue = (V) oldEntry.getValue();
                oldEntry.setValue(entry.getValue());
                return oldValue;
            } else {
                insertEntry(entry);
                return null;
            }
        }

        //获得指定索引的子节点
        public Node childAt(int index) {
            return this.sons.get(index);
        }

        //删除给定索引的子节点
        public void removeChild(int index) {
            this.sons.remove(index);
        }

        //将新的子节点插入到指定位置
        public void insertChild(Node<K, V> child, int index) {
            this.sons.add(index, child);
        }
    }

  然后定义树的数据结构:

public class Btree{  
  //度数T,不传入则默认为 2-3 树
    private Integer DEFAULT_T = 2;
    //根节点
    private Node<K, V> root;

    private int t = DEFAULT_T;

    //非根节点的最小项数,体现的是除了根节点,其余节点都是分裂而来的!
    private int nodeMinSize = t - 1;
    //节点的最大项数
    private int nodeMaxSize = 2 * t - 1;
    //比较函数对象
    private Comparator<K> kComparator;
}

B树的操作

  对于一棵树常用的操作无非是增删改查,其余诸如旋转之类的调整树结构的操作封装在增删改查内部。我们看一下 B 树增删改查的逻辑。

  B树的查找

  查找是 B 树最简单的操作:

  1.在节点内进行二分查找,如果找到则返回。未找到返回其在节点内插入时的索引。

  2.根据索引递归的查找子节点,直到查找到叶子节点仍未找到则表明数据不在树中。

  实现如下:

//在以root为根的树内搜索key项
    private V search(Node<K, V> root, K key) {
        SearchResult<V> re = root.search(key);
        if (re.isExist) {
            return re.value;
        } else {
            //回归条件
            if (root.isLeaf) {
                return null;
            }
            int index = re.index;
            //递归搜索子节点
            return (V) search(root.childAt(index), key);
        }
    }

    public V search(K key) {
        return search(this.root, key);
    }

  B树的插入

  然后是B树的插入操作,插入操作需要考虑节点的分裂与向上融合,整个的过程如下:

  1. 首先判断根节点是否已满,满则先进行分裂得到新的根节点。

  2.从根节点向下寻找,找到待插入数据在叶子节点的位置。

  3. 向下寻找时,每经过一个节点,都检查插入位置子节点的大小是否为 2*t-1 ,因为我们插入节点可能造成下层节点的向上融合,上层节点如果大小为 2*t-1 ,融合新元素后将会有数据超过最大值的危险。

   寻找路径上,只要有节点的大小为 2*t-1 ,则先进行分裂,再继续向下查找。

  4. 直到查找到叶子节点,直接插入。(当然也有其它实现方式,比如每次插入后检查插入的节点是否需要分裂,沿着搜索路径回溯着向上融合)

  我们先将分裂和向上融合的放法定义出来:

/**
     * @Author Nxy
     * @Date 2020/2/23 20:49
     * @Param 分裂满子结点,fatherNode:待分裂节点的父节点,splitNode:待分裂节点,index:待分裂节点在父节点中的索引
     * @Return
     * @Exception
     * @Description 满子节点的分裂过程:从中间节点断开,后半部分形成新结点插入父节点。若分裂节点不是叶子节点,将子节点一并分裂到新节点
     */
    private void splitNode(Node<K, V> fatherNode, Node<K, V> splitNode, int index) {
        //分裂产生的新节点
        Node<K, V> newNode = new Node<K, V>(this.kComparator);
        //如果原节点为叶子节点,那么新节点也是
        newNode.setIsLeaf(splitNode.isLeaf);
        //将 t到2*t-2 项迁移到新节点
        for (int i = t; i < this.nodeMaxSize; i++) {
            newNode.entrys.add(splitNode.entrys.get(i));
        }
        //中间节点向上融合到父节点的 index+1
        Entry<K, V> midEntry = splitNode.entrys.get(t - 1);
        for (int i = this.nodeMaxSize - 1; i >= t - 1; i--) {
            //删除原节点中已迁移的项,删除时注意从尾部向前删除
            splitNode.entrys.remove(i);
        }
        //如果分裂的节点不是叶子节点,子节点一并跟随分裂
        if (!splitNode.getIsLeaf()) {
            for (int i = t; i < this.nodeMaxSize + 1; i++) {
                newNode.sons.add(splitNode.sons.get(i));
            }
            //删除时注意从尾部向前删除
            for (int i = this.nodeMaxSize; i >= t; i--) {
                splitNode.sons.remove(i);
            }
        }
        //父节点插入分裂的中间元素,分裂出的新节点加入父节点的 sons
        fatherNode.insertEntry(midEntry);
        fatherNode.insertChild(newNode, index + 1);
    }

  然后定义插入方法:

/**
     * @Author Nxy
     * @Date 2020/2/23 23:53
     * @Param root:当前节点,entry:待插入元素
     * @Return
     * @Exception
     * @Description 插入一个非满节点:一路向下寻找插入位置。
     * 在寻找的路径上,如果碰到大小为2t-1的节点,分裂并向上融合。
     * 每次插入都从叶子节点插入,通过分裂将插入动作向上反馈,直到融合到根节点,只有由根节点的分裂
     * 才能增加整棵树的高度,从而维持树的平衡。
     * 树在一开始就是平衡的(只有根),整棵树的高度增加必须由根节点的分裂引发,从而高度增加后还是平衡的
     * 因为没次检查子节点前如果子节点满了会先分裂,所以除根节点外,其余节点被其子节点向上融合均不会导致节点满
     * 仅插入一个元素的情况下,每个节点最多经历一次子节点的分裂
     */
    private boolean insertNotFull(Node<K, V> root, Entry<K, V> entry) {
        if (root.getIsLeaf()) {
            //到达叶子节点,直接插入
            return root.insertEntry(entry);
        }
        SearchResult<V> re = root.search(entry.getKey());
        if (re.isExist) {
            //已存在key,直接返回
            return false;
        }
        int index = re.getIndex();
        Node<K, V> searchChild = root.childAt(index);
        //待查询子节点已满,分裂后再判断该搜索哪个子节点
        if (searchChild.nodeSize() == 2 * t - 1) {
            splitNode(root, searchChild, index);
            if (root.compare(root.entryAt(index).getKey(), entry.getKey()) > 0) {
                searchChild = root.childAt(index + 1);
            }
        }
        return insertNotFull(searchChild, entry);
    }

    //插入一个新节点
    public boolean insertNode(Entry<K, V> entry) {
        //根节点满了,先分裂根节点
        if (root.nodeSize() == 2 * t - 1) {
            Node<K, V> newRoot = new Node<K, V>();
            newRoot.setIsLeaf(false);
            newRoot.insertChild(root, 0);
            splitNode(newRoot, root, 0);
            this.root = newRoot;
        }
        return insertNotFull(root, entry);
    }

  B树的删除

  删除比较麻烦,因为为了保证删除后树的结构依然符合定义,我们需要考虑非常多的情况。过程如下:

  在本节点内查找删除项,找到了

    如果本节点叶子节点,直接删除。

    如果不是叶子节点,则为了保证树结构,不可直接删除,继续判断:

       1.尝试与子节点互换元素以维护树的结构

      (首先是尝试将该数据项与子节点中的数据项互换)

        如果该数据项的左子节点有大于等于 t 个元素,则将左子节点最后一个元素与删除元素互换位置。

        左子节点元素个数少于 t ,检查右子节点,如果右子节点元素数大于等于 t ,将右子节点第一个元素与待删除元素互换位置。

         2. 尝试与左右子节点合并

       方案 1 没起作用,说明待删除元素的左右子节点元素个数都小于 t ,那么将其与待删除元素合并为一个大节点,长度将小于等于 2t-1 ,依然符合 B 树的定义。

       那么我们将待删除元素合并为左子节点最后一个元素,右子节点携带其子元素一并合并入左子节点中。递归的对合并后节点进行处理。

    在本节点内未找到待删除元素,去子节点继续寻找

     如果本节点为叶子节点,无子节点,直接返回待删除节点不在树中。

     否则判断子节点是否可删除元素,如果子节点元素个数大于等于 t :

       1.直接递归的处理子节点

     如果子节点元素个数小于 t ,不可删除项:

             2.尝试让子节点的左右兄弟节点旋转来匀出一个元素给子节点

     如果左兄弟可以匀出元素,左兄弟最后一个元素 - 本节点以子节点为右子节点的元素 - 子节点 进行右旋,同时将左兄弟最后一个元素的其右子树加到子节点儿子列表的开头。

     如果右兄弟可以匀出元素,右兄弟第一个元素 - 本节点以子节点为左子节点的元素-子节点 进行左旋,同时将右兄弟第一个子元素加到子节点儿子列表的结尾。

       3. 尝试合并子节点与其左/右兄弟节点

     如果子节点有左兄弟节点,本节点中将以子节点为右子节点的元素 - 子节点合并入子节点的左兄弟,子节点的孩子列表追加到左子元素孩子列表的结尾。

     如果子节点有右兄弟节点,本节点中以子节点为左子节点的元素 - 右兄弟节点合并入子节点,右兄弟节点的孩子列表追加到本节点孩子列表的结尾。

 

       以上便是删除的逻辑过程,看起来情况比较多,但并不复杂。核心便是在删除时,为了不破坏树的结构,我们必须将删除元素交换到叶子节点后才能删除。而在交换过程中,不能使删除路径上节点的元素数小于 t-1(包括叶子节点)。

       下面是实现:

private Entry<K, V> delete(Node<K, V> root, Entry<K, V> entry) {
        SearchResult<V> re = root.search(entry.getKey());
        if (re.isExist()) {
            //回归条件,如果是叶子节点中的元素,直接删除
            if (root.getIsLeaf()) {
                return root.removeEntry(re.getIndex());
            }
            //如果不是叶子节点,判断应将待删除节点交换到左子节点还是右子节点
            Node<K, V> leftChild = root.childAt(re.getIndex());
            //如果左子节点包含多于 t-1 个项,转移到左子节点删除
            if (leftChild.nodeSize() >= t) {
                //删除过程为,将待删除项与其左子节点最后一项互换,并递归互换下去,直到将待删除节点换到叶子节点后删除
                root.removeEntry(re.getIndex());
                root.insertEntry(leftChild.entryAt(leftChild.nodeSize() - 1), re.getIndex());
                leftChild.removeEntry(leftChild.nodeSize() - 1);
                leftChild.insertEntry(entry);
                return delete(leftChild, entry);
            }
            //左子节点不可删除项,则同样逻辑检查右子节点
            Node<K, V> rightChild = root.childAt(re.getIndex() + 1);
            if (rightChild.nodeSize() >= t) {
                root.removeEntry(re.getIndex());
                root.insertEntry(rightChild.entryAt(0), re.getIndex());
                rightChild.removeEntry(0);
                rightChild.insertEntry(entry);
                return delete(rightChild, entry);
            }
            //如果左右子节点均不能删除项,将左右子节点合并,并将删除项放到新节点的合并连接处
            Entry<K, V> deletedEntry = root.removeEntry(re.getIndex());
            leftChild.insertEntry(deletedEntry);
            root.removeChild(re.getIndex() + 1);
            //左右子节点合并
            for (int i = 0; i < rightChild.nodeSize(); i++) {
                leftChild.insertEntry(rightChild.entryAt(i));
            }
            //右子节点存在子节点,则子节点也合并入左子节点子节点集合
            if (!rightChild.getIsLeaf()) {
                for (int i = 0; i < rightChild.sons.size(); i++) {
                    leftChild.insertChild(rightChild.childAt(i), leftChild.sons.size());
                }
            }
            //合并后继续向左递归
            return delete(leftChild, entry);
        } else {//删除节点不在本节点
            //回归条件,搜索到叶节点依然没找到,待删除节点不在树中
            if (root.getIsLeaf()) {
                for (int i = 0; i < root.nodeSize(); i++) {
                    System.out.print("++++++++++++++++++++");
                    System.out.print(root.entryAt(i).getKey() + ",");
                    System.out.print("++++++++++++++++++++");
                }
                throw new RuntimeException(entry.key + " is not in this tree!");
            }
            Node<K, V> searchChild = root.childAt(re.index);
            //子节点可删除项,递归删除
            if (searchChild.nodeSize() >= t) {
                return delete(searchChild, entry);
            }
            //待旋转节点,子节点项数小于等于 t-1 ,不能删除项,准备左旋或右旋为其补充项数
            Node<K, V> siblingNode = null;
            int siblingIndex = -1;
            //存在右兄弟
            if (re.getIndex() < root.nodeSize() - 1) {
                Node<K, V> rightBrother = root.childAt(re.getIndex() + 1);
                if (rightBrother.nodeSize() >= t) {
                    siblingNode = rightBrother;
                    siblingIndex = re.getIndex() + 1;
                }
            }
            //不存在右兄弟则尝试左兄嘚
            if (siblingNode == null) {
                if (re.getIndex() > 0) {
                    //尝试左兄弟节点
                    Node<K, V> leftBrothr = root.childAt(re.getIndex() - 1);
                    if (leftBrothr.nodeSize() >= t) {
                        siblingNode = leftBrothr;
                        siblingIndex = re.getIndex() - 1;
                    }
                }
            }
            //至少有一个兄弟可以匀出项来
            if (siblingNode != null) {
                //是左兄嘚
                if (siblingIndex < re.getIndex()) {
                    //左节点最后一项右旋
                    searchChild.insertEntry(root.entryAt(siblingIndex), 0);
                    root.removeEntry(siblingIndex);
                    root.insertEntry(siblingNode.entryAt(siblingNode.nodeSize() - 1), siblingIndex);
                    siblingNode.removeEntry(siblingNode.nodeSize() - 1);
                    //子节点跟着右旋
                    if (!siblingNode.getIsLeaf()) {
                        searchChild.insertChild(siblingNode.childAt(siblingNode.sons.size() - 1), 0);
                        siblingNode.removeChild(siblingNode.sons.size() - 1);
                    }
                } else {
                    //是右兄嘚
                    searchChild.insertEntry(root.entryAt(re.getIndex()), searchChild.nodeSize() - 1);
                    root.removeEntry(re.getIndex());
                    root.insertEntry(siblingNode.entryAt(0), re.getIndex());
                    siblingNode.removeEntry(0);
                    if (!siblingNode.getIsLeaf()) {
                        searchChild.insertChild(siblingNode.childAt(0), searchChild.sons.size());
                        siblingNode.removeChild(0);
                    }
                }
                return delete(searchChild, entry);
            }
            //左右兄嘚都匀不出项来,直接由左右兄嘚节点与父项合并为一个节点
            if (re.getIndex() <= root.nodeSize() - 1) {
                Node<K, V> rightSon = root.childAt(re.getIndex() + 1);
                searchChild.insertEntry(root.entryAt(re.getIndex()), searchChild.nodeSize());
                root.removeEntry(re.getIndex());
                root.removeChild(re.getIndex() + 1);
                for (int i = 0; i < rightSon.nodeSize(); i++) {
                    searchChild.insertEntry(rightSon.entryAt(i));
                }
                if (!rightSon.getIsLeaf()) {
                    for (int j = 0; j < rightSon.sons.size(); j++) {
                        searchChild.insertChild(rightSon.childAt(j), searchChild.sons.size());
                    }
                }
                if (root == this.root) {
                    this.root = searchChild;
                }
            } else {
                //没有右兄弟,试试左兄嘚
                Node<K, V> leftSon = root.childAt(re.getIndex() - 1);
                searchChild.insertEntry(root.entryAt(re.getIndex() - 1), 0);
                root.removeChild(re.getIndex() - 1);
                root.removeEntry(re.getIndex() - 1);
                for (int i = 0; i < leftSon.nodeSize(); i++) {
                    searchChild.insertEntry(leftSon.entryAt(i));
                }
                if (!leftSon.getIsLeaf()) {
                    for (int i = leftSon.sons.size() - 1; i >= 0; i--) {
                        searchChild.insertChild(leftSon.childAt(i), 0);
                    }
                }
                if (root == this.root) {
                    this.root = searchChild;
                }
            }
//            if (root == this.root && root.nodeSize() == 0) {
//                root = searchChild;
//            }
            return delete(searchChild, entry);
        }
    }

  下面放 B 树实现的整体代码:

package BTree;

import java.util.*;

/**
 * @Author Nxy
 * @Date 2020/2/23 14:04
 * @Description B树实现
 */
public class BTree<K, V> {

    /**
     * @Author Nxy
     * @Date 2020/2/23 14:06
     * @Description 内部类,B树中节点中的元素。K:键类型,V:值类型,可以是指向数据的索引,也可以是实体数据
     */
    private class Entry<K, V> {
        private K key;
        private V value;

        public void setKey(K key) {
            this.key = key;
        }

        public K getKey() {
            return this.key;
        }

        public void setValue(V value) {
            this.value = value;
        }

        public V getValue() {
            return this.value;
        }

        @Override
        public String toString() {
            return "key: " + this.key + " , ";
        }
    }

    /**
     * @Author Nxy
     * @Date 2020/2/23 14:12
     * @Description 内部类,封装搜索结果
     */
    private class SearchResult<V> {
        private boolean isExist;
        private V value;
        private int index;

        //构造方法,将查询结果封装入对象
        public SearchResult(boolean isExist, int index, V value) {
            this.isExist = isExist;
            this.index = index;
            this.value = value;
        }

        public boolean isExist() {
            return isExist;
        }

        public V getValue() {
            return value;
        }

        public int getIndex() {
            return index;
        }
    }

    /**
     * @Author Nxy
     * @Date 2020/2/23 14:28
     * @Description 树的节点
     */
    public class Node<K, V> {
        //节点内的项
        private List<Entry<K, V>> entrys;
        //节点的孩子节点们
        private List<Node<K, V>> sons;
        //是否是叶子节点
        private boolean isLeaf;
        //键值比较函数对象,如果采用倒序或者其它排序方式,传入该对象
        private Comparator<K> kComparator;

        //比较两个key,如果没有传入自定义排序方式则采用默认的升序
        private int compare(K key1, K key2) {
            return this.kComparator == null ? ((Comparable<K>) key2).compareTo(key1) : kComparator.compare(key1, key2);
        }

        //普通构造函数
        Node() {
            this.entrys = new LinkedList<Entry<K, V>>();
            this.sons = new LinkedList<Node<K, V>>();
            this.isLeaf = false;
        }

        //自定义K排序方式的构造函数
        Node(Comparator<K> kComparator) {
            this();
            this.kComparator = kComparator;
        }

        public void setIsLeaf(boolean isLeaf) {
            this.isLeaf = isLeaf;
        }

        public boolean getIsLeaf() {
            return this.isLeaf;
        }

        //返回本节点的项数
        public int nodeSize() {
            return this.entrys.size();
        }

        /**
         * @Author Nxy
         * @Date 2020/2/23 15:19
         * @Param key:待查找元素的key值
         * @Return 查找结果封装入 SearchResult
         * @Exception
         * @Description 在本节点内查找元素, 本质就是一个有序数组的二分查找
         */
        public SearchResult<V> search(K key) {
            int begin = 0;
            int end = this.nodeSize() - 1;
//            if (end == 0) {
//                return new SearchResult<V>(false, 0, null);
//            }
            int mid = (begin + end) / 2;
            boolean isExist = false;
            int index = 0;
            V value = null;
            //二分查找
            while (begin < end) {
                mid = (begin + end) / 2;
                Entry midEntry = this.entrys.get(mid);
                int compareRe = compare((K) midEntry.getKey(), key);
                //找到了
                if (compareRe == 0) {
                    break;
                } else {
                    if (compareRe > 0) {
                        //在中点右边
                        begin = mid + 1;
                    } else {
                        end = mid - 1;
                    }
                }
            }
            //二分查找结束,判断结果;三个元素以上才是正经二分,只有两个或一个元素属于边界条件要着重考虑
            if (begin < end) {
                //找到了
                isExist = true;
                index = mid;
                value = this.entrys.get(mid).getValue();
            } else if (begin == end) {
                K midKey = this.entrys.get(begin).getKey();
                int comRe = compare(midKey, key);
                if (comRe == 0) {
                    isExist = true;
                    index = begin;
                    value = this.entrys.get(mid).getValue();
                } else if (comRe > 0) {
                    isExist = false;
                    index = begin + 1;
                    value = null;
                } else {
                    isExist = false;
                    index = begin;
                    value = null;
                }
            } else {
                isExist = false;
                index = begin;
                value = null;
            }
            return new SearchResult<V>(isExist, index, value);
        }

        //删除给定索引位置的项
        public Entry<K, V> removeEntry(int index) {
            Entry<K, V> re = this.entrys.get(index);
            this.entrys.remove(index);
            return re;
        }

        //得到index处的项
        public Entry<K, V> entryAt(int index) {
            return this.entrys.get(index);
        }

        //将新项插入指定位置
        private void insertEntry(Entry<K, V> entry, int index) {
            this.entrys.add(index, entry);
        }

        //节点内插入项
        private boolean insertEntry(Entry<K, V> entry) {
            SearchResult<V> result = search(entry.getKey());
            if (result.isExist()) {
                return false;
            } else {
                insertEntry(entry, result.getIndex());
                return true;
            }
        }

        //更新项,如果项存在,更新其值并返回原值,否则直接插入
        public V putEntry(Entry<K, V> entry) {
            SearchResult<V> re = search(entry.getKey());
            if (re.isExist) {
                Entry oldEntry = this.entrys.get(re.getIndex());
                V oldValue = (V) oldEntry.getValue();
                oldEntry.setValue(entry.getValue());
                return oldValue;
            } else {
                insertEntry(entry);
                return null;
            }
        }

        //获得指定索引的子节点
        public Node childAt(int index) {
            return this.sons.get(index);
        }

        //删除给定索引的子节点
        public void removeChild(int index) {
            this.sons.remove(index);
        }

        //将新的子节点插入到指定位置
        public void insertChild(Node<K, V> child, int index) {
            this.sons.add(index, child);
        }
    }

    //度数T,不传入则默认为 2-3 树
    private Integer DEFAULT_T = 2;
    //根节点
    private Node<K, V> root;

    private int t = DEFAULT_T;

    //非根节点的最小项数,体现的是除了根节点,其余节点都是分裂而来的!
    private int nodeMinSize = t - 1;
    //节点的最大项数
    private int nodeMaxSize = 2 * t - 1;
    //比较函数对象
    private Comparator<K> kComparator;

    //构造一棵自然排序的B树
    BTree() {
        Node<K, V> root = new Node<K, V>();
        this.root = root;
        root.setIsLeaf(true);
    }

    //构造一棵度为 t 的B树
    BTree(int t) {
        this();
        this.t = t;
        nodeMinSize = t - 1;
        nodeMaxSize = 2 * t - 1;
    }

    //构造一棵按给定排序方式排序,且度为 t 的B树
    BTree(Comparator<K> com, int t) {
        this(t);
        this.kComparator = com;
    }

    //在以root为根的树内搜索key项
    private V search(Node<K, V> root, K key) {
        SearchResult<V> re = root.search(key);
        if (re.isExist) {
            return re.value;
        } else {
            //回归条件
            if (root.isLeaf) {
                return null;
            }
            int index = re.index;
            //递归搜索子节点
            return (V) search(root.childAt(index), key);
        }
    }

    public V search(K key) {
        return search(this.root, key);
    }

    /**
     * @Author Nxy
     * @Date 2020/2/23 20:49
     * @Param 分裂满子结点,fatherNode:待分裂节点的父节点,splitNode:待分裂节点,index:待分裂节点在父节点中的索引
     * @Return
     * @Exception
     * @Description 满子节点的分裂过程:从中间节点断开,后半部分形成新结点插入父节点。若分裂节点不是叶子节点,将子节点一并分裂到新节点
     */
    private void splitNode(Node<K, V> fatherNode, Node<K, V> splitNode, int index) {
        //分裂产生的新节点
        Node<K, V> newNode = new Node<K, V>(this.kComparator);
        //如果原节点为叶子节点,那么新节点也是
        newNode.setIsLeaf(splitNode.isLeaf);
        //将 t到2*t-2 项迁移到新节点
        for (int i = t; i < this.nodeMaxSize; i++) {
            newNode.entrys.add(splitNode.entrys.get(i));
        }
        //中间节点向上融合到父节点的 index+1
        Entry<K, V> midEntry = splitNode.entrys.get(t - 1);
        for (int i = this.nodeMaxSize - 1; i >= t - 1; i--) {
            //删除原节点中已迁移的项,删除时注意从尾部向前删除
            splitNode.entrys.remove(i);
        }
        //如果分裂的节点不是叶子节点,子节点一并跟随分裂
        if (!splitNode.getIsLeaf()) {
            for (int i = t; i < this.nodeMaxSize + 1; i++) {
                newNode.sons.add(splitNode.sons.get(i));
            }
            //删除时注意从尾部向前删除
            for (int i = this.nodeMaxSize; i >= t; i--) {
                splitNode.sons.remove(i);
            }
        }
        //父节点插入分裂的中间元素,分裂出的新节点加入父节点的 sons
        fatherNode.insertEntry(midEntry);
        fatherNode.insertChild(newNode, index + 1);
    }

    /**
     * @Author Nxy
     * @Date 2020/2/23 23:53
     * @Param root:当前节点,entry:待插入元素
     * @Return
     * @Exception
     * @Description 插入一个非满节点:一路向下寻找插入位置。
     * 在寻找的路径上,如果碰到大小为2t-1的节点,分裂并向上融合。
     * 每次插入都从叶子节点插入,通过分裂将插入动作向上反馈,直到融合到根节点,只有由根节点的分裂
     * 才能增加整棵树的高度,从而维持树的平衡。
     * 树在一开始就是平衡的(只有根),整棵树的高度增加必须由根节点的分裂引发,从而高度增加后还是平衡的
     * 因为没次检查子节点前如果子节点满了会先分裂,所以除根节点外,其余节点被其子节点向上融合均不会导致节点满
     * 仅插入一个元素的情况下,每个节点最多经历一次子节点的分裂
     */
    private boolean insertNotFull(Node<K, V> root, Entry<K, V> entry) {
        if (root.getIsLeaf()) {
            //到达叶子节点,直接插入
            return root.insertEntry(entry);
        }
        SearchResult<V> re = root.search(entry.getKey());
        if (re.isExist) {
            //已存在key,直接返回
            return false;
        }
        int index = re.getIndex();
        Node<K, V> searchChild = root.childAt(index);
        //待查询子节点已满,分裂后再判断该搜索哪个子节点
        if (searchChild.nodeSize() == 2 * t - 1) {
            splitNode(root, searchChild, index);
            if (root.compare(root.entryAt(index).getKey(), entry.getKey()) > 0) {
                searchChild = root.childAt(index + 1);
            }
        }
        return insertNotFull(searchChild, entry);
    }

    //插入一个新节点
    public boolean insertNode(Entry<K, V> entry) {
        //根节点满了,先分裂根节点
        if (root.nodeSize() == 2 * t - 1) {
            Node<K, V> newRoot = new Node<K, V>();
            newRoot.setIsLeaf(false);
            newRoot.insertChild(root, 0);
            splitNode(newRoot, root, 0);
            this.root = newRoot;
        }
        return insertNotFull(root, entry);
    }

    /**
     * @Author Nxy
     * @Date 2020/2/24 14:00
     * @Param
     * @Return
     * @Exception
     * @Description 如果Key已存在,更新value,否则直接插入entry
     */
    private V putNotFull(Node<K, V> root, Entry<K, V> entry) {
        assert root.nodeSize() < nodeMaxSize;
        if (root.isLeaf) {
            return root.putEntry(entry);
        }
        SearchResult<V> re = root.search(entry.getKey());
        if (re.isExist) {
            //如果存在,则更新
            root.entryAt(re.index).setValue(entry.getValue());
            return re.value;
        }
        //如果不存在,继续向下搜素,先判断子节点是否需要分裂
        Node<K, V> searchChild = root.childAt(re.index);
        if (searchChild.nodeSize() == 2 * t - 1) {
            splitNode(root, searchChild, re.index);
            if (root.compare(entry.getKey(), root.entryAt(re.index).getKey()) > 0) {
                searchChild = root.childAt(re.index + 1);
            }
        }
        return putNotFull(searchChild, entry);
    }

    // 如果树中已存在 key 则更新并返回原 value,否则插入并返回null
    public V put(Entry<K, V> entry) {
        //如果根节点已满,先分裂根节点
        if (this.root.nodeSize() == nodeMaxSize) {
            Node<K, V> newRoot = new Node<K, V>(kComparator);
            newRoot.setIsLeaf(false);
            newRoot.insertChild(root, 0);
            splitNode(newRoot, root, 0);
            this.root = newRoot;
        }
        return putNotFull(root, entry);
    }

    private Entry<K, V> delete(Node<K, V> root, Entry<K, V> entry) {
        SearchResult<V> re = root.search(entry.getKey());
        if (re.isExist()) {
            //回归条件,如果是叶子节点中的元素,直接删除
            if (root.getIsLeaf()) {
                return root.removeEntry(re.getIndex());
            }
            //如果不是叶子节点,判断应将待删除节点交换到左子节点还是右子节点
            Node<K, V> leftChild = root.childAt(re.getIndex());
            //如果左子节点包含多于 t-1 个项,转移到左子节点删除
            if (leftChild.nodeSize() >= t) {
                //删除过程为,将待删除项与其左子节点最后一项互换,并递归互换下去,直到将待删除节点换到叶子节点后删除
                root.removeEntry(re.getIndex());
                root.insertEntry(leftChild.entryAt(leftChild.nodeSize() - 1), re.getIndex());
                leftChild.removeEntry(leftChild.nodeSize() - 1);
                leftChild.insertEntry(entry);
                return delete(leftChild, entry);
            }
            //左子节点不可删除项,则同样逻辑检查右子节点
            Node<K, V> rightChild = root.childAt(re.getIndex() + 1);
            if (rightChild.nodeSize() >= t) {
                root.removeEntry(re.getIndex());
                root.insertEntry(rightChild.entryAt(0), re.getIndex());
                rightChild.removeEntry(0);
                rightChild.insertEntry(entry);
                return delete(rightChild, entry);
            }
            //如果左右子节点均不能删除项,将左右子节点合并,并将删除项放到新节点的合并连接处
            Entry<K, V> deletedEntry = root.removeEntry(re.getIndex());
            leftChild.insertEntry(deletedEntry);
            root.removeChild(re.getIndex() + 1);
            //左右子节点合并
            for (int i = 0; i < rightChild.nodeSize(); i++) {
                leftChild.insertEntry(rightChild.entryAt(i));
            }
            //右子节点存在子节点,则子节点也合并入左子节点子节点集合
            if (!rightChild.getIsLeaf()) {
                for (int i = 0; i < rightChild.sons.size(); i++) {
                    leftChild.insertChild(rightChild.childAt(i), leftChild.sons.size());
                }
            }
            //合并后继续向左递归
            return delete(leftChild, entry);
        } else {//删除节点不在本节点
            //回归条件,搜索到叶节点依然没找到,待删除节点不在树中
            if (root.getIsLeaf()) {
                for (int i = 0; i < root.nodeSize(); i++) {
                    System.out.print("++++++++++++++++++++");
                    System.out.print(root.entryAt(i).getKey() + ",");
                    System.out.print("++++++++++++++++++++");
                }
                throw new RuntimeException(entry.key + " is not in this tree!");
            }
            Node<K, V> searchChild = root.childAt(re.index);
            //子节点可删除项,递归删除
            if (searchChild.nodeSize() >= t) {
                return delete(searchChild, entry);
            }
            //待旋转节点,子节点项数小于等于 t-1 ,不能删除项,准备左旋或右旋为其补充项数
            Node<K, V> siblingNode = null;
            int siblingIndex = -1;
            //存在右兄弟
            if (re.getIndex() < root.nodeSize() - 1) {
                Node<K, V> rightBrother = root.childAt(re.getIndex() + 1);
                if (rightBrother.nodeSize() >= t) {
                    siblingNode = rightBrother;
                    siblingIndex = re.getIndex() + 1;
                }
            }
            //不存在右兄弟则尝试左兄嘚
            if (siblingNode == null) {
                if (re.getIndex() > 0) {
                    //尝试左兄弟节点
                    Node<K, V> leftBrothr = root.childAt(re.getIndex() - 1);
                    if (leftBrothr.nodeSize() >= t) {
                        siblingNode = leftBrothr;
                        siblingIndex = re.getIndex() - 1;
                    }
                }
            }
            //至少有一个兄弟可以匀出项来
            if (siblingNode != null) {
                //是左兄嘚
                if (siblingIndex < re.getIndex()) {
                    //左节点最后一项右旋
                    searchChild.insertEntry(root.entryAt(siblingIndex), 0);
                    root.removeEntry(siblingIndex);
                    root.insertEntry(siblingNode.entryAt(siblingNode.nodeSize() - 1), siblingIndex);
                    siblingNode.removeEntry(siblingNode.nodeSize() - 1);
                    //子节点跟着右旋
                    if (!siblingNode.getIsLeaf()) {
                        searchChild.insertChild(siblingNode.childAt(siblingNode.sons.size() - 1), 0);
                        siblingNode.removeChild(siblingNode.sons.size() - 1);
                    }
                } else {
                    //是右兄嘚
                    searchChild.insertEntry(root.entryAt(re.getIndex()), searchChild.nodeSize() - 1);
                    root.removeEntry(re.getIndex());
                    root.insertEntry(siblingNode.entryAt(0), re.getIndex());
                    siblingNode.removeEntry(0);
                    if (!siblingNode.getIsLeaf()) {
                        searchChild.insertChild(siblingNode.childAt(0), searchChild.sons.size());
                        siblingNode.removeChild(0);
                    }
                }
                return delete(searchChild, entry);
            }
            //左右兄嘚都匀不出项来,直接由左右兄嘚节点与父项合并为一个节点
            if (re.getIndex() <= root.nodeSize() - 1) {
                Node<K, V> rightSon = root.childAt(re.getIndex() + 1);
                searchChild.insertEntry(root.entryAt(re.getIndex()), searchChild.nodeSize());
                root.removeEntry(re.getIndex());
                root.removeChild(re.getIndex() + 1);
                for (int i = 0; i < rightSon.nodeSize(); i++) {
                    searchChild.insertEntry(rightSon.entryAt(i));
                }
                if (!rightSon.getIsLeaf()) {
                    for (int j = 0; j < rightSon.sons.size(); j++) {
                        searchChild.insertChild(rightSon.childAt(j), searchChild.sons.size());
                    }
                }
                if (root == this.root) {
                    this.root = searchChild;
                }
            } else {
                //没有右兄弟,试试左兄嘚
                Node<K, V> leftSon = root.childAt(re.getIndex() - 1);
                searchChild.insertEntry(root.entryAt(re.getIndex() - 1), 0);
                root.removeChild(re.getIndex() - 1);
                root.removeEntry(re.getIndex() - 1);
                for (int i = 0; i < leftSon.nodeSize(); i++) {
                    searchChild.insertEntry(leftSon.entryAt(i));
                }
                if (!leftSon.getIsLeaf()) {
                    for (int i = leftSon.sons.size() - 1; i >= 0; i--) {
                        searchChild.insertChild(leftSon.childAt(i), 0);
                    }
                }
                if (root == this.root) {
                    this.root = searchChild;
                }
            }
//            if (root == this.root && root.nodeSize() == 0) {
//                root = searchChild;
//            }
            return delete(searchChild, entry);
        }
    }

    public Entry<K, V> delete(K key) {
        Entry<K, V> en = new Entry<K, V>();
        en.setKey(key);
        return delete(root, en);
    }

    /**
     * @Author Nxy
     * @Date 2020/2/25 14:18
     * @Description 借助队列打印B树
     */
    public void output() {
        Queue<Node<K, V>> queue = new LinkedList<Node<K, V>>();
        queue.offer(this.root);
        while (!queue.isEmpty()) {
            Node<K, V> node = queue.poll();
            for (int i = 0; i < node.nodeSize(); ++i) {
                System.out.print(node.entryAt(i) + " ");
            }
            System.out.println();
            if (!node.getIsLeaf()) {
                for (int i = 0; i <= node.sons.size() - 1; ++i) {
                    queue.offer(node.childAt(i));
                }
            }
        }
    }

    public static void main(String[] args) {
        Random random = new Random();
        BTree<Integer, Integer> btree = new BTree<Integer, Integer>(3);
        List<Integer> save = new ArrayList<Integer>(30);
//        save.add(8290);
//        save.add(7887);
//        save.add(9460);
//        save.add(9928);
//        save.add(6127);
//        save.add(5891);
//        save.add(1592);
//        save.add(14);
//        save.add(8681);
//        save.add(4843);
//        save.add(1051);

        for (int i = 0; i < 20; ++i) {
            int r = random.nextInt(10000);
            save.add(r);
            System.out.print(r + "  ");
            BTree.Entry en = btree.new Entry<Integer, Integer>();
            en.setKey(r);
            en.setValue(r);
//            BTree.Entry en = btree.new Entry<Integer, Integer>();
//            en.setKey(save.get(i));
            btree.insertNode(en);
        }

        System.out.println("----------------------");
        btree.output();
        System.out.println("----------------------");
        btree.delete(save.get(0));
        btree.output();
    }

}

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部