算法导论之B树

搜索
插入
删除

致敬发明人

Rudolf Bayer
https://en.wikipedia.org/wiki/Rudolf_Bayer

Rudolf-Bayer.png
Edward M. McCreight
https://en.wikipedia.org/wiki/Edward_M._McCreight

Edward-M.McCreight.png

插入

插入示例1

插入示例1.png
插入示例2

插入示例2.png

删除

删除示例1

删除示例1.png
删除示例2

删除示例2.png

插入示例2

源代码

BTreeTest.java

package cs.tsinghua.edu.chapter8;

public class BTreeTest {
    public static void main(String[] args) {
        int key53 = 53;
        int key36 = 36;
        int key77 = 77;
        int key89 = 89;
        int key19 = 19;
        int key41 = 41;
        int key51 = 51;
        int key75 = 75;
        int key79 = 79;
        int key84 = 84;
        int key97 = 97;
        int key64 = 64;

//        BTNode node53 = new BTNode();
//        node53.getKeys().add(key53);
//
//        BTNode node36= new BTNode();
//        node36.getKeys().add(key36);
//
//        BTNode node7789= new BTNode();
//        node7789.getKeys().add(key77);
//        node7789.getKeys().add(key89);
//
//        BTNode node19= new BTNode();
//        node19.getKeys().add(key19);
//
//        BTNode node4151= new BTNode();
//        node4151.getKeys().add(key41);
//        node4151.getKeys().add(key51);
//
//        BTNode node75= new BTNode();
//        node75.getKeys().add(key75);
//
//        BTNode node7984= new BTNode();
//        node7984.getKeys().add(key79);
//        node7984.getKeys().add(key84);
//
//        BTNode node97= new BTNode();
//        node97.getKeys().add(key97);
//
//        //设置父子关系
//        node53.setParent(null);
//        node53.getChildren().set(0, node36);
//        node53.getChildren().add(1, node7789);
//
//        node36.setParent(node53);
//        node36.getChildren().set(0, node19);
//        node36.getChildren().add(1, node4151);
//
//        node7789.setParent(node53);
//        node7789.getChildren().set(0,node75);
//        node7789.getChildren().add(1, node7984);
//        node7789.getChildren().add(2, node97);
//
//        node19.setParent(node36);
//        node19.getChildren().add(1, null);
//
//        node4151.setParent(node36);
//        node4151.getChildren().add(1, null);
//        node4151.getChildren().add(2, null);
//
//        node75.setParent(node7789);
//        node75.getChildren().add(1, null);
//
//        node7984.setParent(node7789);
//        node7984.getChildren().add(1, null);
//        node7984.getChildren().add(2, null);
//
//        node97.setParent(node7789);
//        node97.getChildren().add(1, null);
//
//        //构建B树并初始化根节点
//        BTree tree = new BTree(3);
//        tree.root = node53;
//        tree.size = 11;

        //搜索测试
        //tree.search(key36);
        //tree.search(key79)

        //插入测试
//        int key23 = 23;
//        int key29 = 29;
//        int key45 = 45;
//        int key87 = 87;
//        tree.insert(key23);
//        tree.insert(key29);
//        tree.insert(key45);
//        tree.insert(key87);
        //删除测试
        BTNode node53 = new BTNode();
        node53.getKeys().add(key53);

        BTNode node36= new BTNode();
        node36.getKeys().add(key36);

        BTNode node7789= new BTNode();
        node7789.getKeys().add(key77);
        node7789.getKeys().add(key89);

        BTNode node19= new BTNode();
        node19.getKeys().add(key19);

        BTNode node4151= new BTNode();
        node4151.getKeys().add(key41);
        node4151.getKeys().add(key51);

        BTNode node6475 = new BTNode();
        node6475.getKeys().add(key64);
        node6475.getKeys().add(key75);

        BTNode node7984= new BTNode();
        node7984.getKeys().add(key79);
        node7984.getKeys().add(key84);

        BTNode node97= new BTNode();
        node97.getKeys().add(key97);

        //设置父子关系
        node53.setParent(null);
        node53.getChildren().set(0, node36);
        node53.getChildren().add(1, node7789);

        node36.setParent(node53);
        node36.getChildren().set(0, node19);
        node36.getChildren().add(1, node4151);

        node7789.setParent(node53);
        node7789.getChildren().set(0,node6475);
        node7789.getChildren().add(1, node7984);
        node7789.getChildren().add(2, node97);

        node19.setParent(node36);
        node19.getChildren().add(1, null);

        node4151.setParent(node36);
        node4151.getChildren().add(1, null);
        node4151.getChildren().add(2, null);

        node6475.setParent(node7789);
        node6475.getChildren().add(1, null);

        node7984.setParent(node7789);
        node7984.getChildren().add(1, null);
        node7984.getChildren().add(2, null);

        node97.setParent(node7789);
        node97.getChildren().add(1, null);

        node6475.getChildren().add(1,null);
        node6475.setParent(node7789);

        //构建B树并初始化根节点
        BTree tree = new BTree(3);
        tree.root = node53;
        tree.size = 12;

        tree.remove(key41);
        tree.remove(key53);
        tree.remove(key75);
        tree.remove(key84);
        tree.remove(key51);
    }
}

