B-Tree插入和洗掉的Java實作-有解無憂

B-Tree插入、洗掉的Java實作

一、一顆非空m階B-Tree的性質
除根結點以外的每個結點的孩子參考最多存在m個，關鍵碼最多存在m - 1個；除根結點以外的每個結點的孩子參考至少存在?m / 2?個，關鍵碼至少存在?m / 2? - 1個，
一顆非空B-Tree的根結點至少存在2個孩子參考（注意：一顆非空B-Tree的根結點最少存在的孩子參考數不受m限制，且最少允許存在2個孩子參考！），
每個結點的關鍵碼遵循“左小右大”排序存放，即關鍵碼集合中靠左的關鍵碼小于靠右側的關鍵碼，
所有葉子結點存在同一層（可以看出B-Tree是一種嚴格平衡的多路搜索樹），
package wind.wdb;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;

/**
 * B-Tree
 * @param <K>
 */
public final class MultipleSearchTree<K> {
    /**
     * B-Tree Node
     * @param <K>
     */
    private static final class BTreeNode<K> {
        K[] key;                    // 關鍵碼陣列
        BTreeNode<K> parent;        // 父結點
        BTreeNode<K>[] ptr;         // 孩子結點陣列
        int ptrSize;                // 實際存在的孩子數量

        BTreeNode(int order) {
            // 關鍵碼陣列和指標陣列都多分配一個存盤空間 避免發生上溢時陣列訪問越界
            this.key        = (K[])new Object[order];
            this.parent     = null;
            this.ptr        = new BTreeNode[order + 1];
            this.ptrSize    = 1;                            // 默認至少擁有一個空孩子
        }
    }

    private static final int FIELD_LIMIT_ORDER_MINIMUM  = 3;            // 階數欄位所允許的最小取值
    private static final int FIELD_LIMIT_ORDER_MAXIMUM  = 65535;        // 階數欄位所允許的最大取值
    private static final int FIELD_DEFAULT_ORDER        = 4;            // 階數欄位默認取值

    private final Comparator<? super K> comparator;         // 關鍵碼比較器
    private final int order;                                // 階數
    private BTreeNode<K> root;                              // 樹根
    private int keySize;                                    // 存盤的關鍵碼數

    public MultipleSearchTree(Comparator<? super K> comparator) {
        checkComparator(comparator);
        this.comparator = comparator;
        this.order = FIELD_DEFAULT_ORDER;
    }

    public MultipleSearchTree(int order, Comparator<? super K> comparator) {
        checkComparator(comparator);
        checkOrder(order);
        this.comparator = comparator;
        this.order = order;
    }


    /**
     * 階數檢查
     * @param order
     */
    private static void checkOrder(int order) {
        if (order < FIELD_LIMIT_ORDER_MINIMUM) {
            System.out.println("階數的取值過小，最小的階數取值不能小于" + FIELD_LIMIT_ORDER_MINIMUM + "！");
        } else if (order > FIELD_LIMIT_ORDER_MAXIMUM) {
            System.out.println("階數的取值過大，最小的階數取值不能大于" + FIELD_LIMIT_ORDER_MAXIMUM + "！");
        }
    }


    /**
     * 比較器檢查
     * @param comparator
     * @param <K>
     */
    private static <K> void checkComparator(Comparator<? super K> comparator) {
        if (comparator == null) {
            throw new NullPointerException("關鍵碼比較器不能為空！");
        }
    }


    /**
     * 移除關鍵碼
     * @param key
     * @return 移除成功回傳true，否則回傳false，
     */
    public boolean remove(K key) {
        if (key == null || this.root == null) {
            return false;
        }

        final Comparator<? super K> comparator = this.comparator;
        BTreeNode<K> delItr = this.root;    // 關鍵碼搜索器
        int delPos          = 0;            // delItr.key[delPos]即為要洗掉的關鍵碼

        do {
            delPos = Arrays.binarySearch(delItr.key, 0, delItr.ptrSize - 1, key, comparator);

            if (delPos < 0) {
                // 不斷深入
                delItr = delItr.ptr[~delPos];
            } else {
                break;
            }
        } while (delItr != null);
        // 關鍵碼不存在   故無法洗掉
        if (delItr == null) return false;
        // 若關鍵碼所在結點存在直接后繼   則將實際洗掉關鍵碼的結點替換為直接后繼
        if (delItr.ptr[delPos + 1] != null) {
            BTreeNode<K> original   = delItr;

            delItr                  = delItr.ptr[delPos + 1];
            while (delItr.ptr[0] != null) {
                delItr = delItr.ptr[0];
            }
            original.key[delPos]    = delItr.key[0];
            delPos                  = 0;
        }
        // 移除關鍵碼
        System.arraycopy(delItr.key, delPos + 1, delItr.key, delPos, (delItr.ptrSize - 1) - (delPos + 1));
        // 此處不必移動孩子陣列進行覆寫洗掉 因為洗掉必然發生在外部結點   故移動空結點是耗時且無意義的
        // 更新屬性
        delItr.ptrSize--;
        // 若發生了下溢則有必要進行修復
        if (delItr.ptrSize < Math.ceil(this.order / 2)) {
            fixUnderflow(delItr);
        }

        this.keySize--;

        return true;
    }


