3.31

From The Algorithm Design Manual Solution Wiki
Revision as of 18:08, 20 September 2020 by Algowikiadmin (talk | contribs) (Created page with "Init: k=0 Insert X: k = k+1; A[X] = k; B[k] = X; Search X: return (A[X] < k) and (B[A[X]] == X) Delete X: A[B[k]] = A[X]; B[A[X]] = B[k]; k = k-1; Ple...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Init:

 k=0

Insert X:

 k = k+1; 
 A[X] = k; 
 B[k] = X;

Search X:

 return (A[X] < k) and (B[A[X]] == X)

Delete X:

 A[B[k]] = A[X]; 
 B[A[X]] = B[k]; 
 k = k-1;

Please note that this data structure doesn't support inserting the same X more than once.


Back to Chapter 3