AndroidPi

在二叉搜索树的讨论中可以得出各种查询以及插入、删除操作的时间复杂度上界为$O(h)$，其中$h$为树的高度，即树的叶子节点的最大深度。 因此树的高度很大程度上决定了动态集合操作的时间复杂度。对于一个包含确定数量元素的二叉搜索树，我们希望得到一棵较为“平衡”的二叉树，即后代结点能够较均匀分布在一个祖先结点的两颗子树中，这样相对于元素总量，其高度是一个较小的值。因此，可以将平衡的度量认为是树高h与结点总量n的比率$\frac{h}{n}$，即结点对树高的平均贡献率。 考察树的第i层的$k_i$个结点，有： $$ n = \sum\limits_{i=0}^h k_i, \space k_i \leq 2^i $$ 如果树中有大量不平衡的结点，那么每个第i层的结点越少，会导致树高$h$越大。 红黑树及其性质 红黑树是平衡二叉搜索树的一种，可以保证最坏情况下动态集合操作的时间复杂度为$O(\lg n)$，它在每个结点上增加一个存储位来表示结点颜色，可以是RED或BLACK，通过对任一条从根到叶子结点的路径上各个结点的颜色进行约束，可以确保没有一条路径会比其它路径长出2倍，因而是近似于平衡的。 一棵红黑树中的每个结点包含5个属性，color，key，left，right和p，如果一个结点没有子结点或父结点，这改结点相应指针属性的值为NIL，可以把这些NIL视为指向二叉搜索树的叶结点（外部结点）的指针，而把带关键字的结点视为树的内部结点。 一棵红黑树是满足下面红黑性质的二叉搜索树： 每个结点是红色的或黑色的 根结点是黑色的 每个叶结点（NIL）是黑色的 如果一个结点是红色的，则它的两个子结点都是黑色的 对每个结点，从该结点到所有后代叶结点的简单路径上，均包含相同数目的黑色结点 从某个结点x出发(不含该结点)到达一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高(black height)，定义红黑树的黑高为其根结点的黑高。 红黑树动态集合操作 对不修改树的数据结构的操作，如遍历、查询、最大、最小、前驱、后继一类操作对红黑树和普通二叉搜索树都是一样的，对于插入与删除操作，红黑树需要进行额外的变换，不仅改变数据结构，也需要改变结点的颜色以保证红黑树的性质。 旋转 对于数据结构的修改，可以通过旋转来完成，它是能保持二叉搜索树的性质的局部操作。主要有两种旋转方式，分别为左旋和右旋。 插入 首先采用稍作修改的普通二叉搜索树插入方法将新的结点插入到树中，为了保证红黑树的性质，还需要对结点进行着色和旋转操作。 删除 首先采用进行了一定修改的普通的二叉搜索树删除方法将给定结点z从树T中删除，其中需要维持一个结点y为从树中删除的结点或移至树内的结点，并记录y的初始颜色，如果y的初始颜色为黑色，那么需要进行着色和旋转操作来恢复红黑性质。此外还要跟踪移动到结点y原来位置的x结点，因为它也有可能破坏红黑树性质。

