21
Adding
❶Pretend that you are
trying to find the key,
but stop when there is
no node to move to.
Oklahoma
Colorado
Florida
Iowa
22
Adding
❶Pretend that you are
trying to find the key,
but stop when there is
no node to move to.
Oklahoma
Colorado
Florida
Iowa
23
Adding
❶Pretend that you are
trying to find the key,
but stop when there is
no node to move to.
Oklahoma
Colorado
Florida
Iowa
24
Adding
❶Pretend that you are
trying to find the key,
but stop when there is
no node to move to.
Oklahoma
Colorado
Florida
Iowa
25
…and this is the location for Iowa.
Adding
❶Pretend that you are
trying to find the key,
but stop when there is
no node to move to.
Oklahoma
Colorado
Florida
26
Adding
Oklahoma
Colorado
Florida
Where would you
add this state?
Kazakhstan
27
Adding
Oklahoma
Colorado
Florida
Kazakhstan is the
new right child
of Iowa?
28
2. Some items are harder to remove than others. In particular, an item
3. Finally, once the item is in a spot that is easy to remove, we remove
it.
Removing an Item with a
Given Key
❶Find the item.
❷If necessary, swap the
item with one that is
easier to remove.
Oklahoma
Colorado
Florida
29
Removing ‘Florida’
Florida
Kazakhstan
30
In the second step we need to swap Florida with another item that is
Removing ‘Florida’
Oklahoma
Colorado
Florida
31
Removing ‘Florida’
Oklahoma
Colorado