5.5.1 Step 1: Search

The only difference between this search and an ordinary search in a BST is that we have to keep track of the nodes above the one we're deleting. We do this by pushing them onto the stack defined above. Each iteration through the loop compares item to p's data, pushes the node onto the stack, moves down in the proper direction. The first trip through the loop is something of an exception: we hard-code the comparison result to -1 so that the pseudo-root node is always the topmost node on the stack. When we find a match, we set item to the actual data item found, so that we can return it later.

165. <Step 1: Search AVL tree for item to delete 165> =
k = 0;
p = (struct avl_node *) &tree->avl_root;
for (cmp = -1; cmp != 0; 
     cmp = tree->avl_compare (item, p->avl_data, tree->avl_param)) 
  {
int dir = cmp > 0;
pa[k] = p;
da[k++] = dir;
p = p->avl_link[dir];
if (p == NULL)
return NULL;
}
item = p->avl_data;

This code is included in 164 and 220.

旋转膝落：（空投）↑以外+C或D 
杰克小刀踢：→+B

飞之技巧：（跳跃中）↓+D

雷韧拳：↓↘→+A或C 

空中雷韧拳：（跳跃中）↓↘→+A或C 

真空片手驹：↓↙←+A或C 

超级闪电踢：→↓↘+B或D

居合蹴：↓↘→+B或D 

反动三段蹴：→↘↓↙←+B或D 

红丸投：（近身）→↘↓↙←→+A或C 

雷光拳：↓↘→↓↘→+A或C 

大发电者：（近身）→↘↓↙←→↘↓↙←+A或C 

5.5 Deletion

Deletion in an AVL tree is remarkably similar to insertion. The steps that we go through are analogous:

1. Search for the item to delete.
2. Delete the item.
3. Update balance factors.
4. Rebalance the tree, if necessary.
5. Finish up and return.

The main difference is that, after a deletion, we may have to rebalance at more than one level of a tree, starting from the bottom up. This is a bit painful, because it means that we have to keep track of all the nodes that we visit as we search for the node to delete, so that we can then move back up the tree. The actual updating of balance factors and rebalancing steps are similar to those used for insertion.

The following sections cover deletion from an AVL tree in detail. Before we get started, here's an outline of the function.

164. <AVL item deletion function 164> =
void *
avl_delete (struct avl_table *tree, const void *item) 
{
  /* Stack of nodes. */
struct avl_node *pa[AVL_MAX_HEIGHT]; /* Nodes. */
unsigned char da[AVL_MAX_HEIGHT];    /* avl_link[] indexes. */
int k;                               /* Stack pointer. */
struct avl_node *p;   /* Traverses tree to find node to delete. */
int cmp;              /* Result of comparison between item and p. */
assert (tree != NULL && item != NULL);
<Step 1: Search AVL tree for item to delete 165>
<Step 2: Delete item from AVL tree 166>
<Steps 3–4: Update balance factors and rebalance after AVL deletion 171>
<Step 5: Finish up and return after AVL deletion 176>
}

This code is included in 145.

See also: [Knuth 1998b], pages 473–474; [Pfaff 1998].

• Deleting an AVL Node Step 1 - Search
• Deleting an AVL Node Step 2 - Delete
• Deleting an AVL Node Step 3 - Update
• Deleting an AVL Node Step 4 - Rebalance
• Deleting an AVL Node Step 5 - Finish Up
• AVL Deletion Symmetric Case

低踢：→+B 

滑步：↘+B 

旋风拳：←↙↓↘→+A或C 

爆烈拳：A或C连按

爆烈拳终结：爆烈拳中↓↘→+A或C 

虎破脚：→↓↘+B或D 

电光踢：←↙↓↘→+B或D 

黄金之踵落：↓↙←+B或D 

*死亡龙卷风：↓↘→↓↘→+A或C 

