python framework for balancing search trees our treemap classintroduced in section is concrete map implementation that does not perform any explicit balancing operations howeverwe designed that class to also serve as base class for other subclasses that implement more advanced tree-balancing algorithms summary of our inheritance hierarchy is shown in figure linkedbinarytree (section mapbase (section treemap (section avltreemap (section splaytreemap (section redblacktreemap (section figure our hierarchy of balanced search trees (with references to where they are definedrecall that treemap inherits multiply from linkedbinarytree and mapbase hooks for rebalancing operations our implementation of the basic map operations in section includes strategic calls to three nonpublic methods that serve as hooks for rebalancing algorithmsa call to rebalance insert(pis made from within the setitem method immediately after new node is added to the tree at position call to rebalance delete(pis made each time node has been deleted from the treewith position identifying the parent of the node that has just been removed formallythis hook is called from within the public delete(pmethodwhich is indirectly invoked by the public delitem (kbehavior we also provide hookrebalance access( )that is called when an item at position of tree is accessed through public method such as getitem this hook is used by the splay tree structure (see section to restructure tree so that more frequently accessed items are brought closer to the root we provide trivial declarations of these three methodsin code fragment having bodies that do nothing (using the pass statementa subclass of treemap may override any of these methods to implement nontrivial action to rebalance tree this is another example of the template method design patternas seen in section