数据结构和算法总结

向右看齐 2022-05-19 07:27 142阅读 0赞

# 一、二叉查找树 #

也称有序二叉树，它是指一棵空树，或者满足以下性质的树：

*  若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 *  若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
 *  任意节点的左、右子树也分别为二叉查找树。
 *  没有键值相等的节点（no duplicate nodes）

二叉查找树的高度为lgn，时间复杂度为O(lgn)，最坏情况是退化成一条链表，时间复杂度O(n)

# 二、红黑树 #

二叉查找树，时间复杂度O(logn)(红黑树的高度至多为2log(n+1))。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。性质：

1.  每个结点要么是红的要么是黑的。  
2.  根结点是黑的。  
3.  每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。  
4.  如果一个结点是红的，那么它的两个儿子都是黑的。  
5.  对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点

![format_png][]

1.  通过对结点进行重新着色，以及对树进行相关的旋转操作，即通过修改树中某些结点的颜色及指针结构，来达到对红黑树进行插入或删除结点等操作后继续保持它的性质或平衡的目的。树的旋转分为左旋和右旋(插入最多两次旋转，删除最多三次旋转)
2.  红黑树的插入分为几个过程：1）将红黑树当作一颗二叉查找树，将节点插入；2）将节点着色为红色；3）通过旋转和重新着色等方法来修正该树，使之重新成为一颗红黑树

详情访问[https://blog.csdn.net/qq\_33314107/article/details/81106764][https_blog.csdn.net_qq_33314107_article_details_81106764]

# 三、B树和B+树 #

### B树： ###

B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化**大块数据的读和写操作**。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在**数据库**和**文件系统**。

**B 树**可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。

*  根节点至少有两个子节点
 *  每个节点有M-1个key，并且以升序排列
 *  位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
 *  其它节点至少有M/2个子节点

下图是一个M=4 阶的B树:

[![B tree][]][B tree 1]

### B+树： ###

**B+**树是对B树的一种变形树，它与B树的差异在于：

*  有k个子结点的结点必然有k个关键码；
 *  非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
 *  树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。

[![B Plus tree][]][B Plus tree 1]

B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。

B+ 树的优点在于：

*  由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
 *  B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速

详情访问[https://blog.csdn.net/qq\_33314107/article/details/81811551][https_blog.csdn.net_qq_33314107_article_details_81811551]

[format_png]: /images/20220519/5e24d2871e4a4adfacaf7eaf414e9aa0.png
[https_blog.csdn.net_qq_33314107_article_details_81106764]: https://blog.csdn.net/qq_33314107/article/details/81106764
[B tree]: /images/20220519/c77e5fab4be645b2b7ccbc6cc72b6ad8.png
[B tree 1]: https://images0.cnblogs.com/blog/94031/201403/290047034539184.png
[B Plus tree]: /images/20220519/66673ea92550426ab4aafe722171078d.png
[B Plus tree 1]: https://images0.cnblogs.com/blog/94031/201403/290050025784094.png
[https_blog.csdn.net_qq_33314107_article_details_81811551]: https://blog.csdn.net/qq_33314107/article/details/81811551