    /**
     * 下溢修復
     * @param fixItr
     */
    private void fixUnderflow(BTreeNode<K> fixItr) {
        final Comparator<? super K> comparator = this.comparator;

        while (fixItr.ptrSize < Math.ceil(this.order / 2)) {
            BTreeNode<K> parent = fixItr.parent;

            // 若已上升至根節點
            if (parent == null) {
                // 對于根節點而言不必滿足至少擁有ceil(m/2)個孩子
                if (fixItr.ptrSize < 2 && fixItr.ptr[0] != null) {
                    this.root           = fixItr.ptr[0];
                    this.root.parent    = null;
                }
                return;
            }

            int fixItrPos = 0;

            // 定位fixItr是其父親的第幾個孩子（下標）
            while (parent.ptr[fixItrPos] != fixItr) {
                ++fixItrPos;
            }


            /*
             * 注意：這里判斷fixItrPos不是一個最左側孩子又或者不是最右側孩子的目的是為了防止關鍵碼陣列parent.key訪問越界！
             * 就以下面這個分支"if (0 < fixItrPos)"為例，
             * 假設此時左兄弟的關鍵碼數量恰好滿足"leftSibling.ptrSize - 1 >= Math.ceil(this.order / 2)"
             * 對于這種情況的修復很簡單：
             *      1、將介于左兄弟leftSibling和fixItr的父節點關鍵碼借給fixItr
             *      2、將左兄弟的最大（最右側）的關鍵碼填補父節點借出關鍵碼的位置
             *      3、最后將左兄弟的最右側孩子結點轉移至fixItr作為最左側孩子即可！
             * 但關鍵就在于第1步的“介于左兄弟leftSibling和fixItr的父節點關鍵碼”的選取
             * 貌似咋看好像是parent.key[fixItrPos - 1]和parent.key[fixItrPos]
             * 都可以作為中間關鍵碼的選取？？但其實并不是    簡單思索便可很清楚的知道
             * 如果此時我們的fixItrPos恰好指向的位置是一個最右側的關鍵碼，而此時如果我們使用[fixItrPos]
             * 對parent.key進行訪問就會恰好超出關鍵碼的最大陣列范圍一個元素位置，從而引發陣列訪問越界例外！
             * 因此只能是選取parent.key[fixItrPos - 1]作為介于兩者之間的中間關鍵碼！
             * 即使fixItrPos是這個分支所允許的最小值，那也最小只可能是1，
             * 也就是說其左兄弟是parent.ptr[0]，此時若使用parent.key[fixItrPos - 1]
             * 取中間關鍵碼那也只會取到最靠左側的關鍵碼，不會發生越界情況！
             * （下面的“if (fixItrPos < parent.ptrSize - 1)”情況是對稱的，同理！主要是為了防止訪問越界！）
             */
            // fixItr不是一個最左側孩子
            if (0 < fixItrPos) {
                BTreeNode<K> leftSibling = parent.ptr[fixItrPos - 1];

                // 若關鍵碼充足
                if (leftSibling.ptrSize - 1 >= Math.ceil(this.order / 2)) {
                    // 父親借出關鍵碼給fixItr
                    System.arraycopy(fixItr.key, 0, fixItr.key, 1, fixItr.ptrSize - 1);
                    fixItr.key[0] = parent.key[fixItrPos - 1];

                    // 左兄弟的最大關鍵碼填補父親借出的關鍵碼位置
                    parent.key[fixItrPos - 1] = leftSibling.key[(leftSibling.ptrSize - 1) - 1];

                    // 左兄弟多出的最右側關鍵碼轉移至fixItr
                    System.arraycopy(fixItr.ptr, 0, fixItr.ptr, 1, fixItr.ptrSize);
                    fixItr.ptr[0] = leftSibling.ptr[leftSibling.ptrSize - 1];
                    if (fixItr.ptr[0] != null) {
                        fixItr.ptr[0].parent = fixItr;
                    }

                    // 更新屬性
                    fixItr.ptrSize++;
                    leftSibling.ptrSize--;

                    return;
                }
            }

            // fixItr不是一個最右側孩子
            if (fixItrPos < parent.ptrSize - 1) {
                BTreeNode<K> rightSibling = parent.ptr[fixItrPos + 1];

                if (rightSibling.ptrSize - 1 >= Math.ceil(this.order / 2)) {
                    // 父親借出關鍵碼給fixItr
                    fixItr.key[fixItr.ptrSize - 1] = parent.key[fixItrPos];

                    // 右兄弟的最小關鍵碼填補父親借出的關鍵碼位置
                    parent.key[fixItrPos] = rightSibling.key[0];
                    System.arraycopy(rightSibling.key, 1, rightSibling.key, 0, (rightSibling.ptrSize - 1) - 1);

                    // 右兄弟多出的最左側孩子轉移至fixItr
                    fixItr.ptr[fixItr.ptrSize] = rightSibling.ptr[0];
                    System.arraycopy(rightSibling.ptr, 1, rightSibling.ptr, 0, rightSibling.ptrSize - 1);
                    if (fixItr.ptr[fixItr.ptrSize] != null) {
                        fixItr.ptr[fixItr.ptrSize].parent = fixItr;
                    }

                    // 更新屬性
                    fixItr.ptrSize++;
                    rightSibling.ptrSize--;

                    return;
                }
            }

            if (0 < fixItrPos) {
                BTreeNode<K> leftSibling = parent.ptr[fixItrPos - 1];

                // 父節點關鍵碼轉移至左兄弟末尾
                leftSibling.key[leftSibling.ptrSize - 1] = parent.key[fixItrPos - 1];
                System.arraycopy(parent.key, fixItrPos, parent.key, fixItrPos - 1, (parent.ptrSize - 1) - fixItrPos);

                // 將fixItr從parent的孩子集合中移除
                System.arraycopy(parent.ptr, fixItrPos + 1, parent.ptr, fixItrPos, parent.ptrSize - (fixItrPos + 1));
                // 更新屬性
                parent.ptrSize--;

                // 將fixItr的全部關鍵碼轉移至左兄弟
                System.arraycopy(fixItr.key, 0, leftSibling.key, leftSibling.ptrSize, fixItr.ptrSize - 1);

                // 將fixItr的全部孩子轉移至左兄弟
                if (fixItr.ptr[0] != null) {
                    System.arraycopy(fixItr.ptr, 0, leftSibling.ptr, leftSibling.ptrSize, fixItr.ptrSize);
                    for (int i = 0; i < fixItr.ptrSize; ++i) {
                        fixItr.ptr[i].parent = leftSibling;
                    }
                }

                // 更新屬性
                leftSibling.ptrSize += fixItr.ptrSize;
            } else {
                BTreeNode<K> rightSibling = parent.ptr[fixItrPos + 1];

                // 父節點轉移關鍵碼至fixItr
                fixItr.key[fixItr.ptrSize - 1] = parent.key[fixItrPos];
                System.arraycopy(parent.key, fixItrPos + 1, parent.key, fixItrPos, (parent.ptrSize - 1) - (fixItrPos + 1));

                // 將rs從parent的孩子集合中移除
                System.arraycopy(parent.ptr, fixItrPos + 2, parent.ptr, fixItrPos + 1, parent.ptrSize - (fixItrPos + 2));
                // 更新屬性
                parent.ptrSize--;

                // 將右兄弟的全部關鍵碼轉移至fixItr
                System.arraycopy(rightSibling.key, 0, fixItr.key, fixItr.ptrSize, rightSibling.ptrSize - 1);

                // 將右兄弟的全部孩子轉移至fixItr
                if (rightSibling.ptr[0] != null) {
                    System.arraycopy(rightSibling.ptr, 0, fixItr.ptr, fixItr.ptrSize, rightSibling.ptrSize);
                    for (int i = 0; i < rightSibling.ptrSize; ++i) {
                        rightSibling.ptr[i].parent = fixItr;
                    }
                }

                // 更新屬性
                fixItr.ptrSize += rightSibling.ptrSize;
            }

            // 上溯
            fixItr = parent;
        }
    }


