Difference between pages "3.29" and "3.31"
(Difference between pages)
Jump to navigation
Jump to search
(Created page with "In each node of a binary tree store the sub tree sum for the left sub tree. #''Add'': while descending the tree to the left update the sub tree sum by adding the value #''Ins...") |
(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