Difference between revisions of "TADM2E 3.15"
From Algorithm Wiki
(Recovering wiki) |
|||
| (One intermediate revision by one other user not shown) | |||
| Line 8: | Line 8: | ||
Search X: | Search X: | ||
| − | return (A[X] | + | return (A[X] < k) and (B[A[X]] == X) |
Delete X: | Delete X: | ||
| − | A[k] = A[X]; | + | A[B[k]] = A[X]; |
B[A[X]] = B[k]; | B[A[X]] = B[k]; | ||
k = k-1; | k = k-1; | ||
| + | |||
| + | Please note that this data structure doesn't support inserting the same X more than once. | ||
Latest revision as of 05:42, 4 June 2015
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.
