- The focus of our efforts in balancing trees has been to keep the trees properly structured
- Consequently, whenever a newly inserted node threatens a tree’s balance, action is taken to correct the imbalance
- This can be done for the entire tree, using the DSW technique, or locally, using the AVL process
- Since trees are used to handle items quickly, it is the speed of operations and not the tree’s structure that is critical
- Consider the idea that not all items in a tree are likely to be used with equal frequency
- If we keep track of the most frequently accessed items, and structure the tree to improve access to them, we can improve performance
- This is the basis for self-adjusting trees
- The strategy is to migrate up the tree those elements used most often, creating a “priority tree”
- Each node could have a counter to record accesses; the tree could be rearranged to move highest counts up in the tree
- A second approach is based on the assumption that an item that has been accessed will be accessed soon again
- Each time an element is accessed, it is moved up the tree
- New elements are simply added where appropriate without restructuring
- Although this could promote infrequently accessed objects, over a period of use the more frequently used items will occupy the higher levels of the tree
- Self-Restructuring Trees
- Brian Allen, Ian Munroe, and James Bitner proposed a strategy with two possibilities, shown in Figure
- Single rotation – if an element in a child is accessed, rotate the child around the parent, unless it is the root.
Moving to the root – the parent-child rotation is repeated until the element that was accessed is the root
- In the single-rotation approach, the more often an item is accessed the closer it moves to the root, so access to the element improves
- With move-to-the-root, the assumption is the accessed element will be accessed soon again, so it immediately moves to the root
- Even if the item isn’t used right away, it will remain close to the root for further access
- Unfortunately, these strategies don’t work well in the case of skewed trees such as we’ve seen earlier; although they will improve slowly
- This situation is displayed in Figure below