    /**
     * 添加新的關鍵碼
     * @param key 添加的關鍵碼
     * @return 添加成功回傳true，否則回傳false，
     */
    public boolean add(K key) {
        // 若key先前并不存在當前B-Tree中  則必然會添加成功
        if (key == null) {
            return false;
        } else if (this.root != null) {
            final Comparator<? super K> comparator  = this.comparator;
            BTreeNode<K> iterator                   = this.root;
            BTreeNode<K> insert                     = null;
            int insPos                                 = 0;

            do {
                insPos = Arrays.binarySearch(iterator.key, 0, iterator.ptrSize - 1, key, comparator);

                if (insPos < 0) {
                    // 不斷深入 并由insert記錄最終的插入結點
                    insert      = iterator;
                    iterator    = iterator.ptr[~insPos];
                } else {
                    // 若找到key已存在當前B-Tree中則中斷插入操作
                    return false;
                }
            } while (iterator != null);
            // 取得正確的關鍵碼插入位置
            insPos = ~insPos;
            // 將insert.key[insPos]起始的往后關鍵碼整體向后移動一位  空出[insPos]位置供插入使用
            System.arraycopy(insert.key, insPos, insert.key, insPos + 1, (insert.ptrSize - 1) - insPos);
            insert.key[insPos] = key;
            // 此處無需將insert.ptr[insPos + 1]起始的往后關鍵碼整體向后移動    因為插入必然發生在外部結點   移動空孩子無意義且費效率
            insert.ptrSize++;
            // 若有需要需進行上溢修復
            if (insert.ptrSize > this.order) {
                fixOverflow(insert);
            }
        } else {
            this.root           = new BTreeNode<>(this.order);
            this.root.key[0]    = key;
            this.root.ptrSize   = 2;
        }

        this.keySize++;

        return true;
    }

