not be larger than that isthe height of node' left subtree may be no more than one level different from the height of its right subtree following insertionthe root of the lowest subtree into which the new node was inserted is checked if the height of its children differs by more than single or double rotation is performed to equalize their heights the algorithm then moves up and checks the node aboveequalizing heights if necessary this check continues all the way back up to the root search times in an avl tree are (lognbecause the tree is guaranteed to be balanced howeverbecause two passes through the tree are necessary to insert (or deletea nodeone down to find the insertion point and one up to rebalance the treeavl trees are not as efficient as red-black trees and are not used as often the other important kind of balanced tree is the multiway treein which each node can have more than two children we'll look at one version of multiway treesthe - treein the next one problem with multiway trees is that each node must be larger than for binary tree because it needs reference to every one of its children summary it' important to keep binary search tree balanced to ensure that the time necessary to find given node is kept as short as possible inserting data that has already been sorted can create maximally unbalanced treewhich will have search times of (nin the red-black balancing schemeeach node is given new characteristica color that can be either red or black set of rulescalled red-black rulesspecifies permissible ways that nodes of different colors can be arranged these rules are applied while inserting (or deletinga node color flip changes black node with two red children to red node with two black children in rotationone node is designated the top node right rotation moves the top node into the position of its right childand the top node' left child into its position left rotation moves the top node into the position of its left childand the top node' right child into its position color flipsand sometimes rotationsare applied while searching down the tree to find where new node should be inserted these flips simplify returning the tree to red-black correctness following an insertion