BTree.java

package cs.tsinghua.edu.chapter8;

public class BTree<Key extends Comparable> {
    //入口:根节点
    public BTNode root;
    //辅助节点
    private BTNode hot;
    //B树的阶次，至少为3
    private int order;
    //存放的关键码个数
    public int size;

    public BTree () {
        this.order = 3;
        root = new BTNode();
    }

    public BTree (int order) {
        this.order = order;
        root = new BTNode();
    }

    public static void main(String[] args) {
        //构建测试
        BTree tree = new BTree(3);
        tree.insert(53);

        tree.insert(36);
        tree.insert(77);
        tree.insert(89);

        tree.insert(19);
        tree.insert(41);
        tree.insert(51);
        tree.insert(75);
        tree.insert(79);
        tree.insert(84);
        tree.insert(97);

        System.out.println("插入结束");

        //删除测试
        tree.remove(43);

    }

    public boolean remove(Key e) {
        BTNode v = search(e);
        if (v == null) {
            return false;
        }
        //计算关键码e在v中的秩
        int rank = v.getKeys().indexOf(e);
        //如果v是非叶子节点，则找关键码的直接后继
        //如果v是叶子节点，则找到关键码e在节点v中的秩，将其从节点v的关键码向量中删除，将其从节点v的分支中删除
        if (v.getChildren().get(0) != null) {
            //v是非叶子节点，则找关键码的直接后继，必在叶子节点中
            //沿着v的右子树一直向左
            BTNode u = (BTNode) v.getChildren().get(rank + 1);
            while (u.getChildren().get(0)!= null) {
                u = (BTNode) u.getChildren().get(0);
            }
            //找到关键码的直接后继所在的叶子节点了:将节点v和其直接后继交换位置
            v.getKeys().set(rank, u.getKeys().get(0));
            v = u;
            rank = 0;
        }
        v.getKeys().remove(rank);
        v.getChildren().remove(rank+1);
        this.size --;
        solveUnderFlow(v);
        return true;

    }

