数据结构与算法中查找树知识点总结（5）有哪些关键点？

本文共计11177个文字，预计阅读时间需要45分钟。

1. 基础查找+符号表是一种典型ADT，提供操作键值的方法：插入、查找、删除。本节将介绍两种基本的符号表：无序链表中的顺序查找和基于有序数组的二分查找。

1.基础查找

　　符号表是一种典型的ADT,它提供了操作键值对的方法:　put(插入、insert)、search、delete操作，这一节将会给出两种初级的符号表: 无序链表中的顺序查找、基于有序数组二分查找的有序符号表。

　　在某些实现中我们认为保持键的有序性并大大扩展它的API是很有用。例如键是时间，你可能会对最早的或是最晚的或者给定时间段内的所有键感兴趣。在大多数情况下这些额外的操作只需要在数据结构上增加一些信息及少量代码即可实现，如下定义的一些API便支持一般的动态集合上顺序统计操作的数据结构(所谓第i个顺序统计量是该集合中第i小或大的元素)。

1.1 有序符号表的API说明

　　在一个给定不变的集合中选择第i个顺序统计量的问题，这种被称为选择问题。它可以在O(lgn)时间内利用堆排序或者合并排序对数据进行排序后再取第i个元素，或者基于快速排序的确定性划分算法在O(n)时间内取第i个元素。由此引申出了一个中位数的查找问题(中位数: 集合元素按大小顺序排序后其中间的位置的数，集合大小为奇数时，中位数唯一，位于中间；大小为偶数时，存在两个中位数，取其平均值即可)。对于集合固定的中位数查找只需要利用select操作找到中间的数即可，对于两个有序数组(长度一致或者不一致均可以)的中位数查找可以用分治法(每次可去除一半的元素)。

　　如果集合元素是动态变化呢，可以设计一个含最大堆和最小堆的数据类型，它能够在对数时间内插入元素或删除元素，常数时间内找到中位数。