of the treebut generally it is worthwhile the earliest type of self-balancing binary search tree was the avl tree (named after its inventors adelson-velskii and landisthese maintain the difference in heights of the two sub-trees of all nodes to be at most one this requires the tree to be periodically rebalanced by performing one or more tree rotations as discussed abovebut the complexity of insertiondeletion and search remain at (log nthe general idea is to keep track of the balance factor for each nodewhich is the height of the left sub-tree minus the height of the right sub-tree by definitionall the nodes in an avl-tree will have balance factor in the integer range [- howeverinsertion or deletion of node could leave that in the wider range [- requiring tree-rotation to bring it back into avl form exercisefind some suitable algorithms for performing efficient avl tree rotations compare them with other self-balancing approaches such as red-black trees -trees -tree is generalization of self-balancing binary search tree in which each node can hold more than one search key and have more than two children the structure is designed to allow more efficient self-balancingand offers particular advantages when the node data needs to be kept in external storage such as disk drives the standard (knuthdefinition isdefinition -tree of order is tree which satisfies the following conditionsevery node has at most children every non-leaf node (except the root nodehas at least / children the root nodeif it is not leaf nodehas at least two children non-leaf node with children contains search keys which act as separation values to divide its sub-trees all leaf nodes appear in the same leveland carry information there appears to be no definitive answer to the question of what the "bin " -treestands for it is certainly not "binary"but it could equally well be "balanced""broador "bushy"or even "boeingbecause they were invented by people at boeing research labs the standard representation of simple order example with search keys would bethe search keys held in each node are ordered ( in the example)and the non-leaf node' search keys ( the items and in the exampleact as separation values to divide