摘要: 这两天复习RenMian给我留下谭浩强的C语言教程，温故而知新，夯实基础知识，把第十三章《文件》的书复习后把所有的编程习题做了一遍，贴出来激励自己一下，也希望有用的同学可以参考，时间和水平有限，不足之处，恳请读者批评指正 答案如下 inc/testfile.h: view plaincopy to clipboardprint?01./* inc/testfile.h */  02...  阅读全文

5.6 遍历
Traversal is largely unchanged from BSTs. However, we can be confident that the tree won't easily exceed the maximum stack height, because of the AVL balance condition, so we can omit checking for stack overflow.

178. <AVL traversal functions 178> =
<BST traverser refresher; bst => avl 62>
<BST traverser null initializer; bst => avl 64>
<AVL traverser least-item initializer 180>
<AVL traverser greatest-item initializer 181>
<AVL traverser search initializer 182>
<AVL traverser insertion initializer 179>
<BST traverser copy initializer; bst => avl 69>
<AVL traverser advance function 183>
<AVL traverser back up function 184>
<BST traverser current item function; bst => avl 74>
<BST traverser replacement function; bst => avl 75>

This code is included in 145 and 196.

We do need to make a new implementation of the insertion traverser initializer. Because insertion into an AVL tree is so complicated, we just write this as a wrapper to avl_probe(). There probably wouldn't be much of a speed improvement by inlining the code anyhow:

179. <AVL traverser insertion initializer 179> =

下面我们会实现其它余下的所有的函数，它们只是有很小部分的修改，所以就不在添加注释了

180. <AVL traverser least-item initializer 180> =

181. <AVL traverser greatest-item initializer 181> =

182. <AVL traverser search initializer 182> =

183. <AVL traverser advance function 183> =

184. <AVL traverser back up function 184> =

Exercises:

1. Explain the meaning of this ugly expression, used in avl_t_insert():

    (struct avl_node *) ((char *) p - offsetof (struct avl_node, avl_data))

A： At this point in the code, p points to the avl_data member of an struct avl_node. We want a pointer to the struct avl_node itself. To do this, we just subtract the offset of the avl_data member within the structure. A cast to char* is necessary before the subtraction, because offsetof returns a count of bytes, and a cast to struct avl_node * afterward, to make the result the right type.

5.5.6 镜像情形

下面的的代码是前几节所讲的代码的镜像情形代码实现，在这种情况里面，我们删除的节点位于某个节点的右子树上面

5.5.6 镜像情形
下面的的代码是前几节所讲的代码的镜像情形代码实现，在这种情况里面，我们删除的节点位于某个节点的右子树上面

5.5.5 Step 5: Finish Up

176. <Step 5: Finish up and return after AVL deletion 176> =
tree->avl_count–;
tree->avl_generation++;
return (void *) item;

This code is included in 164.

Step 4: Rebalance

Now we have to write code to rebalance when it becomes necessary. We'll use rotations to do this, as before. Again, we'll distinguish the cases on the basis of x's balance factor, where x is y's right child:

173. <Step 4: Rebalance after AVL deletion 173> =
struct avl_node *x = y->avl_link[1];
if (x->avl_balance == -1)
  { 
    <Left-side rebalancing case 1 in AVL deletion 174> 
  }
else 
  { 
    <Left-side rebalancing case 2 in AVL deletion 175> 
  }

This code is included in 172.

Case 1: x has - balance factor

If x has a - balance factor, we handle rebalancing in a manner analogous to case 2 for insertion. In fact, we reuse the code. We rotate right at x, then left at y. w is the left child of x. The two rotations look like this:

174. <Left-side rebalancing case 1 in AVL deletion 174> =
struct avl_node *w;
<Rotate right at x then left at y in AVL tree 159>
pa[k - 1]->avl_link[da[k - 1]] = w;

This code is included in 173.

Case 2: x has + or 0 balance factor

When x's balance factor is +, the needed treatment is analogous to Case 1 for insertion. We simply rotate left at y and update the pointer to the subtree, then update balance factors. The deletion and rebalancing then look like this:

When x's balance factor is 0, we perform the same rotation, but the height of the overall subtree does not change, so we're done and can exit the loop with break. Here's what the deletion and rebalancing look like for this subcase:

175. <Left-side rebalancing case 2 in AVL deletion 175> =
y->avl_link[1] = x->avl_link[0];
x->avl_link[0] = y;
pa[k - 1]->avl_link[da[k - 1]] = x;
if (x->avl_balance == 0) 
  {
    x->avl_balance = -1;
    y->avl_balance = +1;
    break;
  }
