V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
notcome
V2EX  ›  程序员

多叉树怎么翻译,以及求推荐比较节约的可持久化 (persistent) 多叉树数据结构

  •  
  •   notcome · 2014-06-04 10:43:02 +08:00 · 3482 次点击
    这是一个创建于 3816 天前的主题,其中的信息可能已经有所发展或是发生改变。
    需要建立一个类似文件系统的数据结构, 要求能追踪全部的版本信息. 想来使用一个可持久化的多叉树应该比较方便 (难道还有别的方法吗……)

    又一次手残还没打完就发送了……

    然后我发现不知道怎么翻译多叉树, 谷歌说是 multitree, 看了一下维基百科似乎不是指多叉树.唯一相关的术语是 branching factor, 不过谷歌学术无果.

    目前我就是在纠结树节点如何保存. 因为每次修改的时候 branching factor 实际上已经确定了, 所以使用数组直接存指针应该就可以, 但是这样每次修改需要拷贝 N 个节点, 在平均 branching factor 为 10 的情况下比使用二叉树模拟空间消耗大两倍.

    但是感觉使用二叉树模拟多叉树实现比较复杂, 还没有深入思考. 业界有没有什么成熟的解决方案, 供我借鉴借鉴?

    搜索能力比较捉急啊……
    9 条回复    2014-06-05 14:50:33 +08:00
    notcome
        1
    notcome  
    OP
       2014-06-04 10:57:54 +08:00
    我是不是应该先看一下 B-tree……
    fansekey
        2
    fansekey  
       2014-06-04 11:01:48 +08:00
    不应该是 森林 吗?
    notcome
        3
    notcome  
    OP
       2014-06-04 11:07:35 +08:00 via iPhone
    @fansekey 啊?森林不就是额外加一个节点多叉树吗?
    TMBest
        4
    TMBest  
       2014-06-04 11:09:39 +08:00
    《算法导论》里的,用二叉树实现多叉树,左孩子,右兄弟。
    notcome
        5
    notcome  
    OP
       2014-06-04 11:29:08 +08:00
    @TMBest 我想要建立持久化的存储,如果这样做的话,比如说第五号兄弟需要修改,那么前面四个也需要再备份一遍。在我的应用场景下(即每次增减兄弟都要创建新的版本),这种方式不如直接用数组存指针。

    其实一开始我还愣了一下,后来想起来这是我构思的第一个数据结构,不过子结点我竖着画兄弟横着画,嗯,邻接链表什么的即视感。
    notcome
        6
    notcome  
    OP
       2014-06-04 11:32:02 +08:00
    在钻研 B-tree 之前我还是自己想一想吧。

    如果使用二叉树模拟多叉树,即只用叶子节点存储信息,那么问题也就转变成实现一个二叉树,越平衡越好,只使用叶子节点存信息,支持叶子节点的插入和删除,持久化。嗯对。
    MasterYoda
        7
    MasterYoda  
       2014-06-04 11:51:22 +08:00
    lsm tree
    ffffwh
        8
    ffffwh  
       2014-06-04 13:29:03 +08:00
    n-ary tree?
    vidon
        9
    vidon  
       2014-06-05 14:50:33 +08:00
    ancestry
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1223 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 23:12 · PVG 07:12 · LAX 15:12 · JFK 18:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.