C++代写：CS251 AVLTree

发表于 | 分类于
STL库，作为C++中大量使用模板的库，对于初学者来说十分难以理解。

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实现，有简入难，一步一步学习。