else 
  x->avl_balance = y->avl_balance = 0;

This code is included in 173.

Exercises:

1. In <Step 4: Rebalance after AVL deletion 173>, we refer to fields in x, the right child of y, without checking that y has a non-null right child. Why can we assume that node x is non-null? [answer]

A: Tree y started out with a + balance factor, meaning that its right subtree is taller than its left. So, even if y's left subtree had height 0, its right subtree has at least height 1, meaning that y must have at least one right child.

2. Describe the shape of a tree that might require rebalancing at every level above a particular node. Give an example. [answer]
A:

Rebalancing is required at each level if, at every level of the tree, the deletion causes a +2 or -2 balance factor at a node p while there is a +1 or -1 balance factor at p's child opposite the deletion.

For example, consider the AVL tree below:

Deletion of node 32 in this tree leads to a -2 balance factor on the left side of node 31, causing a right rotation at node 31. This shortens the right subtree of node 28, causing it to have a -2 balance factor, leading to a right rotation there. This shortens the right subtree of node 20, causing it to have a -2 balance factor, forcing a right rotation there, too. Here is the final tree:

Incidentally, our original tree was an example of a “Fibonacci tree”, a kind of binary tree whose form is defined recursively, as follows. A Fibonacci tree of order 0 is an empty tree and a Fibonacci tree of order 1 is a single node. A Fibonacci tree of order n >= 2 is a node whose left subtree is a Fibonacci tree of order n - 1 and whose right subtree is a Fibonacci tree of order n - 2. Our example is a Fibonacci tree of order 7. Any big-enough Fibonacci tree will exhibit this pathological behavior upon AVL deletion of its maximum node.

5.5.3 Step 3: Update Balance Factors

When we updated balance factors in insertion, we were lucky enough to know in advance which ones we'd need to update. Moreover, we never needed to rebalance at more than one level in the tree for any one insertion. These two factors conspired in our favor to let us do all the updating of balance factors at once from the top down.

Everything is not quite so simple in AVL deletion. We don't have any easy way to figure out during the search process which balance factors will need to be updated, and for that matter we may need to perform rebalancing at multiple levels. Our strategy must change.

This new approach is not fundamentally different from the previous one. We work from the bottom up instead of from the top down. We potentially look at each of the nodes along the direct path from the deleted node to the tree's root, starting at pa[k - 1], the parent of the deleted node. For each of these nodes, we adjust its balance factor and possibly perform rebalancing. After that, if we're lucky, this was enough to restore the tree's balancing rule, and we are finished with updating balance factors and rebalancing. Otherwise, we look at the next node, repeating the process.

Here is the loop itself with the details abstracted out:

171. <Steps 3–4: Update balance factors and rebalance after AVL deletion 171> =
assert (k > 0);
while (–-k > 0) 
  {
    struct avl_node *y = pa[k];

    if (da[k] == 0)
      { 
        <Update y's balance factor after left-side AVL deletion 172> 
      }
    else 
      { 
        <Update y's balance factor after right-side AVL deletion 177> 
      }
  }

This code is included in 164.

The reason this works is the loop invariants. That is, because each time we look at a node in order to update its balance factor, the situation is the same. In particular, if we're looking at a node pa[k], then we know that it's because the height of its subtree on side da[k] decreased, so that the balance factor of node pa[k] needs to be updated. The rebalancing operations we choose reflect this invariant: there are sometimes multiple valid ways to rebalance at a given node and propagate the results up the tree, but only one way to do this while maintaining the invariant. (This is especially true in red-black trees, for which we will develop code for two possible invariants under insertion and deletion.)

Updating the balance factor of a node after deletion from its left side and right side are symmetric, so we'll discuss only the left-side case here and construct the code for the right-side case later. Suppose we have a node y whose left subtree has decreased in height. In general, this increases its balance factor, because the balance factor of a node is the height of its right subtree minus the height of its left subtree. More specifically, there are three cases, treated individually below.

Case 1: y has - balance factor

If y started with a - balance factor, then its left subtree was taller than its right subtree. Its left subtree has decreased in height, so the two subtrees must now be the same height and we set y's balance factor to 0. This is between -1 and +1, so there is no need to rebalance at y. However, binary tree y has itself decreased in height, so that means that we must rebalance the AVL tree above y as well, so we continue to the next iteration of the loop.

The diagram below may help in visualization. On the left is shown the original configuration of a subtree, where subtree a has height h and subtree b has height h - 1. The height of a nonempty binary tree is one plus the larger of its subtrees' heights, so tree y has height h + 1. The diagram on the right shows the situation after a node has been deleted from a, reducing that subtree's height. The new height of tree y is (h - 1) + 1 == h.

