Transcript Chapter 2 Advanced Data Structures

Advanced Data Structures
CHAPTER 2
Outlines
•
•
•
•
Binary search trees
B-trees
Heaps and priority queues
Skip list
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
2
Binary Search Trees
Binary Search Trees: Nodes
left
parent right
key
internal node
left
key
parent right
root node
Jaruloj Chongstitvatana
left
key
parent right
leaf node
Chapter 2: Advanced Data Structures
4
Property of Binary Search Trees
For any node n in a binary search tree T,
• if p is a node in the left subtree of n, then
p.key ≤ n.key;
• if q is a node in the right subtree of n, then
n.key ≤ q.key.
T
n
p
Jaruloj Chongstitvatana
q
Chapter 2: Advanced Data Structures
5
Example of Binary Search Trees
12
10
8
4
17
6
9
4
19
9
12
20
5
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
6
Inorder Traversal of Binary Search Trees
inorder(T: node)
if T is not null,
then inorder(T.left)
print(T.key)
inorder(T.right)
return.
}
12
8
4
17
9
5
10
6
4
Jaruloj Chongstitvatana
19
9
Chapter 2: Advanced Data Structures
12
20
7
Search in Binary Search Trees
search(n: node, k: key)
if n is null or n.key = k,
then return(n)
if k < n.key,
then search(n.left, k)
else search(n.right, k)
return.
12
8
4
17
9
5
10
6
4
Jaruloj Chongstitvatana
19
9
Chapter 2: Advanced Data Structures
12
20
8
Insertion in Binary Search Trees
insert(T: node, z: node)
insert(T: node, z: node)
if T is null
y = null
The tree T is empty.
then T.root = z
x=T
return
while x is not null
if key[z] < key[T]
y=x
then if T.left is null
if z.key < x.key
then x = x.left Found the place, and then T.left = z
z.p = T
else x = x.right insert as the right
left child.
child.
else insert(x.left, z)
z.parent= y
else if T.right is null
if y = NIL
then x.right = z
then T.root= z
z.p = T
else if z.key < y.key
else insert(x.right, z)
then y.left= z
return
else y.right = z
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
9
Deletion in Binary Search Trees
• See textbook
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
10
B-trees
B-trees
• Index structures for large amount of data.
• All data cannot be resided in the main
memory.
• Data is stored in a disk.
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
12
Disk Operations
• In a disk, data is
organized in disk
pages.
• To read data in a
disk,
• The disk rotates, and
the R/W head moves
to the page
containing the data.
• Then, the whole disk
page is read.
From: Cormen, T., C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 2001.
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
13
B-trees: Nodes
Internal node
number
of keys
key1
key2
key3
keyn
false
leaf
keyn
true
leaf
Pointers to other nodes
leaf node
number
of keys
key1
key2
key3
Pointers to data pages
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
14
Properties of B-trees
For any node n in a B-tree T
n p
…
key1
c
q
keyi
key1
keyi+1
…
keyi
…
false
keyi+1
…
false
• n.keyi ≤ c.key1 ≤ c.key2 ≤ … ≤ c.keyq ≤
n.keyi+1
• If n is a leaf node, the depth of n is h, where
h is the tree’s height.
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
15
Properties of B-trees
• The minimum degree, t, of the B-tree is the lower bound
on the number of keys a node can contain. (t ≥ 2)
• Every node other than the root must have at least t − 1
keys.
• Every internal node other than the root thus has at least t
children.
• If the tree is nonempty, the root must have at least one
key.
• Every node can contain at most 2t − 1 keys. Therefore, an
internal node can have at most 2t children.
• We say that a node is full if it contains exactly 2t − 1
keys.
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
16
Search in B-trees
65
11
17
6
8
68
12
71
16
26
75
60
69
66
Jaruloj Chongstitvatana
88
70
67
Chapter 2: Advanced Data Structures
17
Search in B-trees
B-TREE-SEARCH(x, k)
i =1
► find a proper child
while i ≤ x.n and k > x.keyi do i =i + 1
if i ≤ x.n and k = x.keyi
then return (x, i )
if x.leaf
then return NIL
► recursively search in the proper subtree
else DISK-READ (x.ci)
return B-TREE-SEARCH (x.ci, k)
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
18
Creating B-trees
B-TREE-CREATE(T )
x = ALLOCATE-NODE()
x.leaf = TRUE
x.n = 0
DISK-WRITE(x)
T.root = x
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
19
Insertion in B-trees
17
8
17
26
11
65
8
26
65
11
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
20
Insertion in B-trees
6
17
11
8
11
12
12
16
16
26
Jaruloj Chongstitvatana
65
Chapter 2: Advanced Data Structures
21
Insertion in B-trees
60
11
6
17
65
8
12
16
26
65
65
71
71
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
22
Insertion in B-trees
66
11
6
17
65
71
8
12
16
26
75
60
67
Jaruloj Chongstitvatana
88
71
75
88
Chapter 2: Advanced Data Structures
23
Insertion in B-trees
70
11
6
17
65
71
8
12
16
26
75
60
69
66
Jaruloj Chongstitvatana
88
67
68
69
Chapter 2: Advanced Data Structures
24
Insertion in B-trees
65
11
17
11
70
17
65
7171
71
68
6
8
12
16
26
75
60
69
66
Jaruloj Chongstitvatana
88
67
Chapter 2: Advanced Data Structures
25
Insertion in B-trees
65
11
17
6
8
68
12
71
16
26
75
60
69
66
Jaruloj Chongstitvatana
88
70
67
Chapter 2: Advanced Data Structures
26
Insertion in B-trees
B-TREE-INSERT(T, k)
r = T.root
if r.n = 2t − 1
► The root node r is full, then create a new root node
then s = ALLOCATE-NODE()
T.root = s;
s.leaf = FALSE
s.n = 0; s.c1 = r
► Split old root into two, and put under the new root
B-TREE-SPLIT-CHILD(s, 1, r)
B-TREE-INSERT-NONFULL(s, k)
else B-TREE-INSERT-NONFULL(r, k)
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
27
Splitting Nodes in B-trees
B-TREE-SPLIT-CHILD(x, i, y)
►Create a new node
z = ALLOCATE-NODE()
►Move up other 1/2 of old node
for j = x.n + 1 downto i + 1
do x.cj+1 = x.cj
z.leaf = y.leaf
x.ci+1 = z
z.n = t − 1
for j = x.n downto i
►Move 1/2 of old node to new
do x.keyj+1 = x.keyj
for j = 1 to t − 1
x.keyi = y.keyt
do z.keyj = y.keyj+t
x.n = x.n + 1
if not y.leaf
DISK-WRITE(y)
then for j = 1 to t
DISK-WRITE(z)
do z.cj = y.cj+t
y.n = t − 1
DISK-WRITE(x)
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
28
Binary Heaps
Binary Heaps
• Binary heap is an array
• can be viewed as a nearly
complete binary tree
• each node of the tree
corresponds to an element
of the array that stores the
value in the node.
1
left
4
2
right
5
3
6
7
8
9
11 12
13
• The tree is completely
10
filled on all levels except
possibly the lowest, which
is filled from the left up to
a point.
1 2 3 4 5 6 7 8 9 10 11 12 13
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
30
Representation of Biinary Heaps
• An array A that represents a heap is an
object with two attributes:
• length[A], which is the number of elements in
the array
• heap-size[A], the number of elements in the
heap stored within array A.
heap-size
1 2 3 …
Jaruloj Chongstitvatana
length
… n x … x
Chapter 2: Advanced Data Structures
31
Properties of Binary Heaps
• If a heap contains n elements, its height is
lg2 n.
• In a max-heaps
For every non-root node i, A[PARENT(i)] ≥ A[i]
• In a min-heaps
For every non-root node i, A[PARENT(i)] ≤ A[i]
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
32
Examples
15
Max heap
12
8
9
3
4
6
2
6
5
5
1
9
11
Min heap
15
Jaruloj Chongstitvatana
7
19
20
18
12
Chapter 2: Advanced Data Structures
33
Heapify
7
12
8
9
3
Jaruloj Chongstitvatana
4
6
2
6
5
1
Chapter 2: Advanced Data Structures
34
Heapify
12
7
12
7
8
9
3
Jaruloj Chongstitvatana
4
6
2
6
5
1
Chapter 2: Advanced Data Structures
35
Heapify
12
7
9
8
7
9
3
Jaruloj Chongstitvatana
4
6
2
6
5
1
Chapter 2: Advanced Data Structures
36
Heapify
MAX-HEAPIFY(A, i )
l = LEFT(i )
r = RIGHT(i )
► Find node containing the largest value among i and its valid children.
if l ≤ heap-size[A] and A[l] > A[i ]
then largest = l
else largest = i
if r ≤ heap-size[A] and A[r] > A[largest]
then largest = r
► Swap the largest node and node i if the node i is not the largest
if largest  i
then exchange A[i ] and A[largest]
MAX-HEAPIFY(A, largest)
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
37
Time Complexity for Heapify
• worst-case
• The left subtree is one-level taller than the right
subtree, and both are complete binary trees
• The left subtree contains (2n-1)/3 nodes and the right
subtree contains (n-2)/3.
Let T(n) be time spent to heapify an n-node heap.
T(n) = T((2n-1)/3) + k
T(n)  Ο(lg n)
T(n)  Ο(h)
• since the height h of a heap is in Ο(lg n)
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
38
Building Max-heaps: BUILD-MAX-HEAP(A)
1
2
11
3
7
4
9
8
Jaruloj Chongstitvatana
10
11
5
2
9
4
10
2
6
7
3
11
5
Chapter 2: Advanced Data Structures
39
Building Max-heaps: BUILD-MAX-HEAP(A)
1
11
10
11
1
7
9
8
Jaruloj Chongstitvatana
10
5
1
4
2
6
3
5
1
Chapter 2: Advanced Data Structures
40
Building Max-heaps: BUILD-MAX-HEAP(A)
heap-size[A] = length[A]
► Start from the rightmost node in the level above leaves
for i = length[A]/2 downto 1
do
MAX-HEAPIFY(A, i )
1
2
3
4
8
Jaruloj Chongstitvatana
5
9
10
6
7
11
Chapter 2: Advanced Data Structures
41
Time to Build Max-heaps
Let n be the heap size,
T(n) be the time spent in BUILD-MAX-HEAP for heap of size n,
t(h) be the time spent in MAX-HEAPIFY for the heap of height h,
k(h, n) be the number of subtrees of height h in the heap of size n.
lg n
lg n
h=0
h=0
T(n)   t(h) k(h, n) =
lg n
 c h n/2h+1 = c n  (h/2h)
