Design and Analysis of Algorithms

Overview of Essential Data Structure 687

We thus have each left thread link pointing directly to the predecessor and each right thread pointing to

the successor node in inorder.

The left-most and right-most nodes have special threads, pointing to a special Head node, shown in the

fi gure as HEAD. Having such head node simplifi es the algorithms considerably and especially, empty trees

are handled properly.

If we denote by $P the predecessor of a node P in inorder, and by P$ the successor of P, then we can

show the arrangements of left and right links in a threaded binary tree as shown in Fig. C.18.

Fig. C.18 The predecessor function

Fig. C.17