程序包 xin.manong.weapon.base.collection

类 BTree<K,​V>

  • 所有已实现的接口:
    Iterable<Entry<K,​V>>
    public class BTree<K,​V>
extends Object
implements Iterable<Entry<K,​V>>
    B+树：阶数m平衡树实现(3<=m<=31，缺省m=13) 1. 所有数据保存在叶子节点，非叶子节点为索引节点 2. 叶子节点数据数量及非叶子节点索引(孩子)数量不小于(m-1)/2+1，不大于m 3. 非叶子节点索引存储下层节点最大key及指向下层节点的引用 4. 非叶子根结点允许最少2个索引(孩子) 5. 支持正向和逆向数据迭代 6. 支持自定义数据比较器
    作者:
    frankcl

    • 构造器详细资料

      • BTree

        public BTree()

      • BTree

        public BTree​(int m)

      • BTree

        public BTree​(int m,
             Comparator<? super K> comparator)

    • 方法详细资料

      • size

        public int size()
        数据数量
        返回:
        数据数量

      • isEmpty

        public boolean isEmpty()
        是否为空
        返回:
        没有数据返回true，否则返回false

      • add

        public boolean add​(K key,
                   V value)
        添加数据 1. 如果数据key已经存在，则使用value覆盖原值，返回false 2. 添加数据之后，如果破坏节点结构规则，需调整节点 a）如果节点数据量(索引量)大于m，需要分裂节点 b）如果节点最大值改变，需要修改其父节点索引数据 c）以上a）和b）操作可能产生链式影响
        参数:
        key - 数据key，如果key为null抛出异常NullPointerException
        value - 数据值，如果value为null抛出异常NullPointerException
        返回:
        如果key不存在返回true，否则返回false

      • remove

        public V remove​(K key)
        移除数据 1. 如果数据key存在则删除数据并返回数据值，否则不做任何操作并返回null 2. 删除数据后，如果破坏节点结构规则，需调整节点 a）如果节点数据量(索引量)小于(m-1)/2+1，进行以下步骤调整 1）如果兄弟节点数据量(索引量)大于m，则像兄弟节点借取一个数据(索引)，否则进行2） 2）与兄弟节点合并 3）1）和2）会对父节点索引造成影响，需要调整父节点索引数据 b）删除数据可能影响父节点索引数据，需要对父节点索引数据进行调整 c）以上a）和b）操作可能造成链式影响
        参数:
        key - 数据key，如果key为null抛出异常NullPointerException
        返回:
        成功返回数据值，否则返回null

      • removeFirst

        public Entry<K,​V> removeFirst()
        移除第一个元素
        返回:
        成功返回移除元素，否则返回null

      • removeLast

        public Entry<K,​V> removeLast()
        移除最后一个元素
        返回:
        成功返回移除元素，否则返回null

      • getFirst

        public Entry<K,​V> getFirst()
        获取第一个元素
        返回:
        存在返回第一个元素，否则返回null

      • getLast

        public Entry<K,​V> getLast()
        获取最后一个元素
        返回:
        存在返回最后一个元素，否则返回null

      • search

        public V search​(K key)
        搜索数据
        参数:
        key - 数据key，如果key为null抛出异常NullPointerException
        返回:
        如果key存在返回数据，否则返回null

      • search

        public List<V> search​(K startKey,
                      K endKey)
        搜索数据范围 如果startKey大于endKey抛出异常IllegalArgumentException
        参数:
        startKey - 起始key，如果key为null抛出异常NullPointerException
        endKey - 结束key，如果key为null抛出异常NullPointerException
        返回:
        返回在起始key（包含）和结束key（包含）范围内数据

      • toString

        public String toString()
        格式化BTree数据
        覆盖:
        toString 在类中 Object
        返回:
        格式化字符串

      • reversedIterator

        public Iterator<Entry<K,​V>> reversedIterator()
        获取逆向数据迭代器
        返回:
        逆向数据迭代器