skiplist
跳表 skiplist
Binary trees can be used for representing abstract data types such as dictionaries and ordered lists. They work well when the elements are inserted in a random order. 二叉树可以使用来表达一个词典或者一个有序列表.当二叉树的元素插入是随机顺序的时候,他可以工作很好
Some sequences of operations, such as inserting the elements in order, produce degenerate data structures that perform very poo.rly. 但是一些特定的顺序,举个例子,如果插入的数据本身已经是有序的,那么效果则会很差 If it were possible to randomly permute the list of items to be inserted, trees would work well with high probability for any input sequence. 如果可以产生随机的数据去插入,那么树会对输入的性能变得非常好 In most cases queries must be answered online, so randomly permuting the input is impractical. Balanced tree algorithms rearrange the tree as operations are performed to maintain certain balance conditions and assure good performance. 在大部分的情况必须实时查询,所以随机交换输入是不可能的,平衡树需要重排来保证某些平衡的条件和确保比较好的性能 Skip lists are a probabilistic alternative to balanced trees. 跳表相对于平衡树来说是另外一个选择 Skip lists are balanced by consulting a random number generator. 跳表的平衡是通过获取一个随机数 Although skip lists have bad worstcase performance, no input sequence consistently produces the worst-case performance (much like quicksort when the pivot element is chosen randomly). 虽然跳表也有bad case(举个例子每次随机的高度都一样) , 但是没有一个输入序列可以把这个bad case稳定的生成(因为是随机产生所以不会一直产生最坏情况) It is very unlikely a skip list data structure will be significantly unbalanced (e.g., for a dictionary of more than 250 elements, the chance that a search will take more than three-times the expeci.ed time is less than one in a million). Skip lists have balance properties similar to that of search trees built by random insertions, yet do not require insertions to be random. 这不太可能跳表变得非常显著地不平衡,跳表的平衡性质和一个随机插入的搜索树相类似,但是不需要随机去插入 It is easier to balance a data structure probabilistitally than to explicitly maintain the balance. 通过概率去平衡一个暑假结构比显式保持它的平衡要简单 For many applications, skip lists are a more natural representation than trees, and they lead to simpler algorithms. 对于很多应用,相对于树来说跳表会更加自然. The simplicity of skip list algorithms makes them easier to implement and provides significant constant factor speed improvements over balanced tree and self-adjusting tree algorithms. 跳表的简易型可以实现和提供一个显著的常量因子去比平衡树和自适应树更好 Skip lists are also very space efficient. 跳表的空间利用率很高 They can easily be configured to require an average of 1% pointers per element (or even less) and do not require balance or priority information to be stored with each node. 他们可以需要平均百分之1的指针和不需要平衡或者权重信息取存储每个节点
SKIP LISTS 跳表 We might need to examine every node of the list when searching a linked list (Figure la). 当我们使用链表这个结构来存储数据,如果我们要搜索某个节点,我们需要顺序遍历每个节点. If the list is stored in sorted order and every other node of the list also has a pointer to the node two ahead of it in the list (Figure lb), we have to examine no more than [n/21 +1 nodes (where n is the length of the list). 如果这个list是 Also giving every fourth node a pointer four ahead (Figure lc) requires that no more than rn/41 + 2 nodes be examined. If every (27th node has a pointer 2’ nodes ahead (Figure Id), the number of nodes that must be examined can be reduced to rlog,nl while only doubling the number of pointers. This data structure could be used for fast searching, but insertion and deletion would be impractical. A node that has k forward pointers is called a level k node. If every (2’)th node has a pointer 2’ nodes ahead, then levels of nodes are distributed in a simple pattern: 50 percent are level 1, 25 percent are level 2, 12.5 percent are level 3 and so on. What would happen if the levels of nodes were chosen randomly, but in the same proportions (e.g., as in Figure le)? A node’s ith forward pointer, instead of pointing 2’-’ nodes ahead, points to the next node of level i or higher. Insertions or deletions would require only local modifications; the level of a node, chosen randomly when the node is inserted, need never change. Some arrangements of levels would give poor execution times, but we will see that such arrangements are rare. Because these data structures are linked lists with extra pointers that s