定义 自由树 自由树是一个连通的、无环的无向图。一个可能不连通的的无向无环图为森林。 有根树和有序树 有根树是一棵自由树，其顶点中存在一个与其它顶点不同的顶点，称其为树的根，一棵有根树的顶点常常称为树的结点。 在一棵有根树T中，从根结点r到结点x的唯一简单路径上的任意结点y为x的一个祖先结点，x称为y的后代结点，每一个结点既是自己的祖先也是自己的后代，如果y是x的祖先，并且y不是x，那么称y为x的真祖先,x为y的真后代。如果y是x的真祖先，并且与x直接相连，则称y为x的父母结点，x为y的孩子结点。根是树中唯一没有父结点的结点，如果两个结点的父结点是同一个，则称它们为兄弟结点。一个没有子结点的结点称为叶子结点或外部结点，而非叶结点是内部结点。 树T中一个结点x的子结点数称为结点x的度，从根结点r到结点x的一条简单路径的长度称为x在T中的深度，根结点的深度为0。树的一个层包含了同一深度的所有结点。结点在树中的高度是指从该结点到叶结点最长的一条简单路径的边数。树的高度也就是树中结点的最大深度。 有序树是一棵有根树，其中每个结点的子结点是有序的。 二叉树与位置树 采用递归的方式定义二叉树，一个二叉树T是定义在有限结点集合上的结构，它不包含任何结点或者包含三个不相交的结点集合：一个根结点，一棵称为左子树的二叉树，以及一棵称为右子树的二叉树。 不包含任何结点的二叉树称为空树或零树，有时用符号NIL表示。在上述递归定义中，如果左子树非空则它的根称为整棵树的根的左孩子，类似，右子树的根称为整棵树根的右孩子。如果子树是零树，则称该孩子是缺失的或者丢失的。 位置树是保留了结点位置信息的树，有序树属于位置树。二叉树是结点的度最大为2的有序树，但有序树在子结点仅有一个（即度为1）时可以对子结点进行区分，而二叉树必须区分是左孩子还是右孩子。因此可以使用一个有序树的内部结点来表示二叉树的位置信息，通过将树中每个缺失的孩子使用一个无孩子的结点代替，得到一棵满二叉树，每个结点是叶结点或者度为2，那么就不存在度为1的结点，那么结点的孩子的顺序就保留了位置信息。 这种位置信息的区分可以扩展到k叉树，即每个结点度最大为k的位置树。完全k叉树是所有叶结点深度相同，且所有内部结点度为k的k叉树。如果树的高度为h，则叶结点数目为$h^k$个。 二叉搜索树 搜索树数据结构支持许多动态集合操作，包括搜索，最大值，最小值，查找前驱与后继，插入，删除等操作，即适合作为字典也可以作为一个优先队列。 二叉搜索树是以一棵二叉树来组织的，可以采用链表数据结构来表示，每个结点是一个对象，除了key和卫星数据，每个结点还包含属性left,right和p，分别指向结点的左孩子，右孩子和父母结点。如果某个子结点或者父结点不存在则相应的属性值为NIL。 二叉搜索树中的关键字总是以满足二叉搜索树性质的方式来存储： 设x是二叉搜索树的一个结点，如果y是x左子树中的一个结点，那么y.key≤x.key。如果y是x右子树中的一个结点，那么y.key≥x.key。 遍历 遍历顺序： 中序遍历：子树根位于左子树和右子树之间 先序遍历：子树根位于左子树和右子树之前 后序遍历：子树根位于左子树和右子树之后 查询 除了search操作，还支持minimum，maximum，successor，predecessor查询，对于高度为h的二叉树，每个操作可以在O(h)时间内完成。 插入与删除 插入与删除操作会引起二叉搜索树的动态集合变化。必须要修改数据结构来反映这个变化，但修改要保持二叉搜索树的性质成立。 插入 设要将一个新的值v插入到树T，从根结点r开始进行比较，如果$v \le r.key$，那么v需要插入到r的左子树中，这个问题便成了将v插入到以r.left为根的左子树的问题，如果$v \ge r.key$，那么v需要插入到r的右子树中，此外还需要考虑比较相等情况下的处理。 但这个问题可以一般化为将v插入到T的一个子树的问题，在插入时进行比较的过程中，对于一个比较结点x如果$v \le x.key$或者$v \ge x.key$，则继续分别在x的左右子树寻找插入的位置，直到比较结点为空，那么这个空位置即为要寻找的插入位置。 对于比较相等的情况，将其插入到比较结点的左子树或者右子树都是可行的，此时位置查找方式与上述小于或大于的情况一样，另一种做法可以直接使v成为比较结点左子树或右子树的根。但这样需要采用两种方式来修改数据结构，因此一般采用一致的插入到空位置方法。 删除 设要从树T中删除一个结点z，分下面三种情况进行考虑： z没有孩子结点：直接删除 z有一个孩子结点：用z的孩子替换z z有两个孩子结点：寻找z的后继y，让y占据z的位置 对于第3种情况，y在z的右子树中，并且y没有左孩子，找到y后，需要将y移出原来的位置并进行拼接，然后替换z，考虑两种情况： y是z的右孩子，保留y的右孩子并替换z y不是z的右孩子，首先用y的右孩子替换y，然后用y替换z