Case 2: y has 0 balance factor

If y started with a 0 balance factor, and its left subtree decreased in height, then the result is that its right subtree is now taller than its left subtree, so the new balance factor is +. However, the overall height of binary tree y has not changed, so no balance factors above y need to be changed, and we are done, hence we break to exit the loop.

Here's the corresponding diagram, similar to the one for the previous case. The height of tree y on both sides of the diagram is h + 1, since y's taller subtree in both cases has height h.

Case 3: y has + balance factor

Otherwise, y started with a + balance factor, so the decrease in height of its left subtree, which was already shorter than its right subtree, causes a violation of the AVL constraint with a +2 balance factor. We need to rebalance. After rebalancing, we may or may not have to rebalance further up the tree.

Here's a diagram of what happens to forcing rebalancing:

Implementation

The implementation is straightforward:

172. <Update y's balance factor after left-side AVL deletion 172> =
y->avl_balance++;
if (y->avl_balance == +1)
  break;
else if (y->avl_balance == +2)
  { 
    <Step 4: Rebalance after AVL deletion 173> 
  }

This code is included in 171.

无论你是男人，还是女人，做人，想成功，下面就是你必须要做到的：

1，朋友请你吃饭，不要觉得理所当然，请礼尚往来，否则你的名声会越来越差。

2，给自己定目标，一年，两年，五年，也许你出生不如别人好，通过努力，往往可以改变70%的命运。破罐子破摔只能和懦弱做朋友。

3，这是个现实的社会，感情不能当饭吃，贫穷夫妻百事哀。不要相信电影里的故事情节，那只是个供许多陌生人喧嚣情感的场所。只有不理智和不现实的人才相信

4，好朋友里面，一定要培养出一个知己，不要以为你有多么八面玲珑，到处是朋友，最后真心对你的，只有一个，相信我。

5，不要相信算卦星座命理，那是哄小朋友的，命运掌握在自己手中。坐在家里等什么房子，车子，还不如睡一觉做个好梦。

6，不喜欢的人少接触，但别在背后说坏话，说是非之人，必定是是非之人，谨记，祸从口出。

7，少玩游戏，这不是韩国，你打不出房子车子还有资本。可以有爱好，但要把握尺度，少玩农场，牧场，斗地主等一些高度吸引人思想的晋级游戏，也许你的级别很高，但不代表你有多么成功，反而会影响和占据你成功的时间。

8，是人都有惰性，这是与生俱来的，但是我们后天可以改变这种惰性，因为有很多人正在改变。对于某种事物或是生意不要等别人做到了，我才想到。不要等别人已经赚到钱了，我才想去做。没有人相信的是市场和机遇，大家都相信的叫做膨胀。

9，知道自己要干什么，夜深人静，问问自己，将来的打算，并朝着那个方向去实现。而不是无所事事和做一些无谓的事。

10，出路出路，走出去了，总是会有路的。困难苦难，困在家里就是难。《社会调查》普遍认为。

 

11，作为女人，不要以老卖老，认为事业跟自己没关系，以为自己就是洗衣服，做饭，看孩子，那就是大错特错。

 

12，做人，要做到；万事孝为先，教童品之道，夫妻和谐美，幸福万年长。但是这些不是拿来用嘴说说就能办到的，解放初期年代要做到这些，需要付出很大的努力和辛苦，当今现实的社会需要你付出很大的金钱，聪明的人都知道这个道理。

13，空闲时间不要经常上网做无聊的事和玩一些没有意义的游戏，读点文学作品，学习一些经营流程，管理规范，国际时事，法律常识。这能保证你在任何聚会都有谈资。

14，宁可错杀一千次来自各方面的信息，也不放过任何一个有可能成功的机会。只有这样你才不会去买后悔药。

15，要做一件事，成功之前，没有必要告诉其他人。成功之后不用你说，其他人都会知道的。这就是信息时代所带来的效应

 

16，头发，指甲，胡子，打理好。社会是个排斥性的接受体，这个星球所需要的艺术家极其有限，请不要冒这个险，就算你留长头发比较好看，也要尽量给人干净的感觉。

17，不要以为你是个男人，就不需要保养。至少饮食方面不能太随便，多吃番茄，海产品，韭菜，香蕉，都是对男性健康有益处的食物。你要是看不到价值，我可以告诉你。至少你能把看病节约下来的钱给你的女人多买几个化妆品.

