快速构建AVL树

Fast Build the AVL Tree

传统AVL树的构建是从空树开始依次将结点插入进来,每插入一个结点就要判断新得到的新树是否满足AVL树的性质,如满足则继续下一个结点的插入,如不满足则先要将之调整为AVL树再插入下一结点,直至结束。这种方法需要对生成的中间树频繁地进行调整,耗时较多。本文提出了一种新的简单的方法,主旨是采用递归思想实现:先将数据进行排序,然后将中点数据作为AVL树的根,小于中点数据的数据构成AVL树的左子树,大于中点数据的数据构成AVL树的右子树。

To assign a disorderly sequence to construct the AVL tree, the traditional method starts from the empty tree to insert the point in turn. When every time inserts the tree, the new tree will decide whether it satisfies the AVL tree＇ s nature. If it satisfies, the next point will insert, if it does not satisfy then it must adjusts to be the AVL tree again then inserts next point, until the end. This method needs to carry on the adjustment frequently to the production of the middle tree, it is very tedious. This article proposes one simple method on this question.