    private void solveUnderFlow(BTNode v) {
        int minBranch = (this.order + 1)/2;
        if (minBranch <= v.getChildren().size()) {
            //递归基：满足B树节点限制，未发生下溢
            return ;
        }
        BTNode p = v.getParent();
        if (p == null) {
            //根节点需要下溢
            if (v.getKeys().size() <= 0 && v.getChildren().get(0) != null) {
                //根节点中已经没有关键码，但有非空的孩子
                this.root = (BTNode) v.getChildren().get(0);
                this.root.setParent(null);
                v.getChildren().set(0,null);
            }
            return ;
        }

        //确定节点v是节点p的第几个孩子
        int rank = 0;
        while (p.getChildren().get(rank) != v) {
            rank ++;
        }
        if (rank > 0) {
            //节点v不是节点p的第一个孩子:左兄弟存在且足够胖
            BTNode ls = (BTNode) p.getChildren().get(rank -1);
            if (ls.getChildren().size() > minBranch) {
                //父节点p就借一个关键码给节点v且作为最小关键码
                v.getKeys().insertElementAt(p.getKeys().get(rank -1), 0);
                //将左兄弟ls的最大关键码转入父节点p
                p.getKeys().set(rank -1, ls.getKeys().remove(ls.getKeys().size() -1));
                //将左兄弟ls的最左侧孩子过继给下溢节点v且作为最左侧孩子
                v.getChildren().insertElementAt(ls.getChildren().remove(ls.getChildren().size() -1),0);
                if (v.getChildren().get(0) != null) {
                    BTNode leftest = (BTNode) v.getChildren().get(0);
                    leftest.setParent(v);
                }
                //至此，通过右旋已经完成对当前层的下溢处理
                return ;
            }
        }
        //v是p的第一个孩子:注意此时rank=0
        if (rank < p.getChildren().size() - 1) {
            //但不是最后一个孩子，则节点v的有右兄弟肯定存在
            BTNode rs = (BTNode) p.getChildren().get(rank + 1);
            if (minBranch < rs.getChildren().size()) {
                //右兄弟够胖:
                //父节点p就借一个关键码给v，作为节点v的最大关键码
                v.getKeys().insertElementAt(p.getKeys().get(rank), v.getKeys().size());
                //将右兄弟rs的最小关键码转入父节点p
                p.getKeys().set(rank, rs.getKeys().remove(0));
                //将右兄弟rs的最左侧孩子过继给节点v且作为最右侧孩子
                v.getChildren().insertElementAt(rs.getChildren().remove(0), v.getChildren().size());
                if (v.getChildren().get(v.getChildren().size() - 1) != null) {
                    BTNode rightest = (BTNode) v.getChildren().get(v.getChildren().size() - 1);
                    rightest.setParent(v);
                }
                //至此，通过左旋已经完成当前层的下溢处理
                return ;
            }
        }

        if (rank > 0) {
            //左兄弟存在
            BTNode ls = (BTNode) p.getChildren().get(rank -1);
            //将节点p的第r-1个关键码转入左兄弟，且节点v不再是节点p的第rank个孩子
            ls.getKeys().insertElementAt(p.getKeys().remove(rank-1), ls.getKeys().size());
            p.getChildren().remove(rank);
            //将节点v的最左侧孩子过继给左兄弟节点ls做最右侧的孩子
            ls.getChildren().insertElementAt(v.getChildren().get(0),ls.getChildren().size());
            if (ls.getChildren().get(ls.getChildren().size() - 1) != null) {
                BTNode rightest = (BTNode) ls.getChildren().get(ls.getChildren().size()-1);
                rightest.setParent(ls);
            }
            //将节点v的剩余关键码依次转入ls
            while (!v.getKeys().isEmpty()) {
                ls.getKeys().insertElementAt(v.getKeys().remove(0), ls.getKeys().size());
                ls.getChildren().insertElementAt(v.getChildren().remove(0), ls.getChildren().size());
                if (ls.getChildren().get(ls.getChildren().size() - 1) != null) {
                    BTNode rightest = (BTNode) ls.getChildren().get(ls.getChildren().size()-1);
                    rightest.setParent(ls);
                }
            }
        }else {
            //右兄弟存在
            BTNode rs = (BTNode) p.getChildren().get(rank+1);
            //将节点p的第r个关键码转入右兄弟，且节点v不再是节点p的第rank个孩子
            rs.getKeys().insertElementAt(p.getKeys().remove(rank), 0);
            p.getChildren().remove(rank);
            //将节点v的最右侧孩子过继rs给右兄弟节点rs做最左侧的孩子
            rs.getChildren().insertElementAt(v.getChildren().get(v.getChildren().size() - 1),0);
            if (rs.getChildren().get(0) != null) {
                BTNode leftest = (BTNode) rs.getChildren().get(0);
                leftest.setParent(rs);
            }
            //将节点v的剩余关键码依次转入ls
            while (!v.getKeys().isEmpty()) {
                rs.getKeys().insertElementAt(v.getKeys().remove(v.getKeys().size()-1), 0);
                rs.getChildren().insertElementAt(v.getChildren().remove(v.getChildren().size()-1), 0);
                if (rs.getChildren().get(0) != null) {
                    BTNode leftest = (BTNode) rs.getChildren().get(0);
                    leftest.setParent(rs);
                }
            }
        }
        //上升一层继续分裂
        solveUnderFlow(p);
    }

    public boolean insert(Key e) {
        BTNode v = search(e);
        if (v != null) {
            return false;
        }
        //在hot节点的有序关键码向量中查找合适的插入位置
        int rank = 0;
        int hotKeySize = hot.getKeys().size();
        while (rank < hotKeySize && e.compareTo(hot.getKeys().get(rank))>0) {
            rank ++;
        }
        //将新关键码插入到合适的位置
        hot.getKeys().insertElementAt(e, rank);
        //创建一个空子树指针
        hot.getChildren().insertElementAt(null, rank+1);
        //更新全树规模
        this.size ++;
        //如果有必要，需要做分裂
        solveOverFlow(hot);
        return true;
    }

