trees to the node that roots the subtreeand do not declare or pass any extra variables the more compact the codethe less likely that silly bug will turn up fourthless often usedtraversal (which we have not seen yetis level-order traversal in level-order traversalall nodes at depth are processed before any node at depth level-order traversal differs from the other traversals in that it is not done recursivelya queue is usedinstead of the implied stack of recursion -trees so farwe have assumed that we can store an entire data structure in the main memory of computer supposehoweverthat we have more data than can fit in main memoryandas resultmust have the data structure reside on disk when this happensthe rules of the game changebecause the big-oh model is no longer meaningful the problem is that big-oh analysis assumes that all operations are equal howeverthis is not trueespecially when disk / is involved modern computers execute billions of instructions per second that is pretty fastmainly because the speed depends largely on electrical properties on the other handa disk is mechanical its speed depends largely on the time it takes to spin the disk and to move disk head many disks spin at , rpm thusin min it makes , revolutionshenceone revolution occurs in / of secondor ms on averagewe might expect that we have to spin disk halfway to find what we are looking forbut this is compensated by the time to move the disk headso we get an access time of ms (this is very charitable estimate - ms access times are more common consequentlywe can do approximately disk accesses per second this sounds pretty gooduntil we compare it with the processor speed what we have is billions instructions equal to disk accesses of courseeverything here is rough calculationbut the relative speeds are pretty cleardisk accesses are incredibly expensive furthermoreprocessor speeds are increasing at much faster rate than disk speeds (it is disk sizes that are increasing quite quicklyso we are willing to do lots of calculations just to save disk access in almost all casesit is the number of disk accesses that will dominate the running time thusif we halve the number of disk accessesthe running time will halve here is how the typical search tree performs on disksuppose we want to access the driving records for citizens in the state of florida we assume that we have , , itemsthat each key is bytes (representing name)and that record is bytes we assume this does not fit in main memory and that we are of users on system (so we have / of the resourcesthusin sec we can execute many millions of instructions or perform six disk accesses the unbalanced binary search tree is disaster in the worst caseit has linear depth and thus could require , , disk accesses on averagea successful search would require log disk accessesand since log an average search would require disk accessesor sec in typical randomly constructed treewe would expect that few nodes are three times deeperthese would require about disk accessesor sec an avl tree is somewhat better the worst case of log is unlikely to occurand the typical case is very close to log thus an avl tree would use about disk accesses on averagerequiring sec