美文网首页
Red-Black tree and B-tree

Red-Black tree and B-tree

作者: wanncy | 来源:发表于2019-07-06 10:47 被阅读0次

    红黑树和B-tree,是BST(二叉搜索树)里运用较多的两种树,

    BST category

    • AVL tree
    • 2-3 tree
    • 2-3-4 tree
    • B-trees
    • Red-Black tree
    • skip list
    • treap

    前言:red-black tree(红黑树)由于其存在的 color flips 和 rotation 两种操作,且case较多 ,因此不建议记住它每种case对应的操作,一般步骤是按照 B-tree、2-3-4 tree、red-black tree的步骤讲述,将 red-black tree 看成 2-3-4 tree 的等距二叉树版本,其中的 insertdelete 操作就能对照来看。

    Usage

    • C++: std::map / std::set
    • Java: TreeMap / TreeSet
    • Haskell: Data.Map

    BST

    Balanced Search Tree

    AVL tree

    AVL tree is a self-balancing Binary Search Tree(BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

    • AVL 树是在普通BST的基础上增加了子树的高度限制,以保证在查找过程中,不会出现斜树的情况
    • 时间复杂度则为 O(logn)

    B-trees

    2-3-4 tree

    2-3-4 tree 是B-Trees的一种,节点内的keys的个数是 b-1 到 2b-1 即:1-3个,节点有2,3或4个孩子

    Time complexity

    以下分析 B Tree的 search、insert、delete complexity。

    • search complexity


      search_complexity

    这里解释下 height 是 O(log_b n),从B tree 的 max height出发考虑:1+2(b-1)+2b(b-1)+... = n 可推出。

    • insert complexity


      insert_complexity
    • delete complexity


      delete_complexity

    从上述可以看出对于 2-3-4 tree 而言,其 time complexity 总是为:O(log n),克服了普通 BST 因为 height 导致在增删改查的时候发挥不稳定的特点。

    B+ Tree

    B+ 树是在B 树基础上发展的数据结构,MySQL普遍使用B+树实现其索引结构。

    • 经典的B+树与B 树相比,一个m阶的B+树有k个子树的中间节点包含k个元素(不同于B树中的k-1个元素),每个元素不保存value,只用来索引,所有的(key,value)都保存在叶子节点中
    • 在经典的B+树基础上,对叶子节点本身进行指针的顺序链接,以加快范围的查询

    优点: 由于非叶子节点中不承载数据,因此非叶子节点的每一层可以容纳更多的元素,降低了树的高度,减少了磁盘I/O的次数。并且因为叶子节点之间存在顺序链接的指针,遍历数据也会很简单。

    Red-Black tree

    红黑树是在查找数据结构里运用较多,典型的特点是在BST的基础上增加了树的平衡特性,即通过保证Black-height(路径上黑色节点的数目)相等,来保证树高<=2log(n+1)

    red-black tree
    • 证明:h <= 2log(n+1)
      (将红黑树的红色节点合并到父亲黑色节点,得到2-3-4树,利用2-3-4树叶子节点与树高的关系推出来原树高的范围),这一推论由property3,4得出,也是决定R_B tree得到广泛运用的关键所在。

    Insert&Delete

    对R-B tree的插入与删除,需要调整树结构。整体分为三大步骤:

    • 找到插入位置,着色为红色;
    • 对父节点与祖父节点重新着色;
    • 对子树进行旋转调整;

    伪代码

    pseudocode.png

    3 cases

    • case1


      case1.png
    • case2 ---> case3


      case2.png
    • case3


      case3.png

    time complexity

    各种时间复杂度同 2-3-4 tree 为:O(log n)

    总结

    summary

    Refer:

    相关文章

      网友评论

          本文标题:Red-Black tree and B-tree

          本文链接:https://www.haomeiwen.com/subject/ezpyhctx.html