• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

04-树5 Root of AVL Tree

浙大mooc 站点默认 1年前 (2019-11-09) 180次浏览 已收录 0个评论

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.
8006cf557f9b2b0c01580ac9a31cd849.png

Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:
For each test case, print the root of the resulting AVL tree in one line.

Sample Input 1:
5
88 70 61 96 120
Sample Output 1:
70
Sample Input 2:
7
88 70 61 96 120 90 65
Sample Output 2:
88

题意没什么好说的,一看就明白了。这题最主要是让我们学会平衡二叉树在插入节点的时候,如果平衡因子大于1了,这这时我们如何去写出代码将树翻转保持原来的平衡因子。而难点也在于这里,但是mooc课件中就已经给出了平衡翻转的代码,虽然只给出了ll和lr的但是我们模仿也很容易写出rr和rl 的,但是我们不能仅仅模仿写完这题就完事了,更需要从深层理解的角度去明白是如何翻转的,能够自己写出这四个翻转函数


个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:04-树5 Root of AVL Tree
喜欢 (0)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到