C++代写：CS251AVLTree

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

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

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!  

—|—