2
h=0
lg n
T(n) = O(n  (h/2h))
h=0

Since  (h/2h)) = 2, T(n) = O(n).
h=0
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
42
Heapsort
HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i = length[A] downto 2
► Swap the max node with last in heap, and
► heapify heap, excluding the last (old max)
do exchange A[1] and A[i ]
heap-size[A] = heap-size[A] − 1
MAX-HEAPIFY(A, 1)
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
43
Time for Heapsort
• The call to BUILD-MAX-HEAP takes O(n)
• Each of the n − 1 calls to MAX-HEAPIFY
takes O(lg n)
• HEAPSORT takes O(n lg n).
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
44
Priority Queues
Priority Queues
• A priority queue is a max-heap with
operations for queues.
• Insert
• Extract-max
• Increase-key
HEAP-MAXIMUM(A)
return A[1]
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
46
Extract-Max In Priority Queues
HEAP-EXTRACT-MAX(A)
if heap-size[A] < 1
then error “heap underflow”
► Take the maximum element from the root
max = A[1]
► Move the last element in the heap to the root
A[1] = A[heap-size[A]]
heap-size[A] = heap-size[A] − 1
► Heapify
MAX-HEAPIFY(A, 1)
return max
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
47
Increase Key
HEAP-INCREASE-KEY(A, i, key)
if key < A[i ]
then error “new key < current key”
A[i ] = key
► Swap the increased element with its parent up toward
► the root until it is not greater than its parent
while i > 1 and A[PARENT(i)] < A[i ]
do exchange A[i] and A[PARENT(i)]
i = PARENT(i)
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
48
Insert
MAX-HEAP-INSERT(A, key)
► Insert the minimum element
heap-size[A] = heap-size[A] + 1
A[heap-size[A]]=−∞
► Increase the minimum element
HEAP-INCREASE-KEY(A, heap-size[A], key)
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
49
Binomial Heaps
Why Binomial Heaps
• Union two binary heaps takes (n).
• Can it be reduced?
• Use binomial heaps
• A binomial heap is a binomial tree that has
the property of heaps.
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
51
Binomial Trees
• The binomial tree Bk is an ordered tree
which consists of two binomial trees Bk−1
that are linked together.
• the root of one is the leftmost child of the root
of the other.
• The binomial tree B0 consists of a single
node.
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
52
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
From: Cormen, T., C. Leiserson, R. Rivest, and C. Stein,
Introduction to Algorithms, MIT Press, 2001.
Examples
53
Examples
level
From: Cormen, T., C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 2001.
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
54
Properties of Binomial Trees
For the binomial tree Bk,
• the number of nodes = 2k
• the height of the tree = k
• the number of nodes at depth i = kCi
• the degree of root = k (maximum degree)
• if the children of the root are numbered from
left to right by k − 1, k − 2, . . . , 0, child i is
the root of a subtree Bi.
See the proof in the textbook.
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
55
Binomial Heaps
• A binomial heap is a set of binomial trees
with heap properties.
head[H]
10
B0
6
1
8
12 25
18
11 17
B2
27
14 29
38
B3
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
56
Nodes in Binomial Heaps
parent
key
degree
child
Jaruloj Chongstitvatana
sibling
Chapter 2: Advanced Data Structures
57
Examples of Nodes in Binomial Heaps
10
1
8
12 25
18
\
6
3
6
11 17
\
14 29
38
8
2
14
1
11
1
17
0
38
0
27
\
Jaruloj Chongstitvatana
\
Chapter 2: Advanced Data Structures
\
\
58
Find Minimum in Binomial Heaps
y = NIL
x = H.head
min = ∞
while x  NIL
do if x.key < min
then min = x.key
y=x
x = x.sibling
return y
head
BINOMIAL-HEAP-MINIMUM(H)
10
1
12 25
18
6
8
11 17
14 29
38
27
Maximum number of trees = lg n + 1,
the running time of BINOMIAL-HEAP-MINIMUM = O(lg n)
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
59
Link Binomial Heaps
• Make node y the new
head of the linked list of
node z’s children in O(1)
time.
BINOMIAL-LINK(y, z)
y.p = z
y.sibling = z.child
z.child = y
z.degree = z.degree + 1
Jaruloj Chongstitvatana
B2
8
B2
6
11 17
14 29
27
38
y
Chapter 2: Advanced Data Structures
z
B3
60
Union Binomial Heaps
• Link the roots of all trees in both heaps, in a
non-decreasing order of the degree.
• Go through each tree in the heap, and
combine two trees of equal degree in the
heaps, according to one of the following four
cases.
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
61
Union Binomial Heaps: case 1
•
x.degree < next-x.degree
•
move up to the next tree.
From: Cormen, T., C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 2001.
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
62
Union Binomial Heaps: case 2
•
x.degree = next-x.degree = next-x.sibling.degree
•
move up to the next tree (and they will be linked in
next step)
From: Cormen, T., C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 2001.
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
63
•
•
•
x.degree = next-x.degree
Link x and next-x.
Use the node with smaller key as the root.
From: Cormen, T., C. Leiserson,
R. Rivest, and C. Stein, Introduction
to Algorithms, MIT Press, 2001.
Union Binomial Heaps: case 3
x.key  next-x.key
x.key<next-x.key
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
64
Binomial-Heap-Union
BINOMIAL-HEAP-UNION(H1, H2)
H = MAKE-BINOMIAL-HEAP()
H.head =
BINOMIAL-HEAP-MERGE(H1, H2)
Free the objects H1 and H2 but not
the lists they point to
► Cases 1 and 2
then prev-x = x
x = next-x
else if x.key ≤ next-x.key
► Case 3
then x.sibling = next-x.sibling
BINOMIAL-LINK(next-x, x)
► Case 4
else if prev-x = NIL
then H.head = next-x
else prev-x.sibling = next-x
if H.head = NIL
then return H
prev-x = NIL
BINOMIAL-LINK(x,next-x)
x = H.head
x = next-x
next-x = x.sibling
next-x = sibling[x]
while next-x  NIL
do if (x.degree  next-x.degree) or return H
(next-x.sibling  NIL and
next-x.sibling.degree=x.degree)
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
65
Binomial Heaps: Insert a Node
BINOMIAL-HEAP-INSERT(H, x)
H’ = MAKE-BINOMIAL-HEAP()
x.p = NIL
x.child = NIL
x.sibling = NIL
x.degree = 0
H’.head = x
H = BINOMIAL-HEAP-UNION(H, H’ )
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
66
Fibonacci Heaps
Why Fibonacci Heaps
• Every insertion in a binomial heap requires
the structure adjustment.
• Take long time (O(lg n)) for that.
• Do we need to adjust it that often?
• No, if you use Fibonacci heaps instead!
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
68
Fibonacci Heaps
• A Fibonacci heap is a collection of minheap-ordered trees.
• The trees in a Fibonacci heap are not
constrained to be binomial trees.
• Trees within Fibonacci heaps are rooted but
unordered. (unlike trees within binomial
heaps, which are ordered)
• Circular, doubly linked lists are used in
Fibonacci heaps.
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
69
Fibonacci Heaps:Example
From: Cormen, T., C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 2001.
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
70
Properties of unordered binomial tree Uk
• Number of nodes = 2k
• Height of the tree = k
• Number of nodes at depth i = kCi
• The degree of root = k, which is greater than
that of any other node
• The children of the root are roots of subtrees
U0,U1, . . . ,Uk−1 in some order.
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
71
Nodes in Fibonacci Heaps
parent
key
degree
mark
left
right
child
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
72
Links in Fibonacci Heaps
From: Cormen, T., C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 2001.
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
73
Fibonacci Heaps: Insert a node
• Link the node in the root list of H
• Update min[H] if necessary
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
74
Consolidate Heaps
• Find two roots x and y in the root list with
the same degree, where key[x] ≤ key[y].
• Link y to x, using FIB-HEAP-LINK, i.e.
remove y from the root list, and make y a
child of x.
• The field degree[x] is incremented, and the
mark on y, if any, is cleared.
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
75
Time Complexity
Binary Heap
(worst-case)
Binomial Heap
(worst-case)
(1)
(1)
Fibonacci Heap
(amortized)
(1)
(lg n)
Ο(lg n)
(1)
(1)
Ο(lg n)
(1)
(lg n)
(lg n)
Ο(lg n)
(n)
Ο(lg n)
(1)
Decrease-key
(lg n)
(lg n)
(1)
delete
(lg n)
(lg n)
Ο(lg n)
Procedure
Make-heap
Insert
Minimum
Extract-min
Union
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
76
Skip Lists
Skip Lists
• Alternative to binary search trees
• Probabilistic data structure
• Easy to implement
• Good performance in average-case
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
78
Structure of Skip Lists
• Max. level H of the skip list
• An array H of header pointers
• A set of nodes such that a node N contains
H
• a key k and a set of values v,
• the height of h node N, where h<=H, and
• an array of h pointers.
2
4
Jaruloj Chongstitvatana
7
6
9
11
Chapter 2: Advanced Data Structures
nil
12
79
Skip List v.s. Binary search tree
7
4
2
6
11
9
nil
12
7
4
2
Jaruloj Chongstitvatana
11
6
9
12
Chapter 2: Advanced Data Structures
80
Search in a Skip List
Search(list, searchkey)
cn = list.head
►Start at the list head
►Start skip from top level to bottom
for i=list.level downto 1
do ► Forward until key of node exceeds search key
while ((cn.fwd[i]).key < searchkey)
do cn = cn.fwd[i]
cn = cn.fwd[1]
if cn.key = searchkey
then return(cn)
else return(null)
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
81
Search in a Skip List
H
2
7
4
6
11
9
nil
12
Search for 11
7
4
2
Jaruloj Chongstitvatana
11
6
9
12
Chapter 2: Advanced Data Structures
82
Search in a Skip List
H
2
4
7
6
nil
11
9
12
Search for 12
7
4
2
Jaruloj Chongstitvatana
11
6
9
Chapter 2: Advanced Data Structures
12
83
Insert in a Skip List
update[3]
cn
Insert 5
update[1]
update[2]
cn
2
4
7
6
9
11
nil
12
5
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
84
Insert in a Skip List
cn = list.head
update[i].fwd[i] = node
►Search for a place to insert ► Insert the node from level 2 up
for i=list.maxlevel downto 1 ► Toss a coin
do while ((cn.fwd[i]).key <
while (rand() >.5)
node.key)
do addLevel(node)
do cn = cn.fwd[i]
i++
update[i]=cn
► Update link in level i
► The key is already in the list if (i <= list.level)
if cn.fwd[1].key = node.key
then node.fwd[i] = update[i].fwd[i]
then return(false)
update[i].fwd[i] = node
► Insert the node in level 1
else addLevel(list.head)
i=1
(list.head).fwd[i] = node
node.fwd[i] = update[i].fwd[i]
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
85
Delete a node
• Only remove the node, and connect the lost
links.
• The list can become uneven.
• But it is more efficient than deletion in
binary search trees.
Jaruloj Chongstitvatana
Chapter 2: Advanced Data Structures
86