7.3 Skip List 7.3.1理想情况 7.3.2插入和删除 73.3级的分配 7.34类 Skipnode 7.3.5类 SkipList 7.3.6复杂性 山东大学计算机科学与技术学院数据结构第7章跳表和散列
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 17 7.3 Skip List ◼ 7.3.1 理想情况 ◼ 7.3.2 插入和删除 ◼ 7.3.3 级的分配 ◼ 7.3.4 类SkipNode ◼ 7.3.5 类SkipList ◼ 7.3.6 复杂性
73.1 ideal case 口12++2413011406075+8 Search:最坏情况下的比较次数fn)=n 24 40 Search: f(n)=n/2+1 if we keep a pointer in the middle 4x1 0 20 24 40 60 山东大学计算机科学与技术学院数据结构第7章跳表和散列
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 18 7.3.1 ideal case 20 24 30 40 60 75 80 Search : 最坏情况下的比较次数 f(n)= n Search : f(n)= n/2+1 if we keep a pointer in the middle. 20 24 30 40 60 75 80 20 24 30 40 60 75 80 2 1 0
731 ideal case 0级链上元素数:n 1级链上元素数:%2n 2级链上元素数:%n /级链上元素数:n/2 We shall say that an element is a level i element iff it is in the chains for level o through i and it is not non the level i+1 E. g. 40 is only level 2 element, and 24 and 75 are the level 1 elements 山东大学计算机科学与技术学院数据结构第7章跳表和散列
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 19 7.3.1 ideal case ◼ 0 级链上元素数: n ◼ 1 级链上元素数: ½ n ◼ 2 级链上元素数：¼ n ◼ …… ◼ i 级链上元素数: n/2i ◼ We shall say that an element is a level i element iff it is in the chains for level 0 through i and it is not non the level i+1. ◼ E.g. 40 is only level 2 element, and 24 and 75 are the level 1 elements
■跳表( skip list n在跳表结构中有一组有层次的链。 0级链是包含所有元素的有序链表,1级链是0级 链的一个子集。閡级链所包含的元素是-级链所 有元素的子集. 山东大学计算机科学与技术学院数据结构第7章跳表和散列 20
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 20 ◼ 跳表(skip list): ◼ 在跳表结构中有一组有层次的链。 ◼ 0级链是包含所有元素的有序链表，1级链是0级 链的一个子集。 i级链所包含的元素是i-1级链所 有元素的子集
Insertions and deletions when insertion and deletions occurs we cannot maintain the regular structure without doing o(n) work. We can attempt to approximate this structure in the face of insertions by noting that in the regular structure. n/2 elements are level i elements. When an insertion is made. the element level is i with probability 1/2!. we can actually allow for any probability to be used when making this determination. Assign the newly inserted element at level i with probability p, fig. (c)p=1/2. for general p, the number of chain level is Llogu p n/+l 山东大学计算机科学与技术学院数据结构第7章跳表和散列
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 Insertions and Deletions ◼ When insertion and deletions occurs, we cannot maintain the regular structure without doing O(n) work. We can attempt to approximate this structure in the face of insertions by noting that in the regular structure, n/2i elements are level i elements. When an insertion is made, the element level is i with probability 1/2i . We can actually allow for any probability to be used when making this determination. Assign the newly inserted element at level i with probability pi ，fig. (c) p=1/2. for general p, the number of chain level is log1/ p n+1