高级数据结构：算法实现与分析

需积分: 9 146 浏览量更新于2024-07-27 收藏 2.03MB PDF 举报

"Advanced Data Structure 是一本由 Peter Brass 撰写的高级数据结构教材，涵盖了搜索树、堆、字符串等高级数据结构的操作与分析，旨在深入探讨数据结构在应用算法中的特殊角色。书中通过丰富的代码示例（C语言）和超过500条参考文献，为读者提供了一本不可或缺的学习资料。作者 Peter Brass 在德国不伦瑞克技术大学获得数学博士学位，并在纽约城市学院计算机科学系担任副教授，曾任海森堡研究学者。" 在这本《高级数据结构》中，作者探讨了数据结构实现查询和更新操作的各种高效方法，这些操作主要针对数值集、区间集或字符串集。以下是一些核心知识点的详细说明： 1. **搜索树**：搜索树是一种能够快速查找、插入和删除元素的数据结构。书中可能涵盖了二叉搜索树、AVL树、红黑树等自平衡搜索树，以及B树和B+树等多路搜索树，这些树型结构能保持平衡，从而保证高效的查找性能。 2. **堆**：堆是一种特殊的完全二叉树，分为最大堆和最小堆，其中父节点的值总是大于或等于（或小于或等于）其子节点的值。堆常用于优先队列的实现，以及在排序算法如堆排序中的应用。 3. **区间数据结构**：处理区间集合的数据结构，如区间树、区间索引等，它们支持区间查询、覆盖查询等操作，广泛应用于时间轴事件管理、统计分析等领域。 4. **正交范围搜索结构**：这类结构允许对二维或多维空间中的对象进行快速的范围查询，例如矩形区域内的对象搜索，常用于地图信息系统和图像处理。 5. **并查集（Union-Find）结构**：用于维护一组无序分组的数据结构，支持快速查找元素所属的组以及合并两个组的操作，常见于图论问题和网络连接状态的表示。 6. **动态化与持久化**：数据结构的动态化是指在不影响历史状态的情况下，对结构进行修改的能力；持久化则是保存数据结构在不同时刻的状态，以便后续回溯。这两种特性在数据库和版本控制系统中有重要应用。 7. **字符串数据结构**：包括Trie树（字典树）、Suffix Tree（后缀树）和Aho-Corasick自动机等，用于高效地处理字符串查询和模式匹配问题。 8. **哈希表**：哈希表通过散列函数将键映射到数组的特定位置，实现快速查找、插入和删除操作。哈希冲突的解决策略，如开放寻址法和链地址法，也是重点讨论的内容。这本书不仅介绍了各种高级数据结构，还深入分析了它们的效率和实现细节，适合希望提升算法能力，特别是数据结构理解与应用的读者。通过学习，读者可以掌握如何根据实际问题选择合适的数据结构，以及如何设计和优化算法，提升程序的性能。

xiv Preface

usual complexity measure is the worst-case complexity; so an operation in a

speciﬁc data structure has a complexity O(f (n)) if, for any state of the data

structure reached by a sequence of update operations that produced an object of

size n, this operation takes at most time Cf (n)forsomeC. An alternative but

weaker measure is the amortized complexity; an update operation has amortized

complexity O(f (n)) if there is some function g(n) such that any sequence of

m of these operations, during which the size of the underlying object is never

larger than n, takes at most time g(n) + mCf (n), so in the average over a long

sequence of operations the complexity is bounded by Cf (n).

Some structures are randomized, so the data structure makes some random

choices, and the same object and sequence of operations do not always lead

to the same steps of the data structure. In that case we analyze the expected

complexity of an operation. This expectation is over the random choices of the

data structure; the complexity is still the worst case of that expectation over all

objects of that size and possible operations.

In some situations, we cannot expect a nontrivial complexity bound of type

O(f (n)) because the operation might give a large answer. The size of the answer

is the output complexity of the operation, and, for operations that sometimes

have a large output complexity, we are interested in output-sensitive methods,

