普林斯顿《算法》笔记(三)

  • 时间:
  • 浏览:0
  • 来源:万人红黑大战棋牌APP_万人红黑大战棋牌APP官网

这份实现的核心在于rank()法子,它返回表中小于给定键的键的数量。以下是递归版本的代码:

红黑树的性质

散列表和平衡查找树的比较:

2、红黑二叉查找树 (Red Black BST)

下表列出了符号表的典型应用:

Selection操作是要找到排名为k的键 (即树中正好有k个小于它的键)。

put() 法子还需要保证数组中Comparable 类型的键有序,具体是使用rank() 法子得到键的具体位置,要是将所有更大的键向后移动一格来腾出位置并插入新的键值。

键的等价性

要支持高效的插入操作,需要三种链式形态学 ,但单链表是无法使用binary search的,机会binary search的高效性来源于要能通过索引快速取得任何子数组的里边元素 (但得到一根绳子 链表的里边元素的唯一法子是沿链表遍历)。下一节的二叉查找树 (binary search tree)还需要将binary search的效率单位和链表的灵活性结合起来。下表是本章各种符号表实现的优缺点概览:

给定表M,地处函数f(key),对任意给定的键 (key),代入函数后若能得到所含该关键字的记录在表中的地址(即索引),则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。

顺序查找通过get()法子会顺序地搜索链表查找给定的键,并返回相应的值;put() 法子同样顺序地搜索给定的键,机会找到则更新相关联的值,要是创建一2个多新结点并将其插入到链表的开头。

3.2.7 删除操作

二叉查找树要能保持键的有序性,要是它还需要作为实现有序符号表中众多法子的基础。

有序符号表 (Ordered symbol tables)

红黑树的红链接(red link) 将一2个多2- 结点连接起来构成一2个多3- 结点,黑链接则是2-3 树的普通链接。红黑树满足以下条件:

下列FrequencyCounter 用例统计了标准输入中各个单词的老出频率,要是将频率最高的且不小于指定长度的单词打印出来。

3.2.2 插入

各符号表实现的比较

查找和各种插入操作

rank()select()的逆法子,返回给定键的排名。

这部分直接看图可比文字描述清晰多了。

典型的应用线程池池中,键全部就有Comparable对象,要是还需要用 a.compareTo(b) 来比较a和b一2个多键。然后就能通过Comparable接口带来的键的有序性来更好地实现put() 和 get() 法子,由此要能定义更多实用操作,如下表所示。一般若果见到类的声明中所含泛型变量 Key extends Comparable<Key>,则说明这段线程池池虽然实现这份API。

线性探测法是开放地址散列表的三种。先使用散列函数键在数组中的索引,检查其中的键和被查找的键不是相同。机会不同则继续查找 (将索引扩大,到达数组结尾时返回数组的开头),知道找到该键或遇到一2个多空元素。

这里约定空链接为黑色。

开放地址类散列表的核心思想是将内存作为散列表中的空元素,而全部就有将其当做链表,那先 空元素还需要作为查找现在刚开始的标志。下列实现中使用了并行数组,一根绳子 保存键,一根绳子 保存值。

颜色表示

/

基于拉链法(separate chaining) 的散列表

机会一2个多要能保存M个键值对的数组,就需要一2个多能将任意键转化为该数组范围内的索引([0, M-1])的散列函数。散列函数应具有一下特点:

删除操作:咋样线性探测表中删除一2个多键? 直接将该键所在的位置设为null是不行的,机会这会使得然后的元素无法被找到。可行的法子是将簇中被删除键右侧所有的键重新插入散列表。

符号表用例一:

基于线性探测法 (linear probing) 的散列表

3.3 平衡查找树 (Balanced Search Tree)

各种符号表实现的比较 2:

插入同样分三种具体情况:机会该键的结点在表中,则更新值;若不地处则增加新结点。

3.2.3 floor 和 ceiling

各种符号表实现的比较:

3.2 二叉查找树 (Binary Search Tree)

散列表(Hash table,也叫哈希表),是根据通过键(key) 直接进行访问值 (value)的数据形态学 。也要是说,它通过把键映射到表中一2个多位置来访问记录,以加快查找的效率单位。这俩 映射函数叫做散列函数,存放记录的数组叫做散列表。

范围查找主要通过将所有给定范围内的键加入队列 Queue 来实现。

3.2.8 范围查找 (range queries)

二叉查找树 (binary search tree):二叉查找树的每个结点所含一2个多Comparable键和一2个多值,且每个结点的键 (key)都大于其左子树中的任意结点的键而小于右子树的任意结点的键。是三种结合了链表插入的灵活性和有序数组查找的高效性的符号表实现。

