van-Emde-Boas-Tree

Implementation of the van Emde Boas Tree, used in representing disjoint sets.

Operation

Insert

• consists of 3 cases, value to insert is val
• Case 1 (val<min), Insert current node’s min in child cluster, make current node’s min as val
• Case 2 (val>max), make current node max as val, insert max in child cluster
• Case 3 (valmin), insert val in child cluster
• Insert the cluster num into the summary node

Delete

• consists of 3 cases, value to insert is val
• Case 1 (val == min), make successor(val) as min in current node, in child node delete successor(val)
• Case 2 (val == max), make predecessor(val) as min in current node, in child node delete predecessor(val)
• Case 3 (valmin), delete val in child cluster
• Update summary node if the cluster is empty

Min

• return min attribute from current node

Max

• return max attribute from current node

Search

• search val in the tree
• Case 1 (val < min or val > max), return false, element not present in tree
• Case 2 (val == min or val == max), return true
• Case 3 (val > min and val < max), search val in child cluster

Predecessor

• find predecessor of val, without checking if val is present in the tree
• Case 1 (val =< min), no predecessor, return -1
• Case 2(val > max), return max as predecessor
• Case 3(val > min and val <= max), check for predecessor in same node if no predecessor then check max of left sibling, if max is -1 then check next left sibling and so on

Successor

• find successor of val without checking if val is present in the tree
• Case 1 (val < min), return min as the successor
• Case 2(val >= max), no successor return -1
• Case 3(val > min and val <= max), check for successor in same node if no successor then check min of right sibling, if min is -1 then check next right sibling and so on