顺序统计量（Order statistic） 一个n位元素组成的集合中，第i个顺序统计量是该集合中第i小的元素。例如，最小值是第一个顺序统计量（i=1），最大值是第n个顺序统计量(i=n)。 中位数（Median） 中位数是顺序统计量的一种，它是集合中的中点元素，与上述顺序统计量的描述一致，i从1开始计数。当n为奇数时，中位数有唯一一个，位于i=(n+1)/2处，当n为偶数时，中位数有两个，分别为上中位数(n/2)与下中位数(n/2+1)。 问题与定义 讨论中一个由n个互异的元素构成集合中选择第i个顺序统计量的问题，为方便讨论，假设元素都是互异的，但实际上这里的讨论都可以推广到包含重复元素的集合中。对这一问题的形式化定义为 输入：一个包含n个互异元素的集合A和一个整数i，1≤ i ≤n。 输出：元素x属于集合A，且A中恰好有i-1个其它元素小于它。 基本思想 随机划分 使用类似快排的划分思路，选择一个主元（pivot），将序列中的其它元素进行划分为小于等于主元和大于等于主元的两个子序列，如果主元的顺序统计量就是要查找的顺序统计量则查找成功，如果目标顺序统计量小于主元的顺序统计量，则从较小的子序列中根据上述同样的过程进行查找，否则则在较大的子序列中进行查找。 确定性划分 确定性划分首先将序列分为较小的组，每一组有一个较小常数数量的元素，对每个分组进行排序，找出每组的中位数，然后对每组的中位数用同样的方式进行划分后查找这些中位数的中位数。利用每组中位数的中位数作为主元对序列进行划分，划分后的处理方式与随机划分相似。这里的重点是分组后的中位数的中位数x可以将序列划分为较为平均的两部分，因为，各分组的中位数y小于x的分组中小于中位数y的必定也小于x，中位数y大于x的分组中大于y的元素也必定大于x，它们大约各占整个序列的1/4，这样就避免了随机划分可能出现较差的情况。 实现 使用随机划分子序列的算法 def swap(A, i, j): temp = A[i] A[i] = A[j] A[j] = temp def random_select(A, p, r, i): """ A: 要查找的序列 p: 序列开始索引，包含 r: 序列结束索引，包含 i: 要查找的顺序统计量 """ # 如果只有一个元素，直接返回 if p == r: return A[p] q = random_partition(A, p, r) if i == q: return A[q] if i < q: return random_select(A, p, q-1, i) else: return random_select(A, q+1, r, i) def random_partition(A, p, r): """ A: 要划分的序列 p: 序列开始索引，包含 r: 序列结束索引，不包含 """ # 这里直接从中间进行划分 mid = (p + r) / 2 pivot = A[mid] # 主元 left = p # [p,left)间的元素都小于等于主元 right = r # (right,r]间的元素都大于等于主元 while left < right: if A[left] >= pivot and A[right] <= pivot: swap(A, left, right) left += 1 right -= 1 else: if A[left] < pivot: left += 1 if A[right] > pivot: right -= 1 return left def main(): A = [100, 134, -1, 1324, 1123, 9, 34, 3, -98, 132, 3, 3, 12, 29, 36] for i in xrange(0, len(A)-1): print random_select(A, 0, len(A)-1, i) if __name__ == '__main__': main() 使用确定性划分的算法 def swap(A, i, j): temp = A[i] A[i] = A[j] A[j] = temp def insertion_sort(A, r): for i in xrange(0, len(r)): current = i for j in xrange(i, -1, -1): if A[r[current]] < A[r[j]]: swap(A, r[current], r[j]) current = j def median(A, r): # print "median", r insertion_sort(A, r) if len(r) % 2 == 1: return r[len(r) / 2] else: return r[len(r) / 2 - 1] def select(A, r, i): # print "select", r """ A: 要查找顺序统计量的序列 r: 查找的序号 """ size = len(r) if size == 1: return r[0] start = r[0] # start index in A end = r[size - 1] # end index in A medians = [] if size % 5 == 0: num = size / 5 else: num = size / 5 + 1 for j in xrange(0, num): s = j * 5 # start index of r e = s + 5 # end index of r if e >= size: e = size m = median(A, r[s : e]) medians....

