红黑树和二叉排序树的关系是什么_红黑树和二叉排序树的关系是什么意思

搜索查找相关树：二叉排序树，平衡二叉树，红黑树，B树，B+树，哈希树，Trie树（字典树），KD树 　　树是一种基础而实用的数据结构。 　　目录二叉树相关概念二叉排序树平衡二叉树红黑树B树B+树哈希树字典树 Trie树KD树 　　二叉树相关概念 　　二叉树是每个结点最多有两个子树的树结构。 　　度为 2 的树要求每个节点最多只能有两棵子树，并且至少有一个节点有两棵子树。二叉树的要求是度不超过 2，就是说度也可以是 1 或者 0。二叉树还有一个重要特点，是左子树和右子树不一样；普通的树不分左右子树。 　　另外树的根节点数目可以是0或1，也就是可以有0个结点。而二叉树的根节点有且只有一个。这个是互相矛盾的，但是就是这么规定的。一些概念题可能会考到。 　　二叉排序树 　　二叉排序树，又叫二叉查找树，它或者是一棵空树；或者是具有以下性质的二叉树： 　　1.若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 　　2.若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 　　3.它的左右子树也分别为二叉排序树。 　　如下图所示： 　　
　　查找性能方面：最坏情况下，当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度为数组长度，其平均查找长度(n+1)/2和顺序查找相同；最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log_2n成正比。 　　二叉搜索树的插入和删除可以参考算法与数据结构(十) 二叉排序树的查找、插入与删除。 　　二叉排序树的中序遍历可以得到素的有序数组。 　　平衡二叉树 　　平衡二叉树，又称AVL树、平衡二叉排序树，它是一种特殊的二叉排序树。AVL树或者是一棵空树，或者是具有以下性质的二叉树： 　　1.左子树和右子树都是平衡二叉树； 　　2.左子树和右子树的深度（高度）之差的绝对值不超过1。 　　
　　其实就是平衡的二叉排序树，且每个子树都是平衡二叉排序树。这样，平衡二叉树的查找时间复杂度可以保证在O(logn)。 　　关于平衡二叉树失衡的调整——旋转： 　　旋转操作主要包括LL（左左）旋转、LR（左右）旋转、RR（右右）旋转、RL（右左）旋转，LL旋转与RR旋转对称，LR旋转与RL旋转对称。旋转操作是在插入结点或删除结点导致原AVL树不平衡时进行的。我的理解是当二叉树失衡的原因出现在“最低失衡根结点左子树的左子树”（所谓“最低失衡根结点”，则是从新增结点开始向根部回溯，所遇到的第一个失衡的根节点）时，则使用LL旋转来调整；当失衡出现在“最低失衡根节点左子树的右子树”，则使用LR旋转调整；RR旋转，RL旋转同理。 　　LL旋转即“最低失衡根节点”左子树的左子树上的节点导致失衡（又叫R旋转：让目标节点变成右孩子）。对应旋转方法：将“最低失衡根节点”左孩子作为新根节点；根节点作为新根节点右孩子；新根节点本来的右孩子作为根节点左孩子。 　　RR旋转即“最低失衡根节点”右子树的右子树上的节点导致失衡（又叫L旋转：让目标节点变成左孩子）。对应旋转方法：将“最低失衡根节点”右孩子作为新根节点；根节点作为新根节点左孩子；新根节点本来的左孩子作为根节点右孩子。 　　LR旋转即“最低失衡根节点”左子树的右子树上的节点导致失衡，需要两次旋转：对“最低失衡根节点”左孩子进行RR旋转；对“最低失衡根节点”进行LL旋转。 　　RL对称。具体流程以及代码可以参考：平衡二叉树。 　　红黑树 　　红黑树是一棵二叉搜索树，它在每个结点上增加了一个存储位来表示结点的颜色，可以是RED或者BLACK。通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束，红黑树可以确保没有一条路径会比其他路径长出2倍，因而是近似平衡的。 　　红黑树满足红黑性质： 　　1.每个节点是红色或者黑色的 　　2.根节点是黑色的，叶节点（NIL）是黑色的 　　3.红色节点的两个子节点都是黑色的 　　4.对每个结点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。（因为所有路径的黑色节点相同，且红色节点的子节点必然是黑色，于是最长的路径中，是红黑相间的(2n-1)，最短路径是纯黑大的，差为(n-1)，小于n，故没有一条路径会比其他路径长出2倍）。 　　红黑树的插入和删除时间复杂度都在O(logn)。 　　具体可以参考：看这篇得到红黑树插入的整体结构 看这篇的“红叔”部分讲解，其他有错。 　　稍稍总结一下： 　　红黑树的插入分为一下情况： 　　–黑父： 直接插入 　　–红父 　　—红叔： 向上变黑 　　—黑叔： 看结构，和AVL四种旋转基本相同。 　　红黑树的删除可以参考。 　　红黑树和AVL平衡二叉树的区别： 红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。 平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。 　　B树 　　我们都知道二叉查找树的查找的时间复杂度是Ｏ(log N)，其查找效率已经足够高了，那为什么还有Ｂ树和Ｂ＋树的出现呢？难道它两的时间复杂度比二叉查找树还小吗？ 　　答案当然不是，Ｂ树和Ｂ＋树的出现是因为另外一个问题，那就是磁盘ＩＯ；众所周知，ＩＯ操作的效率很低，那么，当在大量数据存储中，查询时我们不能一下子将所有数据加载到内存中，只能逐一加载磁盘页，每个磁盘页对应树的节点。造成大量磁盘ＩＯ操作（最坏情况下为树的高度）。平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。 　　所以，我们为了减少磁盘ＩＯ的次数，就你必须降低树的深度，将“瘦高”的树变得“矮胖”。一个基本的想法就是： 　　（1）、每个节点存储多个素 　　（2）、摒弃二叉树结构，采用多叉树 　　这样就引出来了一个新的查找树结构 ——多路查找树。 根据AVL给我们的启发，一颗平衡多路查找树(B~树)自然可以使得数据的查找效率保证在O(logN)这样的对数级别上。 　　一个m阶的B树（Balance Tree）具有如下几个特征：B树中所有结点的孩子结点最大值称为B树的阶，通常用m表示。一个结点有k个孩子时，必有k-1个关键字才能将子树中所有关键字划分为k个子集。 　　1.根结点至少有两个子女。 　　2.每个中间节点都包含k-1个素和k个孩子，其中 ceil（m/2） ≤ k ≤ m 　　3.每一个叶子节点都包含k-1个素，其中 ceil（m/2） ≤ k ≤ m 　　4.所有的叶子结点都位于同一层。 　　5.每个节点中的素从小到大排列，节点当中k-1个素正好是k个孩子包含的素的值域划分 　　6.每个结点的结构为：（n，A0，K1，A1，K2，A2，… ，Kn，An） 　　其中，Ki(1≤i≤n)为关键字，且Ki<Ki+1(1≤i≤n-1)。 　　Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki+1。 　　n为结点中关键字的个数，满足ceil(m/2)-1≤n≤m-1。 　　
　　查询 　　以上图为例：若查询的数值为５： 　　第一次磁盘ＩＯ：在内存中定位（与17、35比较），比17小，左子树； 　　第二次磁盘ＩＯ：在内存中定位（与８、12比较），比８小，左子树； 　　第三次磁盘ＩＯ：在内存中定位（与3、5比较），找到5，终止。 　　插入 　　整个过程中，我们可以看出：比较的次数并不比二叉查找树少，尤其适当某一节点中的数据很多时，但是磁盘IO的次数却是大大减少。比较是在内存中进行的，相比于磁盘IO的速度，比较的耗时几乎可以忽略。所以当树的高度足够低的话，就可以极大的提高效率。相比之下，节点中的素多点也没关系，仅仅是多了几次内存交互而已，只要不超过磁盘页的大小即可。 　　对高度为ｋ的m阶B树，新结点一般是插在叶子层。通过检索可以确定关键码应插入的结点位置。然后分两种情况讨论： 　　1、 若该结点中关键码个数小于m-1，则直接插入即可。 　　2、 若该结点中关键码个数等于m-1，则将引起结点的分裂。以中间关键码为界将结点一分为二，产生一个新结点，并把中间关键码插入到父结点(ｋ-1层)中 　　重复上述工作，最坏情况一直分裂到根结点，建立一个新的根结点，整个B树增加一层。 　　
　　
　　如图就是在一个二阶B树中插入4的过程，35，26节点依次分裂。 　　删除 　　B树的删除较为复杂，具体参考B树和B+树的插入、删除图文详解或简单剖析B树。 　　总结一下，B树B+树的插入：可以插（插完仍满足定义要求）直接插；不可插（插完节点太大），分裂向上调整，中值作为分裂子树的根节点，归入父节点，若归入后父节点不满足定义，递归此过程。 　　删除：可以删（删完仍满足定义要求）直接删；删完节点过小(k<[m/2]-1)，先从左右兄弟找结点，不然从父节点找结点向下调整，若调整完父节点不满足定义，递归此过程。 　　B+树也一样，不过更简单一些，只需在叶子节点进行操作。 　　应用 　　1.B树主要用于文件系统以及部分数据库索引，例如： MongoDB。而大部分关系数据库则使用B+树做索引，例如：mysql数据库； 　　2.从查找效率考虑一般要求B树的阶数m >= 3; 　　3.B-树上算法的执行时间主要由读、写磁盘的次数来决定，故一次I/O操作应读写尽可能多的信息。因此B-树的结点规模一般以一个磁盘页为单位。一个结点包含的关键字及其孩子个数取决于磁盘页的大小。 　　B+树 　　Ｂ＋树是Ｂ树的变种，有着比Ｂ树更高的查询效率。一个m阶的B+树具有如下几个特征： 　　1.有k个子树的中间节点包含有k个素（B树中是k-1个素），每个素不保存数据，只用来索引，所有数据都保存在叶子节点。 　　2.所有的叶子结点中包含了全部素的信息，及指向含这些素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。 　　3.所有的中间节点素都同时存在于子节点，在子节点素中是最大（或最小）素。 　　4.B+树中，叶子素指向对应素以及该索引下其他相关素，且这些素之间按顺序有链式指针链接起来。（下图中，5->8->9->10->15->18->…->96->99） 　　
　　
　　B+树的优势在于查找效率上， 首先，Ｂ＋树的查找和Ｂ树一样，类似于二叉查找树。起始于根节点，自顶向下遍历树，选择其分离值在要查找值的任意一边的子指针。在节点内部典型的使用是二分查找来确定这个位置。 　　不同的是，Ｂ＋树中间节点没有卫星数据（索引素所指向的数据记录），只有索引，而Ｂ树每个结点中的每个关键字都有卫星数据；这就意味着同样的大小的磁盘页可以容纳更多节点素，在相同的数据量下，Ｂ＋树更加“矮胖”，IO操作更少 ； 其次，因为卫星数据的不同，导致查询过程也不同。Ｂ树的查找只需找到匹配素即可，最好情况下查找到根节点，最坏情况下查找到叶子结点，所说性能很不稳定，而Ｂ＋树每次必须查找到叶子结点，性能稳定； 最后，在范围查询方面，所有叶子节点形成有序链表，便于范围查询，B+树的优势更加明显。 　　B树的范围查找需要不断依赖中序遍历。首先二分查找到范围下限，在不断通过中序遍历，知道查找到范围的上限即可。整个过程比较耗时。 而B+树的范围查找则简单了许多。首先通过二分查找，找到范围下限，然后同过叶子结点的链表顺序遍历，直至找到上限即可，整个过程简单许多，效率也比较高。 　　例如：同样查找范围[3-11]，两者的查询过程如下： 　　B树的查找过程： 　　
　　B+树的查找过程： 　　
　　插入和删除和B树类似。 　　哈希树 　　质数分辨定理：n个不同的质数能够“分辨”的连续整数的个数和他们的乘积相等。“分辨”就是指这些连续的整数不可能有全然同样的余数序列。 　　比如，质数（=2310）可以分辨[1,2310]的所有数。质数2511(=110)可以分辨[1,110]的所有数。 　　哈希树就可以利用质数分辨定理来建树。 　　选择从2开始的连续质数来建立一个十层的哈希树。第一层结点为根结点。根结点（对应质数2）下有2个结点；第二层（对应质数3）的每一个结点下有3个结点；第三层（对应质数5）的每一个结点下有5个结点。依此类推，即每层结点的子节点数目为连续的质数。到第十层，每一个结点下有29个结点。 　　同一结点中的子结点。从左到右代表不同的余数结果。比如：第二层结点下有三个子节点。那么从左到右分别代表：除3余0，除3余1。除3余2. 　　对质数进行取余操作得到的余数决定了处理的路径。比如我们以随机的10个数的插入为例，来图解HashTree的插入过程： 　　
　　有读者可能有疑问，假设一直冲突下去怎么办？首先，若关键词们是整型。我们的10层哈希树全然能够分辨出来它们，这是质数分辨算法决定的。 　　我们事实上也能够把全部的键-值节点放在哈希树的第10层叶节点处，这第10层的满节点数就包括了全部的整数个数。可是假设这样处理的话，全部的非叶子节点作为键-值节点的索引，这样使树结构庞大，浪费空间。 　　哈希树的查找可以在O(树深)复杂度内完成。删除则只需先查到到要删除的节点，然后把此节点的“占位标记”置为false就可以（即表示此节点为空节点。但并不进行物理删除）。 　　哈希树结构简单，查找迅速，结构不变不用担心“退化”问题，所以也无需想平衡树一样加入各种复杂的旋转操作。 　　具体可以参考查找——图文翔解HashTree（哈希树）。 　　字典树 Trie树 　　字典树，又称为单词查找树，Tire数，是一种树形结构，它是一种哈希树的变种。 　　
　　字典树满足： 　　1.根节点不包含字符，除根节点外的每一个子节点都包含一个字符 　　2.从根节点到某一节点。路径上经过的字符连接起来，就是该节点对应的字符串 　　3.每个节点的所有子节点包含的字符都不相同 　　字典树的典型应用是用于统计，排序和保存大量的字符串(不仅限于字符串)，经常被搜索引擎系统用于文本词频统计。 　　利用字符串的公共前缀来减少查询时间，最大限度的减少无谓的字符串比较，查询效率比哈希树高。 　　Trie树的实现可以参考字典树(Trie树)实现与应用 　　KD树 　　k-d tree即k-dimensional tree，常用来作空间划分及近邻搜索，是二叉空间划分树的一个特例。 　　具体可以参考k-d tree算法原理及实现和KD树