18，力求上进的人，不要总想着靠谁谁，人都是自私的，自己才是最靠得住的人。

19，面对失败，不要太计较，天将降大任于斯人也，必先苦其心志，劳其筋骨，饿起体肤……但要学会自责，找到原因，且改掉坏习惯。 二十岁没钱，那很正常；三十岁没钱，可能是没有好的家境，需要更大的努力；四十岁没钱，只能自己找原因。穷人变成富人是可能的，而且很可能。穷人能穷一辈子，也是必然的，存在就是理由，只是有所选择。

20，面对选择，只有成功。如果你也选择成功，我们必将走向成功的彼岸。

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

     摘要: Resume   ...  阅读全文

5.5.2 Step 2: Delete

At this point, we've identified p as the node to delete. The node on the top of the stack, da[k - 1], is p's parent node. There are the same three cases we saw in deletion from an ordinary BST (see Deleting from a BST), with the addition of code to copy balance factors and update the stack.

The code for selecting cases is the same as for BSTs:

166. <Step 2: Delete item from AVL tree 166> =
if (p->avl_link[1] == NULL)
{ <Case 1 in AVL deletion 168> }
else 
  {
struct avl_node *r = p->avl_link[1];
if (r->avl_link[0] == NULL)
{ 
        <Case 2 in AVL deletion 169> 
      }
else 
      { 
        <Case 3 in AVL deletion 170> 
      }
}

See also 167.

This code is included in 164.

Regardless of the case, we are in the same situation after the deletion: node p has been removed from the tree and the stack contains k nodes at which rebalancing may be necessary. Later code may change p to point elsewhere, so we free the node immediately. A pointer to the item data has already been saved in item (see avldelsaveitem):

167. <Step 2: Delete item from AVL tree 166> +=
tree->avl_alloc->libavl_free (tree->avl_alloc, p);

Case 1: p has no right child

If p has no right child, then we can replace it with its left child, the same as for BSTs (see bstdelcase1).

168. <Case 1 in AVL deletion 168> =
pa[k - 1]->avl_link[da[k - 1]] = p->avl_link[0];

This code is included in 166.

Case 2: p's right child has no left child

If p has a right child r, which in turn has no left child, then we replace p by r, attaching p's left child to r, as we would in an unbalanced BST (see bstdelcase2). In addition, r acquires p's balance factor, and r must be added to the stack of nodes above the deleted node.

169. <Case 2 in AVL deletion 169> =
r->avl_link[0] = p->avl_link[0];
r->avl_balance = p->avl_balance;
pa[k - 1]->avl_link[da[k - 1]] = r;
da[k] = 1;
pa[k++] = r;

This code is included in 166.

Case 3: p's right child has a left child

If p's right child has a left child, then this is the third and most complicated case. On the other hand, as a modification from the third case in an ordinary BST deletion (see bstdelcase3), it is rather simple. We're deleting the inorder successor of p, so we push the nodes above it onto the stack. The only trickery is that we do not know in advance the node that will replace p, so we reserve a spot on the stack for it (da[j]) and fill it in later:

170. <Case 3 in AVL deletion 170> =
struct avl_node *s;
int j = k++;
for (;;) 
  {
da[k] = 0;
pa[k++] = r;
s = r->avl_link[0];
if (s->avl_link[0] == NULL)
break;
r = s;
}
s->avl_link[0] = p->avl_link[0];
r->avl_link[0] = s->avl_link[1];
s->avl_link[1] = p->avl_link[1];
s->avl_balance = p->avl_balance;
pa[j - 1]->avl_link[da[j - 1]] = s;
da[j] = 1;
pa[j] = s;

This code is included in 166.

Exercises:

1. Write an alternate version of <Case 3 in AVL deletion 170> that moves data instead of pointers, as in Exercise 4.8-2.
[answer]

1. This approach cannot be used in libavl (see Exercise 4.8-3).

651. <Case 3 in AVL deletion, alternate version 651> =
struct avl_node *s;
da[k] = 1;
pa[k++] = p;
for (;;) 
  {
da[k] = 0;
pa[k++] = r;
s = r->avl_link[0];
if (s->avl_link[0] == NULL)
break;
r = s;
}
p->avl_data = s->avl_data;
r->avl_link[0] = s->avl_link[1];
p = s;

 

2. Why is it important that the item data was saved earlier? (Why couldn't we save it just before freeing the node?)
[answer]
2. We could, if we use the standard libavl code for deletion case 3. The alternate version in Exercise 1 modifies item data, which would cause the wrong value to be returned later.