排序算法下界 对任意的比较排序算法都可以抽象为一棵决策树，它是一棵完全二叉树，可以表示在给定输入规模下对所有元素的比较操作，其中，控制、数据移动等其它操作都被忽略。对于一个正确的排序算法，它都能够生成输入的每一种排列，所以对一个正确的比较排序算法来说，n个元素的$n!$种可能的排列都应该出现在决策树的叶结点上，对于一个给定的输入，其排序结果必然就是这所有可能中的某一个。 根据这个比较排序的决策树模型，从根结点到一个可达的叶结点之间的最长简单路径的长度，表示的是对应排序算法中最坏情况下的比较次数，它等于决策树的高度。因此，当决策树中的每种排列都是以可达的叶结点形式出现时，该决策树高度的下界也就是比较排序算法运行时间的下界。 最坏情况的下界 考虑一棵高度为h，具有l个可达叶结点的决策树，它对应一个对n个元素所做的比较排序，输入的$n!$种可能的排序都是叶结点，并且一棵高度为h的二叉树中，叶结点的数量不多于$2^h$，因此有： $$ n! \leq l \leq 2^h $$ 得到 $$ h \geq \lg (n!) = \Omega (n\lg n) $$ 计数排序 适用场景 n个输入元素是0到k区间的整数，或者元素可以通过转换函数，在不丢失大小信息的情况下，唯一地映射到0到k区间某一个整数。 基本思想 对每一个输入元素x确定小于x的元素个数，利用这一信息可以直接将x放到它在输出数组中的位置上。 实现 def counting_sort_integer(A, B, k): C = [0 for x in xrange(0, k+1)] for x in A: C[x] += 1 for i in xrange(0, k+1): if i > 0: C[i] += C[i-1] for x in A: # index start with 0, so minus 1 B[C[x]-1] = x C[x] -= 1 if __name__ == '__main__': A = [123, 21, 14321, 0, 120, 98, 1000, 1024, 123, 1, 0, 123, 24, 123, 3, 2, 12] B = [None] * len(A) counting_sort_integer(A, B, 14321) print B 基数排序 适用场景 对具有多关键字域的记录或某一基数表示的数（二进制位表示，10进制数，16进制数，字符串等）进行排序，其共同的特点是每个元素有d位，每一位有一个固定的取值区间，因此可以利用到计数排序的方法。...

堆 堆是一个数组，可以看作一个近似的完全二叉树，树中的每一个节点对应于数组中的一个元素。除了最底层的叶节点，往上的所有层都是完全填充的，并且都是从左向右进行填充。表示堆的数组A有两个属性：A.length表示数组大小，A.heap-size表示堆大小，即堆中有多少个元素存在数组中。 算法导论中将根节点的序号设定为1，但实际使用的数组都是从0开始的，即从偶数开始填充堆，那么为了使数组依次逐层进行填充，对于一个节点在数组中的序号i，其左右孩子为: Left(i): 2i+1 Right(i): 2i+2 根据左右孩子可以将一个序号为i的节点的父节点计算为： Parent(i): floor((i-1)/2) 最大堆与最小堆 最大堆是父节点的值大于等于子节点的值，反之，最小堆是子节点的值大于等于父节点的值。在堆排序中使用最大堆，最小堆通常用于构造优先队列。 最大堆与堆排序 class Heap: def __init__(self, array, heap_size = None): if heap_size is not None: self.heap_size = heap_size else: self.heap_size = len(array) self.array = array @classmethod def left(cls, i): return (i << 1) + 1 @classmethod def right(cls, i): return (i << 1) + 2 @classmethod def parent(cls, i): return (i - 1) / 2 @classmethod def swap(cls, A, i, j): temp = A[i] A[i] = A[j] A[j] = temp class MaxHeap(Heap): def __init__(self, array, heap_size = None): Heap....