www.delorie.com/gnu/docs/avl/libavl_135.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
It take a little more effort to insert a new node into a threaded BST than into an unthreaded one, but not much more. The only difference is that we now have to set up the new node's left and right threads to point to its predecessor and successor, respectively.
Fortunately, these are easy to figure out. Suppose that new node n is the right child of its parent p (the other case is symmetric). This means that p is n's predecessor, because n is the least node in p's right subtree. Moreover, n's successor is the node that was p's successor before n was inserted, that is to say, it is the same as p's former right thread.
Here's an example that may help to clear up the description. When new node 3 is inserted as the right child of 2, its left thread points to 2 and its right thread points where 2's right thread formerly did, to 4:
The following code unifies the left-side and right-side cases using dir, which takes the value 1 for a right-side insertion, 0 for a left-side insertion. The side opposite dir can then be expressed simply as !dir.
if (tree->tbst_root != NULL) for (p = tree->tbst_root; ; p = p->tbst_link[dir]) |
n = tree->tbst_alloc->libavl_malloc (tree->tbst_alloc, sizeof *n); if (n == NULL) return NULL; tree->tbst_count++; n->tbst_data = item; n->tbst_tag[0] = n->tbst_tag[1] = TBST_THREAD; n->tbst_link[dir] = p->tbst_link[dir]; if (tree->tbst_root != NULL) |
See also: [ Knuth 1997], algorithm 2.3.1I.
Exercises:
1. What happens if we reverse the order of the final if statement above and the following assignment? [answer]
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
webmaster donations bookstore | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |