小编Sea*_*son的帖子

所以我最近发布了这个,但我仍然因为出了什么问题而感到茫然.具体来说,我似乎无法弄清楚是什么导致我的AVL树需要这么长时间来排序.我读了一个包含500,000个随机,未分类数字的文件,通过在for循环中使用向量来对树进行排序,一次为数字提供一个数字.现在,我也使用普通的BST进行了测试,因为有人提到必须一次创建一个节点,这可能就是为什么花了这么长时间,但是只用了5秒就完成了,因为只有12,164个节点被跳过了重复.我的AVL树需要花费3个小时才能对列表中的一半进行排序,因此必定会出现问题.任何人都可以弄明白它是什么？据我所知,重新平衡和插入逻辑是正确的,因为每当我运行一堆测试用例时,它们都很好.我似乎无法追查问题所在.这是我想要查看的所有人的完整代码.由于我为检测目的而包含的所有内容(如跟踪循环),Main现在有点混乱,但大部分都将在最终版本中消失.

编辑:

这个问题已得到解答.

#include <iostream>
#include<iomanip>
#include <time.h>
#include <vector>
#include <fstream>
using namespace std;

vector<int> numbers;

struct node
{
public:
    int data, height;
    node *leftChild, *rightChild;
};

node* root = NULL;

int findMin(node *p) // finds the smallest node in the tree
{
    while (p->leftChild != NULL)
        p = p->leftChild;
    return p->data;
}
int findMax(node *p) // finds the largest node in the tree
{
    while(p->rightChild != NULL)
        p = p->rightChild;
    return p->data;
}
int max(int a, int b) …