*爆烈飓风猛虎踢：↓↘→↘↓↙←+A或C 

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/asiainfolf/archive/2010/10/05/5922701.aspx

低踢：→+B

滑步：↘+B

旋风拳：←↙↓↘→+A或C

爆烈拳：A或C连按

爆烈拳终结：爆烈拳中↓↘→+A或C

虎破脚：→↓↘+B或D

电光踢：←↙↓↘→+B或D

黄金之踵落：↓↙←+B或D

*死亡龙卷风：↓↘→↓↘→+A或C

*爆烈飓风猛虎踢：↓↘→↘↓↙←+A或C

5.4.6 Example

We're done with writing the code. Now, for clarification, let's run through an example designed to need lots of rebalancing along the way. Suppose that, starting with an empty AVL tree, we insert 6, 5, and 4, in that order. The first two insertions do not require rebalancing. After inserting 4, rebalancing is needed because the balance factor of node 6 would otherwise become -2, an invalid value. This is case 1, so we perform a right rotation on 6. So far, the AVL tree has evolved this way:

If we now insert 1, then 3, a double rotation (case 2.1) becomes necessary, in which we rotate left at 1, then rotate right at 4:

Inserting a final item, 2, requires a right rotation (case 1) on 5:

5.4.5 Symmetric Case

Finally, we need to write code for the case that we chose not to discuss earlier, where the insertion occurs in the right subtree of y. All we have to do is invert the signs of balance factors and switch avl_link[] indexes between 0 and 1. The results are this:

157. <Rebalance AVL tree after insertion in right subtree 157> =
struct avl_node *x = y->avl_link[1];
if (x->avl_balance == +1)
{ 
    <Rotate left at y in AVL tree 158> 
  }
else 
  { 
    <Rotate right at x then left at y in AVL tree 159> 
  }

This code is included in 151 and 162.

158. <Rotate left at y in AVL tree 158> =
w = x;
y->avl_link[1] = x->avl_link[0];
x->avl_link[0] = y;
x->avl_balance = y->avl_balance = 0;

This code is included in 157 and 532.

159. <Rotate right at x then left at y in AVL tree 159> =
assert (x->avl_balance == -1);
w = x->avl_link[0];
x->avl_link[0] = w->avl_link[1];
w->avl_link[1] = x;
y->avl_link[1] = w->avl_link[0];
w->avl_link[0] = y;
if (w->avl_balance == +1) 
  x->avl_balance = 0, y->avl_balance = -1;
else if (w->avl_balance == 0) 
  x->avl_balance = y->avl_balance = 0;
else /* w->avl_balance == -1 */ 
  x->avl_balance = +1, y->avl_balance = 0;
w->avl_balance = 0;

This code is included in 157, 174, 310, 428, and 533.

5.4.3 Step 3: Update Balance Factors

When we add a new node n to an AVL tree, the balance factor of n's parent must change, because the new node increases the height of one of the parent's subtrees. The balance factor of n's parent's parent may need to change, too, depending on the parent's balance factor, and in fact the change can propagate all the way up the tree to its root.

At each stage of updating balance factors, we are in a similar situation. First, we are examining a particular node p that is one of n's direct ancestors. The first time around, p is n's parent, the next time, if necessary, p is n's grandparent, and so on. Second, the height of one of p's subtrees has increased, and which one can be determined using da[].

In general, if the height of p's left subtree increases, p's balance factor decreases. On the other hand, if the right subtree's height increases, p's balance factor increases. If we account for the three possible starting balance factors and the two possible sides, there are six possibilities. The three of these corresponding to an increase in one subtree's height are symmetric with the others that go along with an increase in the other subtree's height. We treat these three cases below.

Case 1: p has balance factor 0

If p had balance factor 0, its new balance factor is - or +, depending on the side of the root to which the node was added. After that, the change in height propagates up the tree to p's parent (unless p is the tree's root) because the height of the subtree rooted at p's parent has also increased.

