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


GNU libavl 2.0.1

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

Chapter 11

Section 11.3

1.
 
static void 
rotate_right (struct rtbst_node **yp)
{ struct rtbst_node *y = *yp; struct rtbst_node *x = y-&#62;rtbst_link[0]; if (x-&#62;rtbst_rtag[1] == RTBST_THREAD)
{ x-&#62;rtbst_rtag = RTBST_CHILD; y-&#62;rtbst_link[0] = NULL; } else
y-&#62;rtbst_link[0] = x-&#62;rtbst_link[1]; x-&#62;rtbst_link[1] = y; *yp = x; }

 
static void 
rotate_left (struct rtbst_node **xp)
{ struct rtbst_node *x = *xp; struct rtbst_node *y = x-&#62;rtbst_link[1]; if (y-&#62;rtbst_link[0] == NULL)
{ x-&#62;rtbst_rtag = RTBST_THREAD; x-&#62;rtbst_link[1] = y; } else
x-&#62;rtbst_link[1] = y-&#62;rtbst_link[0]; y-&#62;rtbst_link[0] = x; *xp = y; }

Section 11.5.4

1. There is no general efficient algorithm to find the parent of a node in an RTAVL tree. The lack of left threads means that half the time we must do a full search from the top of the tree. This would increase the execution time for deletion unacceptably.

2.
 
if (p-&#62;rtavl_rtag == RTAVL_THREAD) 
{ if (p-&#62;rtavl_link[0] != NULL) {
&#60;@xref{right-looking, , Case 1 in RTAVL deletion.&#62;,674}
} else
{
&#60;@xref{right-looking, , Case 2 in RTAVL deletion.&#62;,675}
} }
else
{ struct rtavl_node *r = p-&#62;rtavl_link[1]; if (r-&#62;rtavl_link[0] == NULL) {
&#60;@xref{right-looking, , Case 3 in RTAVL deletion.&#62;,676}
} else
{
&#60;@xref{right-looking, , Case 4 in RTAVL deletion.&#62;,677}
} } tree-&#62;rtavl_alloc-&#62;libavl_free (tree-&#62;rtavl_alloc, p);

 
struct rtavl_node *t = p-&#62;rtavl_link[0];
while (t-&#62;rtavl_rtag == RTAVL_CHILD)
  t = t-&#62;rtavl_link[1];
t-&#62;rtavl_link[1] = p-&#62;rtavl_link[1];
pa[k - 1]-&#62;rtavl_link[da[k - 1]] = p-&#62;rtavl_link[0];
This code is included in @refalso{673

 
pa[k - 1]-&#62;rtavl_link[da[k - 1]] = p-&#62;rtavl_link[da[k - 1]];
if (da[k - 1] == 1)
  pa[k - 1]-&#62;rtavl_rtag = RTAVL_THREAD;
This code is included in @refalso{673

 
r-&#62;rtavl_link[0] = p-&#62;rtavl_link[0];
if (r-&#62;rtavl_link[0] != NULL) 
{ struct rtavl_node *t = r-&#62;rtavl_link[0]; while (t-&#62;rtavl_rtag == RTAVL_CHILD) t = t-&#62;rtavl_link[1]; t-&#62;rtavl_link[1] = r; } pa[k - 1]-&#62;rtavl_link[da[k - 1]] = r; r-&#62;rtavl_balance = p-&#62;rtavl_balance; da[k] = 1; pa[k++] = r;
This code is included in @refalso{673

 
struct rtavl_node *s;
int j = k++;
for (;;) 
{ da[k] = 0; pa[k++] = r; s = r-&#62;rtavl_link[0]; if (s-&#62;rtavl_link[0] == NULL) break; r = s; } da[j] = 1; pa[j] = pa[j - 1]-&#62;rtavl_link[da[j - 1]] = s; if (s-&#62;rtavl_rtag == RTAVL_CHILD) r-&#62;rtavl_link[0] = s-&#62;rtavl_link[1]; else
r-&#62;rtavl_link[0] = NULL; if (p-&#62;rtavl_link[0] != NULL)
{ struct rtavl_node *t = p-&#62;rtavl_link[0]; while (t-&#62;rtavl_rtag == RTAVL_CHILD) t = t-&#62;rtavl_link[1]; t-&#62;rtavl_link[1] = s; } s-&#62;rtavl_link[0] = p-&#62;rtavl_link[0]; s-&#62;rtavl_link[1] = p-&#62;rtavl_link[1]; s-&#62;rtavl_rtag = RTAVL_CHILD; s-&#62;rtavl_balance = p-&#62;rtavl_balance;
This code is included in @refalso{673

3.
 
struct rtavl_node *s;
da[k] = 0;
pa[k++] = p;
for (;;) 
{ da[k] = 1; pa[k++] = r; s = r-&#62;rtavl_link[1]; if (s-&#62;rtavl_rtag == RTAVL_THREAD) break; r = s; } if (s-&#62;rtavl_link[0] != NULL)
{ struct rtavl_node *t = s-&#62;rtavl_link[0]; while (t-&#62;rtavl_rtag == RTAVL_CHILD) t = t-&#62;rtavl_link[1]; t-&#62;rtavl_link[1] = p; } p-&#62;rtavl_data = s-&#62;rtavl_data; if (s-&#62;rtavl_link[0] != NULL) r-&#62;rtavl_link[1] = s-&#62;rtavl_link[0]; else
{ r-&#62;rtavl_rtag = RTAVL_THREAD; r-&#62;rtavl_link[1] = p; } p = s;


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

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