Difference between pages "3.27" and "3.31"

Latest revision as of 18:08, 20 September 2020

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.

@@ Line 1: / Line 1: @@
-Let's put into the black box whole set <math>S=\{x_i\}_{i=1}^n</math>. If <math>bb(S)</math> is True, then such a subset exists and we can go on:
+Init:
-# R:=S
+  k=0
-# for i:=1 to n do
-## If <math>bb(R/\{x_i\})</math> is True then <math>R:=R/\{x_i\}</math>
-When this iteration is finished R will be subset of S that adds up to k.
-Above solution works even when there are multiple subsets that add up to k.
+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]]