    private void solveOverFlow(BTNode v) {
        if (this.order >= v.getChildren().size()) {
            //递归基：表示当前节点并没有发生上溢
            return ;
        }
        //获取轴点
        int pivot = this.order/2;
        BTNode u = new BTNode();
        //将v右侧order-privot-1个孩子及关键码分裂为右侧u节点
        for (int j = 0 ; j < this.order - pivot - 1;j++) {
            u.getChildren().insertElementAt(v.getChildren().remove(pivot+1), j);
            u.getKeys().insertElementAt(v.getKeys().remove(pivot+1), j);
        }
        //移动节点v最靠右的孩子
        u.getChildren().set(this.order - pivot -1,v.getChildren().remove(pivot+1));
        if (u.getChildren().get(0) != null) {
            //节点u的孩子们非空，则统一设置其父节点
            for (int j = 0; j < this.order - pivot; j++) {
                BTNode uChild = (BTNode) u.getChildren().get(j);
                uChild.setParent(u);
            }
        }
        //节点v的父节点
        BTNode p = v.getParent();
        if (p == null) {
            p = new BTNode();
            this.root = p;
            p.getChildren().set(0, v);
            v.setParent(p);
        }
        //获取节点p中指向u的指针的秩
        int rank = 0;
        Key e = (Key)v.getKeys().get(0);
        int pKeySize = p.getKeys().size();
        while (rank < pKeySize && e.compareTo(p.getKeys().get(rank))>0) {
            rank ++;
        }
        //提升轴点的关键码
        p.getKeys().insertElementAt(v.getKeys().remove(pivot), rank);
        //建立新节点u与父节点p之间的关联
        p.getChildren().insertElementAt(u, rank+1);
        u.setParent(p);
        //继续上溢
        solveOverFlow(p);

    }

    public BTNode search(Key e) {
        BTNode v = this.root;
        this.hot = null;
        while (v != null) {
            //在当前节点中搜索不大于e的最大关键码
            int rank = 0;
            int keySize = v.getKeys().size();
            while (rank < keySize && e.compareTo(v.getKeys().get(rank))>0) {
                rank ++;
            }
            if (rank < keySize && (e.compareTo(v.getKeys().get(rank)) == 0)) {
                return v;
            }
            this.hot = v;
            v = (BTNode) v.getChildren().get(rank);
        }
        return null;
    }
}

BTNode.java

package cs.tsinghua.edu.chapter8;

import java.util.Vector;

public class BTNode<Key extends Comparable> {
    //关键码向量
    private Vector<Key> keys;
    //孩子向量
    private Vector<BTNode> children;
    //父节点
    private BTNode parent;

    /**
     * BTNode只能作为根节点创建，且初始时有0个关键码和1个空孩子指针
     */
    public BTNode () {
        keys = new Vector<>();
        children = new Vector<>();
        parent = null;
        children.insertElementAt(null, 0);
    }

    /**
     * 作为根节点，而且只有一个关键码，和两个孩子
     * @param e
     * @param lc
     * @param rc
     */
    public BTNode(Key e, BTNode lc, BTNode rc) {
        parent = null;
        keys.insertElementAt(e, 0);
        children.insertElementAt(lc, 0);
        children.insertElementAt(rc, 1);
        if (lc != null) {
            lc.setParent(this);
        }
        if (rc != null) {
            rc.setParent(this);
        }
    }

    public BTNode getParent() {
        return parent;
    }

    public void setParent(BTNode parent) {
        this.parent = parent;
    }

    public Vector<Key> getKeys() {
        return keys;
    }

    public void setKeys(Vector<Key> keys) {
        this.keys = keys;
    }

    public Vector<BTNode> getChildren() {
        return children;
    }

    public void setChildren(Vector<BTNode> children) {
        this.children = children;
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof BTNode)) {
            return false;
        }
        boolean result = true;
        BTNode other = (BTNode) obj;
        Vector<Key> otherKeys = other.getKeys();
        int size = otherKeys.size();
        for (int i=0; i<size; i++) {
           Key otherKey = otherKeys.get(i);
           Key myKey = this.getKeys().get(i);
           if (myKey.compareTo(otherKey) != 0) {
                result = false;
                break;
           }
        }
        return result;
    }
}

最后编辑于：2019.06.08 17:29:09

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 218,036评论 6赞 506
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,046评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 164,411评论 0赞 354
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,622评论 1赞 293
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,661评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,521评论 1赞 304
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,288评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,200评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,644评论 1赞 314
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,837评论 3赞 336
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,953评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,673评论 5赞 346
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,281评论 3赞 329
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,889评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,011评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,119评论 3赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,901评论 2赞 355

算法导论之B树

致敬发明人

插入

删除

源代码

推荐阅读更多精彩内容