www.delorie.com/gnu/docs/avl/libavl_190.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
The previous section implemented the "right-looking" form of deletion used elsewhere in libavl. Compared to deletion in a fully threaded binary tree, the benefits to using an RTBST with this kind of deletion are minimal:
This is hardly worth it. We saved at most one assignment per call. We need something better if it's ever going to be worthwhile to use right-threaded trees.
Fortunately, there is a way that we can save a little more. This is by changing our right-looking deletion into left-looking deletion, by switching the use of left and right children in the algorithm. In a BST or TBST, this symmetrical change in the algorithm would have no effect, because the BST and TBST node structures are themselves symmetric. But in an asymmetric RTBST even a symmetric change can have a significant effect on an algorithm, as we'll see.
The cases for left-looking deletion are outlined in the same way as for right-looking deletion:
if (p->rtbst_link[0] == NULL) |
If the node to delete p has a right child but no left child, we can just replace it by its right child. There is no right thread to update in p's left subtree because p has no left child, and there is no left thread to update because a right-threaded tree has no left threads.
The deletion looks like this if p's right child is designated x:
q->rtbst_link[dir] = p->rtbst_link[1]; |
This case is analogous to case 2 in right-looking deletion covered earlier. The same discussion applies.
q->rtbst_link[dir] = p->rtbst_link[dir]; if (dir == 1) q->rtbst_rtag = RTBST_THREAD; |
If p has a left child r that itself has a right thread, then we replace p by r. Node r receives p's former right link, as shown here:
There is no need to fiddle with threads. If r has a right thread then it gets replaced by p's right child or thread anyhow. Any right thread within r's left subtree either points within that subtree or to r. Finally, r's right subtree cannot cause problems.
r->rtbst_link[1] = p->rtbst_link[1]; r->rtbst_rtag = p->rtbst_rtag; q->rtbst_link[dir] = r; |
The final case handles deletion of a node p with a left child r that in turn has a right child. The code here follows the same pattern as <@xref{\NODE\, , Case 4 in TBST deletion.>,263} (see the discussion there for details). The first step is to find the predecessor s of node p:
struct rtbst_node *s; for (;;) |
Next, we update r, handling two subcases depending on whether s has a left child:
if (s->rtbst_link[0] != NULL) r->rtbst_link[1] = s->rtbst_link[0]; else |
The final step is to copy p's fields into s, then set q's child pointer to point to s instead of p. There is no need to chase down any threads.
s->rtbst_link[0] = p->rtbst_link[0]; s->rtbst_link[1] = p->rtbst_link[1]; s->rtbst_rtag = p->rtbst_rtag; q->rtbst_link[dir] = s; |
Exercises:
1. Rewrite <@xref{\NODE\, , Case 4 in left-looking RTBST deletion.>,392} to replace the deleted node's rtavl_data by its predecessor, then delete the predecessor, instead of shuffling pointers. (Refer back to Exercise 4.8-3 for an explanation of why this approach cannot be used in libavl.) [answer]
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
webmaster | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |