www.delorie.com/gnu/docs/avl/libavl_286.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

Chapter 10

1. If we already have right-threaded trees, then we can get the benefits of a left-threaded tree just by reversing the sense of the comparison function, so there is no additional benefit to left-threaded trees.

Section 10.5.1

1.
 
struct rtbst_node *s = r-&#62;rtbst_link[0];
while (s-&#62;rtbst_link[0] != NULL) 
{ r = s; s = r-&#62;rtbst_link[0]; } p-&#62;rtbst_data = s-&#62;rtbst_data; if (s-&#62;rtbst_rtag == RTBST_THREAD) r-&#62;rtbst_link[0] = NULL; else
r-&#62;rtbst_link[0] = s-&#62;rtbst_link[1]; p = s;

Section 10.5.2

1. This alternate version is not really an improvement: it runs up against the same problem as right-looking deletion, so it sometimes needs to search for a predecessor.

 
struct rtbst_node *s = r-&#62;rtbst_link[1];
while (s-&#62;rtbst_rtag == RTBST_CHILD) 
{ r = s; s = r-&#62;rtbst_link[1]; } p-&#62;rtbst_data = s-&#62;rtbst_data; if (s-&#62;rtbst_link[0] != NULL)
{ struct rtbst_node *t = s-&#62;rtbst_link[0]; while (t-&#62;rtbst_rtag == RTBST_CHILD) t = t-&#62;rtbst_link[1]; t-&#62;rtbst_link[1] = p; r-&#62;rtbst_link[1] = s-&#62;rtbst_link[0]; }
else
{ r-&#62;rtbst_link[1] = p; r-&#62;rtbst_rtag = RTBST_THREAD; } p = s;


  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003