red-black trees the times for insertion and deletion are increased by constant factor because of having to perform color flips and rotations on the way down and at the insertion point on the averagean insertion requires about one rotation thereforeinsertion still takes (log ntime but is slower than insertion in the ordinary binary tree because in most applications there will be more searches than insertions and deletionsthere is probably not much overall time penalty for using red-black tree instead of an ordinary tree of coursethe advantage is that in red-black tree sorted data doesn' lead to slow (nperformance red-black tree implementation if you're writing an insertion routine for red-black treesall you need to do (irony intendedis to write code to carry out the operations described in the preceding sections as we notedshowing and describing such code is beyond the scope of this book howeverhere' what you'll need to think about you'll need to add red-black field (which can be type booleanto the node class you can adapt the insertion routine from the tree java program (listing in on the way down to the insertion pointcheck if the current node is black and its two children are both red if sochange the color of all three (unless the parent is the rootwhich must be kept blackafter color flipcheck that there are no violations of rule if soperform the appropriate rotationsone for an outside grandchildtwo for an inside grandchild when you reach leaf nodeinsert the new node as in tree javamaking sure the node is red check again for red-red conflictsand perform any necessary rotations perhaps surprisinglyyour software need not keep track of the black height of different parts of the tree (although you might want to check this during debuggingyou need to check only for violations of rule red parent with red childwhich can be done locally (unlike checks of black heightsrule which would require more complex bookkeepingif you perform the color flipscolor changesand rotations described earlierthe black heights of the nodes should take care of themselves and the tree should remain balanced the rbtree workshop applet reports black-height errors only because the user is not forced to carry out the insertion algorithm correctly other balanced trees the avl tree is the earliest kind of balanced tree it' named after its inventorsadelson-velskii and landis in avl trees each node stores an additional piece of datathe difference between the heights of its left and right subtrees this difference may