注:这里的堆还是以小根堆为例。   我们想要设计一种堆能像二叉堆那样高效地支持合并操作,也就是$O\left( n \right)$时间处理一次Merge,而且只使用一个数组看起来很困难对吧,毕竟合并操作需要把一个数组复制到另...
阅读(4) 评论(0)
二叉堆是一种典型的优先队列实现策略,广义而言,堆是优先队列的实现方式,在此之下又分为二叉堆,左式堆,斜堆,二项队列等具体形态。但第一个用得太普遍了,所以我们平时一说到堆(Heap)指的就是二叉堆。基本模型如下,基本操作就这两个,其他的都...
阅读(6) 评论(0)
最后我们来探究红黑树的删除算法,相比插入操作,它的情况更复杂一些。因此直接考虑很容易撞到南墙,我们更需要利用转化与化归的思想(还记得高中数学四大思想方法吧,这里一样适用),通过提升变化,把红黑树映射成一颗B-树,并站在后者的角度,反过来...
阅读(6) 评论(0)
首先说一下,关于红黑树有一篇很棒的论文《A dichromatic framework for balanced trees》,作者之一的Robert Sedgewick,想必大家不会陌生。如果有兴趣可以仔细研读一下,里面讲了更多细节的...
阅读(10) 评论(0)
红黑树是AVL树的另一变种,他也能在动态变化的过程中保持某种意义的平衡,对红黑树的操作最坏情况下也只有O(logN)的复杂度,而且下面我们会看到,对于插入而言我们有另外一种比AVL树更容易的实现方法,非递归的。在具体谈到技术细节之前,我...
阅读(14) 评论(0)
P.s:在代码里会同时用到向量和B-树的search,insert, remove,具体调用的是哪个结构的函数结合上下文就能看懂。   根据上一篇文章,我们对于这棵树的大致结构已经明了,那该如何有效利用并且根据情况维护它呢?这...
阅读(9) 评论(0)
Ps.我们遵循从感性到理性的认知顺序来逐步探索B-树的奥秘,之前经常说的value这里用key(关键码)指代,因为可能存的是字符串,说是value就不合适了。 (多图预警!!!建议在WI-FI下观看)  虽然迄今为止我们所看到...
阅读(10) 评论(0)
极端退化  前面所提到的二叉搜索树,已经为我们对数据集进行高效的静态和动态操作打开了一扇新的大门。正如我们所看到的,BST从策略上可以看作是将之前的向量(动态数组)和链表结构的优势结合起来,不过多少令我们有些失望的是:目...
阅读(53) 评论(0)