    /**
     * 上溢修復
     * @param fixItr
     */
    private final void fixOverflow(BTreeNode<K> fixItr) {
        final Comparator<? super K> comparator = this.comparator;

        while (fixItr.ptrSize > this.order) {
            BTreeNode<K> parent = fixItr.parent;                    // 父親
            BTreeNode<K> right  = new BTreeNode<>(this.order);      // 分裂出來的右孩子
            int midKeyIndex     = (fixItr.ptrSize - 1) >> 1;        // fixItr.key的中間關鍵碼位置下標

            // fixItr.key[midKeyIndex]作為被提升至父節點的關鍵碼
            // fixItr.key從[midKeyIndex + 1]起始的關鍵碼全部轉移至right.key
            System.arraycopy(fixItr.key, midKeyIndex + 1, right.key, 0, (fixItr.ptrSize - 1) - (midKeyIndex + 1));
            // fixItr.ptr從[midKeyIndex + 1]起始的孩子全部轉移至right.ptr
            if (fixItr.ptr[0] != null) {
                System.arraycopy(fixItr.ptr, midKeyIndex + 1, right.ptr, 0, fixItr.ptrSize - (midKeyIndex + 1));
                // 重定向父親參考
                for (int i = midKeyIndex + 1; i < fixItr.ptrSize; ++i) {
                    fixItr.ptr[i].parent = right;
                }
            }
            // 更新屬性
            right.ptrSize   = fixItr.ptrSize - (midKeyIndex + 1);
            fixItr.ptrSize  -= right.ptrSize;

            // 若發生上溢的是根節點
            if (parent == null) {
                this.root           = new BTreeNode<>(this.order);
                this.root.key[0]    = fixItr.key[midKeyIndex];
                this.root.ptr[0]    = fixItr;
                this.root.ptr[1]    = right;
                fixItr.parent       = this.root;
                right.parent        = this.root;
                // 更新屬性
                this.root.ptrSize   = 2;
                return;
            }

            // 若發生上溢的非根節點
            // 確定中間關鍵碼在parent.key中的提升位置
            int risePos = ~Arrays.binarySearch(parent.key, 0, parent.ptrSize - 1, fixItr.key[midKeyIndex], comparator);

            // 騰出parent.key[risePos]以供存盤提升的關鍵碼
            System.arraycopy(parent.key, risePos, parent.key, risePos + 1, (parent.ptrSize - 1) - risePos);
            parent.key[risePos]     = fixItr.key[midKeyIndex];
            // 騰出parent.ptr[risePos + 1]以供存盤分裂出來的右孩子
            System.arraycopy(parent.ptr, risePos + 1, parent.ptr, risePos + 2, parent.ptrSize - (risePos + 1));
            parent.ptr[risePos + 1] = right;
            right.parent            = parent;
            // 更新屬性
            parent.ptrSize++;

            // 上溯
            fixItr = parent;
        }
    }

}


final class Run {
    public static void main(String[] args) {
        MultipleSearchTree<Double> bTree    = new MultipleSearchTree<>(4, Double::compareTo);
        Random random                       = new Random();
        Double[] key                        = new Double[100000];

        for (int j = 0; j < 100; ++j) {
            for (int i = 0; i < key.length; ++i) {
                key[i] = random.nextDouble();
            }
            for (int i = 0; i < key.length; ++i) {
                System.out.print("第" + (i + 1) + "輪：");
                System.out.println(bTree.add(key[i]) ? "插入成功" : "插入失敗");
            }
            for (int i = 0; i < key.length; ++i) {
                System.out.print("第" + (i + 1) + "輪：");
                System.out.println(bTree.remove(key[i]) ? "洗掉成功" : "洗掉失敗");
            }
        }
    }
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/244002.html
標籤：java
上一篇：B-Tree插入、洗掉的Java實作
下一篇：cxLookupComboBox1顯示問題？