Binary Trees
Volume Number: 6>replyPtr Issue Number: 8>replyPtr$ !Column Tag: Language Translation>replyPtrC Binary Trees 
>replyPtrV 'By Clifford Story, Mouunt Prospect, ILÄy U
Note: Source code files accompanying article are located on MacTech CD-ROM or>replyPtr source code disks.>replyPtr A. Introduction>replyPtr $IThis article, Part V, I’m going to take an excursion away from language>replyPtr Qtranslation and develop some support routines. In particular, I’m going to create>replyPtr Sroutines to handle binary trees; later, I’ll use these routines to implement a symbol>replyPtr 9table for the new Canon tool and the fabled Inline tool.>replyPtrfl$KThere are a couple of “Why?” questions to answer. First question, why fill>replyPtrÎ SMacTutor with a long article on something that is taught in every college computer>replyPtr˜ Tdepartment in the U.S.? Ah, but not all of us have computer degrees; I don’t, for>fixBtnName Yexample. And while you can find the subject in various books, I couldn’t find a decent>replyPtr Yexplanation of balanced binary trees -- I had to figure it out from hints I gleaned from>replyPtr RKnuth’s discussion (Searching and Sorting, pages 451 -- 457). Second question, why>fixBtnName' Ya binary tree? Aren’t symbol tables usually done with hash tables? Well, yes, this is>replyPtr Smy impression, and Aho and Ullman state that hashing is “[t]he most efficient and>replyPtr Mcommonly used method” for maintaining symbol tables (The Theory of Parsing,>replyPtr RTranslation, and Compiling, volume II, page 793). So why a binary tree? I’m sorry,>fixBtnNameW )I haven’t got an answer for that one...>replyPtr $RIf you should ever write your own compiler, I guess you should use a hash table. >fixBtnNameo UAfter all, Aho & Ullman’s opinion carries a lot of weight. In the meantime, binary>replyPtr $trees are fun, so sit up and enjoy!>fixBtnName B. Simple Binary Trees>fixBtnName $LA binary tree is a tree with at most two sub-trees at each node. These are>fixBtnName Tcommonly called the left and right sub-trees. Searching a binary tree is very simple:>fixBtnName Xtake the left branch if the search key is less than the node’s value, and the right branch>fixBtnName Rif it is greater. Keep going until you get either an exact match (in which case the>fixBtnName :search succeeds), or a nil pointer (in which case the search fails).>fixBtnNamefi$KThe example program I have written implements search and insertion, as well as>replyPtr a recursive dump routine. It does not do deletions. I haven’t any use for deletions in a>fixBtnNameˆ 9symbol table, so I have left that part as an exercise...>replyPtr B(1). Node Structureapplication!$VEach node has four fields: the node’s value or key, a pointer to the left sub-tree,application- Ya pointer to the right sub-tree, and the data. Here is the node structure I will use in>replyPtr9 my example:applicationS$Û>replyPtr`$/* 1 */applicationwtypedef struct nodeapplication {application char *key;>replyPtr struct node *left;>replyPtr struct node *right;application char *data;application } node;applicationı>replyPtr‡$>The data for this example is some arbitrary character string.applicationÏ$NI’ll going to create new nodes with the Mac trap NewPtr. I would usually use anapplication¯ Zarray of nodes with a free list, and allocate them myself; I’m using NewPtr in this caseapple for simplicity’s sake.apple$Û>replyPtr+$/* 2 */appleB// createnode>replyPtrX
>replyPtrV 'By Clifford Story, Mouunt Prospect, ILÄy U Note: Source code files accompanying article are located on MacTech CD-ROM or>replyPtr source code disks.>replyPtr A. Introduction>replyPtr $IThis article, Part V, I’m going to take an excursion away from language>replyPtr Qtranslation and develop some support routines. In particular, I’m going to create>replyPtr Sroutines to handle binary trees; later, I’ll use these routines to implement a symbol>replyPtr 9table for the new Canon tool and the fabled Inline tool.>replyPtrfl$KThere are a couple of “Why?” questions to answer. First question, why fill>replyPtrÎ SMacTutor with a long article on something that is taught in every college computer>replyPtr˜ Tdepartment in the U.S.? Ah, but not all of us have computer degrees; I don’t, for>fixBtnName Yexample. And while you can find the subject in various books, I couldn’t find a decent>replyPtr Yexplanation of balanced binary trees -- I had to figure it out from hints I gleaned from>replyPtr RKnuth’s discussion (Searching and Sorting, pages 451 -- 457). Second question, why>fixBtnName' Ya binary tree? Aren’t symbol tables usually done with hash tables? Well, yes, this is>replyPtr Smy impression, and Aho and Ullman state that hashing is “[t]he most efficient and>replyPtr Mcommonly used method” for maintaining symbol tables (The Theory of Parsing,>replyPtr RTranslation, and Compiling, volume II, page 793). So why a binary tree? I’m sorry,>fixBtnNameW )I haven’t got an answer for that one...>replyPtr $RIf you should ever write your own compiler, I guess you should use a hash table. >fixBtnNameo UAfter all, Aho & Ullman’s opinion carries a lot of weight. In the meantime, binary>replyPtr $trees are fun, so sit up and enjoy!>fixBtnName B. Simple Binary Trees>fixBtnName $LA binary tree is a tree with at most two sub-trees at each node. These are>fixBtnName Tcommonly called the left and right sub-trees. Searching a binary tree is very simple:>fixBtnName Xtake the left branch if the search key is less than the node’s value, and the right branch>fixBtnName Rif it is greater. Keep going until you get either an exact match (in which case the>fixBtnName :search succeeds), or a nil pointer (in which case the search fails).>fixBtnNamefi$KThe example program I have written implements search and insertion, as well as>replyPtr a recursive dump routine. It does not do deletions. I haven’t any use for deletions in a>fixBtnNameˆ 9symbol table, so I have left that part as an exercise...>replyPtr B(1). Node Structureapplication!$VEach node has four fields: the node’s value or key, a pointer to the left sub-tree,application- Ya pointer to the right sub-tree, and the data. Here is the node structure I will use in>replyPtr9 my example:applicationS$Û>replyPtr`$/* 1 */applicationwtypedef struct nodeapplication {application char *key;>replyPtr struct node *left;>replyPtr struct node *right;application char *data;application } node;applicationı>replyPtr‡$>The data for this example is some arbitrary character string.applicationÏ$NI’ll going to create new nodes with the Mac trap NewPtr. I would usually use anapplication¯ Zarray of nodes with a free list, and allocate them myself; I’m using NewPtr in this caseapple for simplicity’s sake.apple$Û>replyPtr+$/* 2 */appleB// createnode>replyPtrXapple‹ thelength = 1 + strlen(thekey);appleÁthenode->key = (char *)appleÚ(NewPtr(thelength);>replyPtrhandle if (thenode->key == nil)>replyPtr({aliasHandle(DisposPtr((Ptr)thenode);>replyPtr(return(nil);>replyPtr)(}aliasHandle4BlockMove((Ptr)thekey,>replyPtr?((Ptr)thenode->key, thelength);>replyPtrUthenode->left = nil;>replyPtr`thenode->right = nil;aliasHandlev!thelength = 1 + strlen(thedata);>replyPtr thenode->data = (char *)>replyPtr (NewPtr(thelength);>replyPtr if (thenode->data == nil)aliasHandle ({aliasHandle (DisposPtr((Ptr)thenode->key);aliasHandle (DisposPtr((Ptr)thenode);>replyPtr(return(nil);>replyPtr(}aliasHandleŸBlockMove((Ptr)thedata,aliasHandle‰( (Ptr)thenode->data, thelength);aliasHandle˙return(thenode);>replyPtr}aliasesı>replyPtr7$TFinally, I’ll start off the table with a head node, a dummy node with no data thataliasesC Mpoints to the true root of the tree. That way, I can create the tree before any>replyPtrO Finsertions; I don’t have to special-case inserting data into a nil tree.aliasesi B(2). Finding a Node by Key>replyPtrz$RAs I said above, looking up a node by key is easy. The routine below is passed aaliases Spointer to the root node of the tree, and the search key. It starts with the root and>replyPtr ]follows the algorithm, until either it finds the node it is looking for and falls out of the>replyPtr -loop, or finds a nil pointer and returns it.>replyPtr $Û>replyPtr$/* 3 */aliases‹
// lookupaliasesÚnode *lookup(node *thetable,>replyPtrresource char *thekey)alias{aliasnode *thenode;>replyPtr)int compare;>replyPtr?thenode = thetable;aliasUwhile (compare = strcmp(>replyPtr`6thekey, thenode->key))>replyPtrk({aliasv(if (compare < 0)>replyPtr 6thenode = thenode->left;>replyPtr (else>replyPtr 6thenode = thenode->right;alias (if (thenode == nil)alias 6return(nil);>replyPtr (}aliasreturn(thenode);>replyPtr‰}aliasÚı>replyPtr B(3). Inserting a Nodeabsolute*$LThis routine inserts a new node into the tree. First, it performs a search notabsolute6 Zunlike that in the “lookup” routine, except that it returns nil (indicating failure) ifabsoluteB Ythe search is successful -- i.e., a duplicate key exists. If, on the other hand, it finds a>replyPtrN Rnil pointer, then that is the place for the new node, and the routine inserts it.absoluteh$Û>replyPtru$/* 4 */absolute
// insertabsolute node *insert(node *thetable,>replyPtr (char *thekey, char *thedata)>replyPtr {absolutenode *thenode;>replyPtrŸint compare;>replyPtr‰node *thechild;absolute˙thenode = thetable;buttonwhile (compare = strcmp(>replyPtr6thekey, thenode->key))>replyPtr&({button<(if (compare < 0)>replyPtrG6{button]6thechild = thenode->left;buttonh6if (thechild == nil)>replyPtrsC{button~Cthenode->left = createnode(>replyPtr Qthekey, thedata);button Creturn(thenode->left);>replyPtr C}button 6}button(else>replyPtr6{button·6thechild = thenode->right;>replyPtrÏ6if (thechild == nil)>replyPtr˜C{customGetFileCthenode->right = createnode(customGetFileQthekey, thedata);customGetFileCreturn(thenode->right);customGetFile#C}customGetFile96}customGetFileO(thenode = thechild;customGetFilee(}customGetFile{return(nil);>replyPtr }customGetFile ı>replyPtr B(4). Dumping and DestroyingcustomGetFile $RTree structures are natural candidates for recursive routines, and here are two. customGetFile„ VThe “dump” routine displays the entire tree, in key order. The “destroy” routinecustomGetFileÔ 5disposes of all the dynamic memory used by the tree.>replyPtr
$Û>replyPtr
$/* 5 */current-// dumpcurrentCvoid dump(node *thetable)currentN{currentdif (thetable == nil)>replyPtr
o(return;current dump(thetable->left);current !printf(“%10s - %10s - %10s\n”,>replyPtr
(thetable->key,>replyPtr
(thetable->left ?>replyPtr
6thetable->left->key : “nil”,>replyPtr
(thetable->right ?current 6!thetable->right->key : “nil”);>replyPtr
Ëdump(thetable->right);>replyPtr
handle}curDestAliasHndl// destroy>replyPtr*void destroy(node *thetable)>replyPtr5{curDestAliasHndlKif (thetable == nil)>replyPtrV(return;curDestAliasHndlldestroy(thetable->left);>replyPtrwdestroy(thetable->right);curDestAliasHndl DisposPtr((Ptr)thetable->key);>replyPtr DisposPtr((Ptr)thetable->data);curDestAliasHndl DisposPtr((Ptr)thetable);curDestAliasHndl }curDestAliasHndlı>replyPtr‚ B(5). A Test Shellcreate $ı>replyPtr$/* 6 */create$// Binary.ccreate/// --------create: // Binary tree search and insertioncreateP#pragma load “ managers”createf// Constants and Macroscreate|#define nil 0create // Types>replyPtr $typedef enum {false, true} logical;create typedef struct nodecreate{create char *key;>replyPtrflstruct node *left;>replyPtrÍstruct node *right;createıchar *data;doRenameButtonhandle} node;doRenameButton// PrototypesdoRenameButton,void initmac();doRenameButton7