C++代写：CS251 AVL Tree

发表于   |   分类于

Introduction

AVL Tree也就是AVL树，是早的自平衡二叉查找树。其任意节点的两颗子树最大高度差仅为1，因此也被称为高度平衡树。
相对红黑树，AVL树目前的应用场景已经非常下了，大部分还是用于学习和研究。
AVL树最大的特点是，树的查找、插入和删除在平均和最坏情况下都是O(log n)，但增加和删除节点可能需要旋转这颗树，使其重新平衡。

Requirement

Implement a C++ AVL Tree class AVLTree in files AVLTree.h and AVLTree.cpp

  1. The constructor AVLTree () builds the AVLTree.
  2. The destructor ~AVLTree() deallocates all dynamically allocated memory.
  3. The void insert(int k) method inserts the key k into the AVLTree, and does not do anything if the key is already stored.
  4. The void remove(int k) method removes key k from the AVLTree and does not do anything if AVLTree does not contain key k.
  5. The items stored are positive integers which serve both as keys and as elements.
  6. The void printInorder() method prints the tree to the standard output using an inorder traversal; it prints a (key, height) pair for each node and ends with a newline.
  7. The void printPostorder() method prints the tree to the standard output using postorder traversal; it prints a (key, height) pair for each node and ends with a newline.

Analysis

本题需要用实现一个AVL树。AVL树本身代码不复杂，但是需要考虑到接口兼容STL库，这才是本题最大的难点。
STL库，作为C++中大量使用模板的库，对于初学者来说十分难以理解。我的建议是可以参考一些简易的STL实现，有简入难，一步一步学习。

Test

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
insert 44
insert 17
insert 78
insert 32
insert 50
insert 88
insert 48
insert 62
printInorder
insert 54
printInorder
remove 32
printInorder
printPostorder
exit

Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
inserting 44
inserting 17
inserting 78
inserting 32
inserting 50
inserting 88
inserting 48
inserting 62
Inorder printing
(17,2)
(32,1)
(44,4)
(48,1)
(50,2)
(62,1)
(78,3)
(88,1)
inserting 54
Inorder printing
(17,2)
(32,1)
(44,4)
(48,1)
(50,2)
(54,1)
(62,3)
(78,2)
(88,1)
removing 32
Inorder printing
(17,1)
(44,3)
(48,1)
(50,2)
(54,1)
(62,4)
(78,2)
(88,1)
Postorder printing
(17,1)
(48,1)
(54,1)
(50,2)
(44,3)
(88,1)
(78,2)
(62,4)
BYE!