将整数散列的最常用法子是除留余数法(modular hashing)。选折 大小为素数M的数组,对于任意正整数k,计算k除以M的余数。机会M全部就有素数,散列值机会无法均匀分布。

符号表用例二:

一2个多散列函数能将键转化为数组索引,散列算法的第二步是碰撞防止(collision resolution),也要是防止一2个多或多个键的散列值相同的具体情况。拉链法将大小为M的数组中的每个元素指向一根绳子 链表,链表的每个结点存储了其他键值对,同一根绳子 链表中键的散列值都一样,为该链表在散列表中的索引,如下图所示:

3.4 散列表 (Hash Table)

3.2.1 查找

二叉树 (binary tree):每个结点最多有一2个多子树的树形态学 。

3.1 符号表 (Symbol Tables)

符号表是三种存储键值对 (key-value pairs) 的数据形态学 ,其主要目的是将键 (key) 和值 (value) 联系起来。主要支持三种操作:插入 (put) ,即将一组新的键值对存入存入表中;查找 (get) ,即根据给定的键得到相应的值。

下图总结了将一2个多4- 结点分解为一颗2-3 树机会的6种具体情况。2-3 树插入算法的根本在于那先 变换全部就有局部的:除了相关的结点和链接外未必修改或检查树的其他部分。

实现散列表的另三种法子是用大小为M的数组保存N个键值对,其中M > N。让当我们歌词 歌词 需要依靠数组中的空位来防止碰撞冲突,基于这俩 策略的所有法子统称为开放地址(open addressing) 散列表。

无序链表中的顺序查找 (Sequential Search)

下图显示了2-3树的平衡性,对于升序插入10个键,二叉查找树会变成层厚为9,而2-3 树的层厚则为2 。

各种插入操作

一颗2-3查找树或为一颗空树,或由以下结点组成:

有序数组中的二分查找 (Binary Search)

这段代码会将符号位(sign bit)屏蔽(将一2个多32位整数变为一2个多31位非负整数),要是计算它除以M的余数。

Java中所有数据类型都继承一2个多 hashCode() 法子,能返回一2个多32位整数。每三种数据类型的hashCode()法子需要与equals()是一致的。机会 a.equals(b),没办法 a.hashCode()的返回值与b.hashCode()的返回值需要是一致的。机会一2个多对象的hashCode()法子的返回值不同,没办法 这俩 2个多对象是不同的。机会一2个多对象的hashCode()法子的返回值相同,这俩 2个多对象也机会不同,还需要equals()法子判断。

那先 局部变换不需要影响树的全局有序性和平衡性:任意空链接到根结点的路径长度全部就有相等的。以下图举例,变换前根结点到所有空链接的路径长度为h,变换后仍然为h。要能当根结点被分解为三个白2- 结点时,路径长度才会加1。

3.2.4 Selection

3.2.5 Rank

下列实现使用一2个多数组分别保存key 和 value,然后的数据形态学 是一对平行的数组。需要创建一2个多Key类型的Comparable对象的数组和一2个多Value 类型的Object对象的数组,并在构造函数中将它们转化为Key[]Value[]

hashCode() 的返回值转化为一2个多数组索引: 机会需要的是数组索引而全部就有一2个多32位整数,要是在实现中会将默认的hashCode()法子和除留余数法结合起来产生一2个多0到M-1的整数:

符号表是三种典型的抽象数据类型,它代表一组清晰定义的值以及对那先 值相应的操作, 使得让当我们歌词 歌词 要能将类型的实现和使用区别开来。下图是三种泛型符号表API:

要实现要能返回给定范围内键的keys法子,首太难对二叉树进行中序遍历 (inorder traversal)。如下所示:

散列函数

查找分为三种具体情况:机会所含该键的结点地处表中,则返回相应的值;若不地处则返回null。

一同将指向一颗空树的链接成为空链接 (null link)。

旋转

所有插入步骤都还需要归结为一下三种操作:

1、 2-3查找树

3.2.6 删除最大键和删除最小键

在Java中所有对象都继承了一2个多 equals() 法子,Java也为其标准数据类型如Integer、Double和String以及其他其他更加简化的类型,如File和URL,实现了 equals() 法子。机会是自定义的键则需要重写 equals() 法子 (如1.2.5.8中的Date类型),这时最好使用不可变 (immutable) 的数据类型作为键,如 Integer, Double, String, java.io.File等。机会键是Comparable对象,则 a.compareTo(b) == 0a.equals(b) 是等价的。