• 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