数据结构系列

B 树是为磁盘或其他直接存取的辅助存取设备而设计的一种多叉平衡搜索树，类似于红黑树，但 B 树在降低磁盘 I/O 操作方面要更好一些。许多数据库系统使用 B 树或 B 树的变种来存储信息。 我们知道，磁盘 I/O 是很慢的，因为要涉及到磁头寻道、定址和数据读取时间。寻道是一种机械运动，速度自然慢；定址的平均时间是磁盘旋…

当我们在使用二叉搜索树时，如果树的高度较高，对其的操作并不比对链表操作要快。原因是二叉搜索树在插入顺序基本有序时会退化为一个排序链表，所以说是不平衡的。 对二叉搜索树的改进有 AVL 树和红黑树。先来看红黑树，它广泛应用在 STL 的 set 和 map，Java 库和 Linux 内核中。 红黑树是一颗平衡的二叉搜索…

上一篇文章实现了一个最简单的二叉搜索树，里面有两个成员函数：插入和中序遍历。我觉得，插入应该算是 BSTree 中最核心的一个函数了。 二叉搜索树虽然是一颗排序树，但当数据的插入顺序基本逆序时，BSTree 就退化为一个很近似链表的结构。而链表中查找的时间复杂度为 O(n)，显然这失去了二叉搜索树 O(lg N) 的优…

上一篇文章简单实现了一个普通的二叉树，参见[这里](/post/e660f1d5/30a3fd3d)。 二叉搜索树是二叉树的一种变体，它相比普通二叉树的特性就是里面的数据都是有序的，中序遍历它就可以得到一个升序数组。 BSTreet实现代码如下： 如果你有任何想法或是可以改进的地方，欢迎和我交流！ 完整代码及测试用例在…

众所周知，二叉树是一种很重要的数据结构，基于二叉树的哈夫曼树可用于文件压缩，BSTreet、AVLTree 可用于排序，RBTree 被广泛用在 STL 中的 map、set 等容器上和 Java 中的 TreeSet 和 TreeMap 上。 二叉树的节点结构： 应用于二叉树的方法主要有：前中后序遍历(递归/非递归)…

哈希算法可以说是效率比较高的一种算法了，基本上时间复杂度为 O(1)。但哈希有个坑爹的地方就是碰撞问题。当发生冲突时，有两种解决办法： 线性探测 哈希桶法 具体算法不再解释，以下代码使用 STL 中 vector 和 list 实现了一个基于哈希桶的哈希表。 代码如下： 如果你有任何想法或是可以改进的地方，欢迎和我交流…

一个双向队列,底层使用 list 实现，因为 list 在 push\_back，push\_front，pop\_back，pop\_front 这些函数中效率较高。 如果你有任何想法或是可以改进的地方，欢迎和我交流！ 完整代码及测试用例在 github 上：[点我前往](https://github.com/Sma…

stack 的特性不用多说了吧，先进后出。底层可以用 vector 或 list 实现。 如果你有任何想法或是可以改进的地方，欢迎和我交流！ 完整代码及测试用例在 github 上：[点我前往](https://github.com/SmartBrave/DataStruct/tree/master/Stack) )

以下代码实现了一个堆，可以传入仿函数来决定生成最大堆或最小堆。 如果你有任何想法或是可以改进的地方，欢迎和我交流！ 完整代码及测试用例在 github 上：[点我前往](https://github.com/SmartBrave/DataStruct/tree/master/Heap) )

list 和 vector 是 STL 库中两个最基本的容器，以下代码模拟实现一个简单的 list： 如果你有任何想法或是可以改进的地方，欢迎和我交流！ 完整代码及测试用例在 github 上：[点我前往](https://github.com/SmartBrave/DataStruct/tree/master/Lis…

众所周知，STL 库以高效而闻名。而且使用它可以很方便的实现我们的主要逻辑，不需要关心各种底层的实现细节。本文模拟实现了一个简单的 vector 容器。关于 vector 的介绍请移步：[浅谈STL](/post/cf4cc8e2/e667fb74) 代码如下： 如果你有任何想法或是可以改进的地方，欢迎和我交流！ 完整…