The example below shows a new node n inserted as the left child of a node with balance factor 0. On the far left is the original tree before insertion; in the middle left is the tree after insertion but before any balance factors are adjusted; in the middle right is the tree after the first adjustment, with p as n's parent; on the far right is the tree after the second adjustment, with p as n's grandparent. Only in the trees on the far left and far right are all of the balance factors correct.

Case 2: p's shorter subtree has increased in height

If the new node was added to p's shorter subtree, then the subtree has become more balanced and its balance factor becomes 0. If p started out with balance factor +, this means the new node is in p's left subtree. If p had a - balance factor, this means the new node is in the right subtree. Since tree p has the same height as it did before, the change does not propagate up the tree any farther, and we are done. Here's an example that shows pre-insertion and post-balance factor updating views:

Case 3: p's taller subtree has increased in height

If the new node was added on the taller side of a subtree with nonzero balance factor, the balance factor becomes +2 or -2. This is a problem, because balance factors in AVL trees must be between -1 and +1. We have to rebalance the tree in this case. We will cover rebalancing later. For now, take it on faith that rebalancing does not increase the height of subtree p as a whole, so there is no need to propagate changes any farther up the tree.

Here's an example of an insertion that leads to rebalancing. On the left is the tree before insertion; in the middle is the tree after insertion and updating balance factors; on the right is the tree after rebalancing to. The -2 balance factor is shown as two minus signs (--). The rebalanced tree is the same height as the original tree before insertion.

As another demonstration that the height of a rebalanced subtree does not change after insertion, here's a similar example that has one more layer of nodes. The trees below follow the same pattern as the ones above, but the rebalanced subtree has a parent. Even though the tree's root has the wrong balance factor in the middle diagram, it turns out to be correct after rebalancing.

Implementation

Looking at the rules above, we can see that only in case 1, where p's balance factor is 0, do changes to balance factors continue to propagate upward in the tree. So we can start from n's parent and move upward in the tree, handling case 1 each time, until we hit a nonzero balance factor, handle case 2 or case 3 at that node, and we're done (except for possible rebalancing afterward).

Wait a second—there is no efficient way to move upward in a binary search tree!¹ Fortunately, there is another approach we can use. Remember the extra code we put into <Step 1: Search AVL tree for insertion point 148>? This code kept track of the last node we'd passed through that had a nonzero balance factor as s. We can use s to move downward, instead of upward, through the nodes whose balance factors are to be updated.

Node s itself is the topmost node to be updated; when we arrive at node n, we know we're done. We also kept track of the directions we moved downward in da[]. Suppose that we've got a node p whose balance factor is to be updated and a direction d that we moved from it. We know that if we moved down to the left (d == 0) then the balance factor must be decreased, and that if we moved down to the right (d == 1) then the balance factor must be increased.

Now we have enough knowledge to write the code to update balance factors. The results are almost embarrassingly short:

150. <Step 3: Update balance factors after AVL insertion 150> =
for (p = y, k = 0; p != n; p = p->avl_link[da[k]], k++)
if (da[k] == 0)
p->avl_balance–;
else 
    p->avl_balance++;

This code is included in 146, 301, and 419.

Now p points to the new node as a consequence of the loop's exit condition. Variable p will not be modified again in this function, so it is used in the function's final return statement to take the address of the new node's avl_datamember (see <AVL item insertion function 146> above).

Exercises:

1. Can case 3 be applied to the parent of the newly inserted node?
[answer]
No. Suppose that n is the new node, that p is its parent, and that p has a - balance factor before n's insertion (a similar argument applies if p's balance factor is +). Then, for n's insertion to decrease p's balance factor to -2, n would have to be the left child of p. But if p had a - balance factor before the insertion, it already had a left child, so n cannot be the new left of p. This is a contradiction, so case 3 will never be applied to the parent of a newly inserted node.

