Difference between pages "3.27" and "3.31"
(Difference between pages)
Jump to navigation
Jump to search
(Created page with "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: # R:=S # for i:=1 to n do ##...") |
(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...") |
||
Line 1: | Line 1: | ||
− | + | 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]] | Back to [[Chapter 3]] |
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.
Back to Chapter 3