查找

5 篇

数据结构与算法(十九)——散列表

定义

如果所有的键都是小整数,可以用一个数组来实现无序的符号表,将键作为数组的索引而数组中键i处所储存的就是它对应的值。这样我们就可以快速访问任意键的值。

散列表是这种简易方法的扩展并能处理更加复杂的类型的键。我们需要用算术操作将键转化为数组的索引来访问数组中的键值对。

使用散列的查找算法分为两步。第一步是用散列函数将被查找的键转化为数组的一个索引。第二步是处理碰撞冲突的过程。

继续阅读

数据结构与算法(十八)——平衡查找树之红黑二叉查找树

定义

红黑二叉查找树是一种简单的数据结构,用来实现2-3树。

替换3-结点

红黑二叉查找树背后的基本思想是用标准的二叉查找树(完全由2-结点构成)和一些额外的信息(替换3-结点)来表示2-3树。

我们将树中的链接分为两种类型,红链接将两个2-结点连起来构成一个3-结点,黑链接则是2-3树中的普通链接。

继续阅读

数据结构与算法(十七)——平衡查找树之2-3查找树

定义

二叉查找树在最快的情况下,性能还是很糟糕。

我们希望能够保持二叉查找树的平衡性。在一棵还有N个结点的树中,我们希望树的高度为logN,这样就能够保证所有的查找都能在logN次比较内结束。

2-3查找树允许树中的一个结点保存多个键。我们将一棵标准的二叉查找树中的结点称为2-结点(含有一个键和两条链接),现在引入3-结点,它含有两个键和三条链接。2-结点和3-结点中的每条链接都对应着其中保存的键所分割产生的一个区间。

继续阅读