美文网首页
二分查找、红黑树、B-树、B+树

二分查找、红黑树、B-树、B+树

作者: 永远的太阳0123 | 来源:发表于2018-09-24 12:02 被阅读0次

1.二分查找

    public static int BinarySearch(int arr[], int value, int length) {
        int low = 0;
        int high = length - 1;
        int mid;
        while (low <= high) {
            mid = (low + high) / 2;
            if (arr[mid] == value)
                return mid;
            else if (arr[mid] > value)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
    }

2.红黑树
红黑树是一种自平衡二叉查找树。
除了二叉查找树的一般要求,红黑树还有如下的额外要求:
(1)结点是红色或黑色的。
(2)根结点是黑色的。
(3)所有叶结点是黑色的空结点。
(4)每个红色结点的两个子结点都是黑色的。
(5)从任一结点到其每个叶子结点的路径包含相同数量的黑色结点。
性质:从根结点到叶子结点的最长路径不超过最短路径的2倍。例如根结点-黑色结点-叶结点,最短路径为2;根结点-红色结点-黑色结点-红色结点-叶结点,最长路径为4。


3.B树
B树是一种平衡的多路查找树。
一棵m阶的B树需要满足的特性:
(1)根结点的子结点数范围为2 ~ m个。
(2)除根结点、叶结点以外的结点的子结点数范围为⌈m/2⌉ ~ m个。
(3)叶结点在同一层,有(⌈m/2⌉-1) ~ (m-1)个关键字(所有非根结点的性质);根结点有1 ~ (m-1)个关键字。
(4)有k个子结点的结点中含有k-1个关键字。


4.B+树
一棵m阶的B+树和m阶的B树的差异:
(1)有n个子结点的结点中含有n个关键字,
(2)所有叶子结点包含了全部关键字信息及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序连接。
(3)所有非叶子结点可以看成是索引部分,结点中仅含有其子树中的最大(或最小)关键字。
通常在B+树上有两个头指针,一个指向根结点,另一个指向关键字最小的叶子结点。因此可以对B+树进行两种查找运算:一种是从最小关键字开始进行顺序查找,另一种是从根结点开始进行随机查找。


相关文章

  • MySQL为什么使用B+树而不是B-树?

    B-树、B+树、红黑树都是平衡查找树,从查询效率上讲,平均都是O(log n)。 但为什么MySQL使用B+树,而...

  • 不可多得的后端架构师技术图谱!内附参考资料!

    数据结构 二叉树 完全二叉树 平衡二叉树 二叉查找树(BST) 红黑树 B-,B+,B*树 LSM 树 队列 集合...

  • 树-二叉搜索树-平衡二叉树-红黑树-B树B+树

    关于树的总结从二叉树->二叉搜索树->平衡二叉树->红黑树->B树与B+树 B+树介绍 B树、B-树、B+树、B*...

  • 二分查找、红黑树、B-树、B+树

    1.二分查找 2.红黑树红黑树是一种自平衡二叉查找树。除了二叉查找树的一般要求,红黑树还有如下的额外要求:(1)结...

  • B 树、B+ 树、B* 树谈到R 树

    第一节、B树、B+树、B*树 1.前言动态查找树主要有:二叉查找树,平衡二叉查找树,红黑树,B树/B+树/ B*树...

  • 后端架构师技术图谱

    数据结构队列集合链表、数组字典、关联数组栈树二叉树完全二叉树平衡二叉树二叉查找树(BST)红黑树B-,B+,B*树...

  • 后端架构师技术图谱(一)

    数据结构队列集合链表、数组字典、关联数组栈树二叉树完全二叉树平衡二叉树二叉查找树(BST)红黑树B-,B+,B*树...

  • 数据结构之BBST

    目录: 1.B-树与B+树2.红黑树 文章参考: 关于B-tree的科普文,很有趣什么是B-树? 关于B+树的科普...

  • B-树/B+树

    B-树(Balance树)和B+树应用与数据库索引,是m叉的多路平衡查找树。 1. 性质分析 1.1 M阶B-树 ...

  • 面试

    通过问数据库,联系到b+,b-树。通过set,问到红黑树。。我同学说的~~

网友评论

      本文标题:二分查找、红黑树、B-树、B+树

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