2. For each of the AVL trees below, add a new node with a value smaller than any already in the tree and update the balance factors of the existing nodes. For each balance factor that changes, indicate the numbered case above that applies. Which of the trees require rebalancing after the insertion?

[answer]

In the leftmost tree, case 2 applies to the root's left child and the root's balance factor does not change. In the middle tree, case 1 applies to the root's left child and case 2 applies to the root. In the rightmost tree, case 1 applies to the root's left child and case 3 applies to the root. The tree on the right requires rebalancing, and the others do not.

3. Earlier versions of libavl used chars, not unsigned chars, to cache the results of comparisons, as the elements of da[] are used here. At some warning levels, this caused the GNU C compiler to emit the warning “array subscript has type `char'” when it encountered expressions like q->avl_link[da[k]]. Explain why this can be a useful warning message.
[answer]
Type char may be signed or unsigned, depending on the C compiler and/or how the C compiler is run. Also, a common use for subscripting an array with a character type is to translate an arbitrary character to another character or a set of properties. For example, this is a common way to implement the standard C functions from ctype.h. This means that subscripting such an array with a char value can have different behavior when char changes between signed and unsigned with different compilers (or with the same compiler invoked with different options).

4. If our AVL trees won't ever have a height greater than 32, then we can portably use the bits in a single unsigned long to compactly store what the entire da[] array does. Write a new version of step 3 to use this form, along with any necessary modifications to other steps and avl_probe()'s local variables.
[answer]

Here is one possibility:

650. <Step 3: Update balance factors after AVL insertion, with bitmasks 650> =
for (p = y; p != n; p = p->avl_link[cache & 1], cache >>= 1)
  if ((cache & 1) == 0)
    p->avl_balance–;
  else 
    p->avl_balance++;

Also, replace the declarations of da[] and k by these:

unsigned long cache = 0; /* Cached comparison results. */
int k = 0;              /* Number of cached comparison results. */

and replace the second paragraph of code within the loop in step 1 by this:

if (p->avl_balance != 0)
  z = q, y = p, cache = 0, k = 0;

dir = cmp > 0;
if (dir)
  cache |= 1ul << k;
k++;

It is interesting to note that the speed difference between this version and the standard version was found to be negligible, when compiled with full optimization under GCC (both 2.95.4 and 3.0.3) on x86.

刘峰六的答案：
这个问题主要涉及的是dir方向的回朔存储的向量组的问题，所以只要更改回朔路径向量da[]就可以了,step3和标准答案略有不同，step1我原来的答案有误，忘了考虑要保留置位后的值了，所以必须使用”|”
unsigned long da;
//step1
for(……..)
{
    ……
    if(p->avl_balance != 0)
       z=q,y=p,k=0;
    da |= (0x1<<k); // 用|来置位
}

//step3
for(p=y,k=0;p!=n;p->avl_link[ (da>>(k-1))&0x1 ]) ], k++)
     if(（da>>(k-1)）& 0x1 )
       ……

---

Footnotes

[1] We could make a list of the nodes as we move down the tree and reuse it on the way back up. We'll do that for deletion, but there's a simpler way for insertion, so keep reading.

---

5.4.4 Step 4: Rebalance

We've covered steps 1 through 3 so far. Step 4, rebalancing, is somewhat complicated, but it's the key to the entire insertion procedure. It is also similar to, but simpler than, other rebalancing procedures we'll see later. As a result, we're going to discuss it in detail. Follow along carefully and it should all make sense.

Before proceeding, let's briefly review the circumstances under which we need to rebalance. Looking back a few sections, we see that there is only one case where this is required: case 3, when the new node is added in the taller subtree of a node with nonzero balance factor.

Case 3 is the case where y has a -2 or +2 balance factor after insertion. For now, we'll just consider the -2 case, because we can write code for the +2 case later in a mechanical way by applying the principle of symmetry. In accordance with this idea, step 4 branches into three cases immediately, one for each rebalancing case and a third that just returns from the function if no rebalancing is necessary:

151. <Step 4: Rebalance after AVL insertion 151> =
if (y->avl_balance == -2)
{ 
    <Rebalance AVL tree after insertion in left subtree 152> 
  }
else if (y->avl_balance == +2)
{ 
    <Rebalance AVL tree after insertion in right subtree 157> 
  }
else 
  return &n->avl_data;

See also 153 and 154.

This code is included in 146.

We will call y's left child x. The new node is somewhere in the subtrees of x. There are now only two cases of interest, distinguished on whether x has a + or - balance factor. These cases are almost entirely separate:

152. <Rebalance AVL tree after insertion in left subtree 152> =
struct avl_node *x = y->avl_link[0];
if (x->avl_balance == -1)
{ 
    <Rotate right at y in AVL tree 155> 
  }
else 
  { 
    <Rotate left at x then right at y in AVL tree 156> 
  }

This code is included in 151 and 162.

In either case, w receives the root of the rebalanced subtree, which is used to update the parent's pointer to the subtree root (recall that z is the parent of y):

153. <Step 4: Rebalance after AVL insertion 151> +=
z->avl_link[y != z->avl_link[0]] = w;

Finally, we increment the generation number, because the tree's structure has changed. Then we're done and we return to the caller:

154. <Step 4: Rebalance after AVL insertion 151> +=
tree->avl_generation++;
return &n->avl_data;

Case 1: x has - balance factor

For a - balance factor, we just rotate right at y. Then the entire process, including insertion and rebalancing, looks like this:

This figure also introduces a new graphical convention. The change in subtree a between the first and second diagrams is indicated by an asterisk (*).¹ In this case, it indicates that the new node was inserted in subtree a.

The code here is similar to rotate_right() in the solution to Exercise 4.3-2:

155. <Rotate right at y in AVL tree 155> =
w = x;
y->avl_link[0] = x->avl_link[1];
x->avl_link[1] = y;
x->avl_balance = y->avl_balance = 0;

This code is included in 152 and 529.

Case 2: x has + balance factor

This case is just a little more intricate. First, let x's right child be w. Either w is the new node, or the new node is in one of w's subtrees. To restore balance, we rotate left at x, then rotate right at y (this is a kind of “double rotation”). The process, starting just after the insertion and showing the results of each rotation, looks like this:

At the beginning, the figure does not show the balance factor of w. This is because there are three possibilities:

Case 2.1: w has balance factor 0.

This means that w is the new node. a, b, c, and d have height 0. After the rotations, x and y have balance factor 0.

Case 2.2: w has balance factor -.

a, b, and d have height h > 0, and c has height h - 1.

Case 2.3: w has balance factor +.

a, c, and d have height h > 0, and b has height h - 1.

156. <Rotate left at x then right at y in AVL tree 156> =
assert (x->avl_balance == +1);
w = x->avl_link[1];
x->avl_link[1] = w->avl_link[0];
w->avl_link[0] = x;
y->avl_link[0] = w->avl_link[1];
w->avl_link[1] = y;
if (w->avl_balance == -1) 
  x->avl_balance = 0, y->avl_balance = +1;
else if (w->avl_balance == 0) 
  x->avl_balance = y->avl_balance = 0;
else /* w->avl_balance == +1 */ 
  x->avl_balance = -1, y->avl_balance = 0;
w->avl_balance = 0;

This code is included in 152, 177, 307, 427, and 530.

Exercises:

1. Why can't the new node be x rather than a node in x's subtrees?
[answer]
Because then y's right subtree would have height 1, so there's no way that y could have a +2 balance factor.

2. Why can't x have a 0 balance factor?
[answer]
The value of y is set during the search for item to point to the closest node above the insertion point that has a nonzero balance factor, so any node below y along this search path, including x, must have had a 0 balance factor originally. All such nodes are updated to have a nonzero balance factor later, during step 3. So x must have either a - or + balance factor at the time of rebalancing.

3. For each subcase of case 2, draw a figure like that given for generic case 2 that shows the specific balance factors at each step.
[answer]

3.1.

3.2.

3.3.

4. Explain the expression z->avl_link[y != z->avl_link[0]] = w in the second part of <Step 4: Rebalance after AVL insertion 151> above. Why would it be a bad idea to substitute the apparent equivalent z->avl_link[y == z->avl_link[1]] = w?
[answer]
w should replace y as the left or right child of z. y != z->avl_link[0] has the value 1 if y is the right child of z, or 0 if y is the left child. So the overall expression replaces y with w as a child of z.
The suggested substitution is a poor choice because if z == (struct avl_node *) &tree->root, z->avl_link[1] is undefined.【注意，这就是为什么不使用==的原因】

5. Suppose that we wish to make a copy of an AVL tree, preserving the original tree's shape, by inserting nodes from the original tree into a new tree, using avl_probe(). Will inserting the original tree's nodes in level order (see the answer to Exercise 4.7-4) have the desired effect?
[answer]
Yes.

3. The first item to be inserted have the value of the original tree's root. After that, at each step, we can insert either an item with the value of either child x of any node in the original tree corresponding to a node y already in the copy tree, as long as x's value is not already in the copy tree.

4. The function below traverses tree in “level order”. That is, it visits the root, then the root's children, then the children of the root's children, and so on, so that all the nodes at a particular level in the tree are visited in sequence.

See also: [Sedgewick 1998], Program 5.16.

621. <Level-order traversal 621> =
/* Calls visit for each of the nodes in tree in level order.
   Returns nonzero if successful, zero if out of memory. */
static int 
bst_traverse_level_order (struct bst_table *tree, bst_item_func *visit) 
{
  struct bst_node **queue;
  size_t head, tail;

  if (tree->bst_count == 0)
    return 1;

  queue = tree->bst_alloc->libavl_malloc (tree->bst_alloc, 
                                          sizeof *queue * tree->bst_count);
  if (queue == NULL)
    return 0;

  head = tail = 0;
  queue[head++] = tree->bst_root;
  while (head != tail) 
    {
      struct bst_node *cur = queue[tail++];
      visit (cur->bst_data, tree->bst_param);
      if (cur->bst_link[0] != NULL)
        queue[head++] = cur->bst_link[0];
      if (cur->bst_link[1] != NULL)
        queue[head++] = cur->bst_link[1];
    }
  tree->bst_alloc->libavl_free (tree->bst_alloc, queue);

  return 1;
}
刘峰六：level_order的遍历实现使用“队列控序”技术

---

Footnotes

[1] A “prime” (') is traditional, but primes are easy to overlook.

---

5.4.2 Step 2: Insert

Following the search loop, q is the last non-null node examined, so it is the parent of the node to be inserted. The code below creates and initializes a new node as a child of q on side dir, and stores a pointer to it into n. Compare this code for insertion to that within <BST item insertion function 32>.

149. <Step 2: Insert AVL node 149> =
n = q->avl_link[dir] = 
  tree->avl_alloc->libavl_malloc (tree->avl_alloc, sizeof *n);
if (n == NULL)
  return NULL;

tree->avl_count++;
n->avl_data = item;
n->avl_link[0] = n->avl_link[1] = NULL;
n->avl_balance = 0;
if (y == NULL)
  return &n->avl_data;

This code is included in 146.

Exercises:

1. How can y be NULL? Why is this special-cased?
[answer]

Variable y is only modified within <Step 1: Search AVL tree for insertion point 148>. If y is set during the loop, it is set to p, which is always a non-null pointer within the loop. So y can only be NULL if it is last set before the loop begins. If that is true, it will be NULL only if tree->avl_root == NULL. So, variable y can only be NULL if the AVL tree was empty before the insertion.

A NULL value for y is a special case because later code assumes that y points to a node.