(noperation time sizeisempty ( findinsertremove (lognfindall (logn sthus( , trees provide for fast dictionary search and update operations ( , trees also have an interesting relationship to the data structure we discuss next red-black trees although avl trees and ( , trees have number of nice propertiesthere are some dictionary applications for which they are not well suited for instanceavl trees may require many restructure operations (rotationsto be performed after removaland ( , trees may require many fusing or split operations to be performed after either an insertion or removal the data structure we discuss in this sectionthe redblack treedoes not have these drawbackshoweveras it requires that only ( structural changes be made after an update in order to stay balanced red-black tree is binary search tree (see section with nodes colored red and black in way that satisfies the following propertiesroot propertythe root is black external propertyevery external node is black internal propertythe children of red node are black depth propertyall the external nodes have the same black depthdefined as the number of black ancestors minus one (recall that node is an ancestor of itself an example of red-black tree is shown in figure