which are fast when the output is small. An operation has output-sensitive

complexity O(f (n) + k) if, on an object of size n that requires an output of

size k, the operation takes at most time C(f (n) +k).

For dynamic data structures, the time to create the structure for an empty

object is usually constant, so we are mainly interested in the update and query

times. The time to delete a structure of size n is almost always O(n). For static

data structures we already create an object of size n, so there we are interested

in the creation time, known as preprocessing time, and the query time.

In this book, log

n denotes the logarithm to base a; if no base is speciﬁed,

we use base 2.

We use the Bourbaki-style notation for closed, half-open, and open intervals,

where [a, b] is the closed interval from a to b,]a, b[ is the open interval, and

the half-open intervals are ]a,b], missing the ﬁrst point, and [a, b[, missing the

last point.

Similar to the O(·)-notation for upper bounds mentioned earlier, we also use

the (·) for lower bounds and (·) for simultaneous upper and lower bounds.

A nonnegative function f is O(g(n)), or (g(n)), if for some positive C and all

sufﬁciently large n holds f (n) ≤ Cg(n), or f (n) ≥ Cg(n), respectively. And

f is (g(n)) if it is simultaneously O(g(n)) and (g(n)). Here “sufﬁciently

large” means that g(n) needs to be deﬁned and positive.

Preface xv

Code Examples

The code examples in this book are given in standard C. For the readers used

to some other imperative programming language, most constructs are self-

explanatory.

In the code examples, = denotes the assignment and == the equality test.

Outside the code examples, we will continue to use = in the normal way.

The Boolean operators for “not,” “and,” “or” are !, &&, ||, respectively,

and % denotes the modulo operator.

Pointers are dereferenced with *,soifpt is a pointer to a memory location

(usually a variable), then *pt is that memory location. Pointers have a type to

determine how the content of that memory location should be interpreted. To

declare a pointer, one declares the type of the memory location it points to, so

“int *pt;” declares pt to be a pointer to an int. Pointers are themselves

variables; they can be assigned, and it is also possible to add integers to a

pointer (pointer arithmetic). If pt points to a memory object of a certain type,

then pt+1 points to the next memory location for an object of that type; this is

equivalent to treating the memory as a big array of objects of that type. NULL

is a pointer that does not point to any valid memory object, so it can be used as

a special mark in comparisons.

Structures are user-deﬁned data types that have several components. The

components themselves have a type and a name, and they can be of any type,

including other structures. The structure cannot have itself as a type of a

component, because that would generate an unbounded recursion. But it can

have a pointer to an object of its own type as component; indeed, such structures

are the main tool of data structure theory. A variable whose type is a structure

can be assigned and used like any other variable. If z is a variable of type C,

and we deﬁne this type by

typedef struct { float x; float y; } C,

then the components of z are z.x and z.y, which are two variables of type

float.Ifzpt is declared as pointer to an object of type C (by C *zpt;),

then the components of the object that zpt points to are (*zpt).x and

(*zpt).y. Because this is a frequently used combination, dereferencing a

pointer and selecting a component, there is an alternative notation zpt->x

and zpt->y. This is equivalent, but preferable, because it avoids the operator

priority problem: dereferencing has lower priority than component selection,

so (*zpt).x is not the same as *zpt.x.

We avoid writing the functions recursively, although in some cases this might

simplify the code. But the overhead of a recursive function call is signiﬁcant

剩余473页未读，继续阅读

hydrofuel

粉丝: 1
资源: 5

高级数据结构：算法实现与分析

Advanced Data Structures

数据结构-advanced data structure (peter brass)

advanced-data-structure

Advanced-Data-Structure

Advanced-data-structure

Advanced_data_structure

ADVANCED-DATA-STRUCTURE-programs

【Advanced Section】Advanced Data Parsing: XPath and Regular Expressions Advanced

Swift Data Structure and Algorithms [2016]

Advanced Data Export 4.15 10.3 Rio

最新资源