二叉树查询时间复杂度_二叉查找树的时间复杂度

九大查找算法 　　时间、空间复杂度比较 　　查找算法平均时间复杂度空间复杂度查找条件顺序查找O(n)O(1)无序或有序二分查找（折半查找）O(log2n)O(1)有序插值查找O(log2(log2n))O(1)有序斐波那契查找O(log2n)O(1)有序哈希查找O(1)O(n)无序或有序二叉查找树（二叉搜索树查找）O(log2n) 　　红黑树O(log2n) 　　2-3树O(log2n – log3n) 　　B树/B+树O(log2n) 　　1 顺序查找 　　算法思路： 　　对于任意一个序列，从一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。 　　代码： 　　运行结果：



　　2 二分查找（折半查找） 　　算法思路：确定查找范围low=0，high=N-1，计算中项mid=（low+high）/2。若mid==x或low>=high,则结束查找；否则，向下继续。若amid<x,说明待查找的素值只可能在比中项素大的范围内，则把mid+1的值赋给low，并重新计算mid，转去执行步骤2；若mid>x，说明待查找的素值只可能在比中项素小的范围内，则把mid-1的值赋给higt，并重新计算mid，转去执行步骤2。 　　说明：查找素必须是有序的，如果是无序的则要先进行排序操作。在做查找的过程中，如果 low 指针和 high 指针的中间位置在计算时位于两个关键字中间，即求得 mid 的位置不是整数，需要统一做取整操作。折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。——《大话数据结构》 　　代码： 　　运行结果：

查找成功

没有查找到 　　3 插值查找 　　插值查找基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找 　　算法思路：确定查找范围low=0，high=N-1，计算中项mid=low+(key-a[low])/(a[high]-a[low])*(high-low)。若mid==x或low>=high,则结束查找；否则，向下继续。若amid<x,说明待查找的素值只可能在比中项素大的范围内，则把mid+1的值赋给low，并重新计算mid，转去执行步骤2；若mid>x，说明待查找的素值只可能在比中项素小的范围内，则把mid-1的值赋给higt，并重新计算mid，转去执行步骤2。 　　说明：插值查找是基于折半查找进行了优化的查找方法。当表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能要比折半查找要好得多。 　　代码： 　　运行结果：

运行结果 　　4 斐波那契查找 　　斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1；开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1). 　　算法思路：相等，mid位置的素即为所求大于，low=mid+1,k-=2;小于，high=mid-1,k-=1。 　　说明： 　　low=mid+1说明待查找的素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。 　　代码： 　　运行结果：

47的位置为5 　　5 哈希查找 　　哈希表： 　　我们使用一个下标范围比较大的数组来存储素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单来存储这个素；也可以简单的理解为，按照关键字为每一个素”分类”，然后将这个素存储在相应”类”所对应的地方。但是，不能够保证每个素的关键字与函数值是一一对应的，因此极有可能出现对于不同的素，却计算出了相同的函数值，这样就产生了”冲突”，换句话说，就是把不同的素分在了相同的”类”之中。后面我们将看到一种解决”冲突”的简便做法。 　　”直接定址”与”解决冲突”是哈希表的两大特点。 　　哈希函数： 　　规则：通过某种转换关系，使关键字适度的分散到指定大小的的顺序结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高。 　　算法思路： 　　如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。用给定的哈希函数构造哈希表；根据选择的冲突处理方法(常见方法：拉链法和线性探测法)解决地址冲突；在哈希表的基础上执行哈希查找； 　　代码： 　　6 二叉树查找 　　二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。 　　算法思路：若b是空树，则搜索失败：若x等于b的根节点的数据域之值，则查找成功：若x小于b的根节点的数据域之值，则搜索左子树：查找右子树。 　　代码： 　　递归和非递归 　　7 2-3树 　　2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key，2-3查找树的定义如下：要么为空，要么：对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key要小，右节点也是一个2-3节点，所有的值比key要大。对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。左节点也是一个2-3节点，所有的值均比两个key中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个跟节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个key中的最大的key还要大。

　　算法思路: 　　要判断一个键是否在树中，我们先将它和根结点中的键比较。如果它和其中的任何一个相等，查找命中。否则我们就根据比较的结果找到指向相应区间的链接，并在其指向的子树中递归地继续查找。如果这是个空链接，查找未命中。



　　代码： 　　8 红黑树 　　2-3查找树能保证在插入素之后能保持树的平衡状态，最坏情况下即所有的子节点都是2-node，树的高度为lgn，从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂，于是就有了一种简单实现2-3树的数据结构，即红黑树（Red-Black Tree）。 　　理解红黑树一句话就够了：红黑树就是用红链接表示3-结点的2-3树。 　　现在我们对2-3树进行改造，改造成一个二叉树。怎么改造呢？对于2节点，保持不变；对于3节点，我们首先将3节点中左侧的素标记为红色，然后我们将其改造成图3的形式； 　　再将3节点的位于中间的子节点的父节点设置为父节点中那个红色的节点，如图4的所示；最后我们将图4的形式改为二叉树的样子，如图5所示。图5是不是很熟悉，没错，这就是我们常常提到的大名鼎鼎的红黑树了。如下图所示。

　　为什么使用红黑树：红黑树是一种平衡树，他复杂的定义和规则都是为了保证树的平衡性。如果树不保证他的平衡性就是下图：很显然这就变成一个链表了。保证平衡性的最大的目的就是降低树的高度，因为树的查找性能取决于树的高度。所以树的高度越低搜索的效率越高！这也是为什么存在二叉树、搜索二叉树等，各类树的目的。 　　红黑树性质：每个节点要么是黑色，要么是红色。根节点是黑色。每个叶子节点（NIL）是黑色。每个红色结点的两个子结点一定都是黑色。任意一结点到每个叶子结点的路径都包含数量相同的黑结点。 　　算法思路： 　　红黑树的思想就是对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型，红色链接，他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的，使用红色链接的两个2-nodes来表示一个3-nodes节点，并且向左倾斜，即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改，和普通的二叉查找树相同。 　　代码： 　　9 B树/B+树 　　在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。——维基百科 　　B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。定义任意非叶子结点最多只有M个儿子；且M>2；根结点的儿子数为[2, M]；除根结点以外的非叶子结点的儿子数为[M/2, M]；每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的 子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；所有叶子结点位于同一层； 　　如：（M=3）

　　算法思路： 　　从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；关键字集合分布在整颗树中；任何一个关键字出现且只出现在一个结点中；搜索有可能在非叶子结点结束；其搜索性能等价于在关键字全集内做一次二分查找；自动层次控制； 　　代码： 　　B+树： 　　B+树是B树的变体，也是一种多路搜索树： 　　其定义基本与B-树同，除了：非叶子结点的子树指针与关键字个数相同；非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树, B树是开区间为所有叶子结点增加一个链指针;所有关键字都在叶子结点出现； 　　如:（M=3）

　　算法思路： 　　B+的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在 非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；不可能在非叶子结点命中；非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；更适合文件索引系统； 　　参考资料 　　https://www.sohu.com/a/296278527_478315https://www.cnblogs.com/exzlc/p/12203744.html部分配图来源于网络 　　最近原创推荐 　　如何定义一个只能在(堆/栈)上生成对象的类 　　十大经典排序算法(动态演示+代码) 　　C语言与C++面试知识总结数据结构之堆栈 　　一文轻松理解内存对齐 　　一文读懂C语言与C++动态内存 　　面试中常见的C语言与C++区别的问题 　　数据结构之线性表