开发面试题之二分查找、红黑树、B-树、B+树

二分查找算法

二分查找又称折半查找，它是一种效率较高的查找方法。

二分查找要求：（1）必须采用顺序存储结构 （2）必须按关键字大小有序排列

原理：将数组分为三部分，依次是中值前，中值（所谓的中值就是数组中间位置的那个值），中值后；将要查找的值和数组的中值进行比较，若小于中值则在中值前面找，若大于中值则在中值后面找，等于中值时直接返回。然后依次是一个递归过程，将前半部分或者后半部分继续分解为三部分。

实现：二分查找的实现用递归和循环两种方式。

package com.company.datastructure;

public class BinarySearchDemo {

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;

}

public static void main(String[] args) {

int target = 66;

int arr[] = {1,2,3,9,22,33,44,55,66,77,88,99,100};

int result = BinarySearch(arr, target, arr.length);

System.out.println(“Result: “ + result);

}

}

时间复杂度

采用的是分治策略。

最坏的情况下两种方式时间复杂度一样：O(log2 N)

最好情况下为O（1）。

空间复杂度

算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数。

非递归方式：

由于辅助空间是常数级别的所以：空间复杂度是O(1);

递归方式：

递归的次数和深度都是log2 N，每次所需要的辅助空间都是常数级别的：

空间复杂度：O(log2N )

红黑树

红黑树是一种自平衡二叉查找树。

除了二叉查找树的一般要求，红黑树还有如下的额外要求：

（1）结点是红色或黑色的。

（2）根结点是黑色的。

（3）所有叶结点是黑色的空结点。

（4）每个红色结点的两个子结点都是黑色的。

（5）从任一结点到其每个叶子结点的路径包含相同数量的黑色结点。

性质：从根结点到叶子结点的最长路径不超过最短路径的2倍。例如根结点-黑色结点-叶结点，最短路径为2；根结点-红色结点-黑色结点-红色结点-叶结点，最长路径为4。

B-树

B-树是一种平衡的多路查找树。

一棵m阶的B树需要满足的特性：

（1）根结点的子结点数范围为2 ~ m个。

（2）除根结点、叶结点以外的结点的子结点数范围为?m/2? ~ m个。

（3）叶结点在同一层，有(?m/2?-1) ~ (m-1)个关键字（所有非根结点的性质）；根结点有1 ~ (m-1)个关键字。

（4）有k个子结点的结点中含有k-1个关键字。

B+树

一棵m阶的B+树和m阶的B树的差异：

（1）有n个子结点的结点中含有n个关键字。

（2）所有叶子结点包含了全部关键字信息及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序连接。

（3）所有非叶子结点可以看成是索引部分，结点中仅含有其子树中的最大（或最小）关键字。

通常在B+树上有两个头指针，一个指向根结点，另一个指向关键字最小的叶子结点。

因此可以对B+树进行两种查找运算：一种是从最小关键字开始进行顺序查找，另一种是从根结点开始进行随机查找。

小结

所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；