Data structure cheat sheet: Difference between revisions
Jump to navigation
Jump to search
Hoppinglife (talk | contribs) |
Hoppinglife (talk | contribs) |
||
| Line 40: | Line 40: | ||
General traversal of binary trees all takes <math>O(n)</math> time, except for the root node, exactly two times of the search routine was called for each node. | General traversal of binary trees all takes <math>O(n)</math> time, except for the root node, exactly two times of the search routine was called for each node. | ||
For Binary Search Trees, Min/Max | For Binary Search Trees, Min/Max is easy - just follow the left/right link. Getting successor/predecessor is tricker: the next element of x is either a) the minimum element of the right subtree, or b) the lowest ancestor of x whose left child is also the ancestor of x. | ||
==== Insertion and Deletion ==== | |||
Insertion is relatively simple, just follows the search procedure until you find an empty node. | |||
Deletion is more complicated: if the target <math>z</math> has two children, we find the successor of <math>z</math>, if it is the right child of <math>z</math>, it can be replaced by y, otherwise, we first replace y by its right child, then replace z using y. | |||
=== Heap === | === Heap === | ||