我正在研究 AVL 树排序算法,我想我终于弄明白了,感谢大家的帮助,直到我意识到它的运行时间比插入排序的运行时间长得多,这不应该是正确的。我正在使用随机生成的数字的未排序数组(或更确切地说, vector )。我将在下面提供一些统计数据和代码。
AVL
for (std::vector<int>::const_iterator i = numbers.begin(); i != numbers.begin()+30000; ++i)
{
root = insert(root, numbers[x]);
cout << "Height: " << height(root);
x++;
track++;
if( (track % 10000) == 0)
{
cout << track << " iterations" << endl;
time_t now = time(0);
cout << now - begin << " seconds" << endl;
}
}
N = 30,000
高度=17
执行的迭代次数 = ~1,730,000
排序的运行时间 = 38 秒
插入排序
for (int i = 0; i < 30000; i++)
{
first++;
cout << first << " first level iterations" << endl;
time_t now = time(0);
cout << now - begin << " seconds" << endl;
int tmp = dataSet[i];
int j;
for (j = i; i > 0 && tmp < dataSet[j - 1]; j--)
{
dataSet[j] = dataSet[j - 1];
}
dataSet[j] = tmp;
}
}
N = 30,000
迭代次数 = 30,000
排序的运行时间 = 4 秒
这不可能是对的,所以我希望大家能帮忙弄清楚这是怎么回事?据我所知,我的所有代码都已正确实现,但我仍将在下面包含相关部分以防遗漏某些内容。
源代码
node* newNode(int element) // helper function to return a new node with empty subtrees
{
node* newPtr = new node;
newPtr->data = element;
newPtr->leftChild = NULL;
newPtr->rightChild = NULL;
newPtr->height = 1;
return newPtr;
}
node* rightRotate(node* p) // function to right rotate a tree rooted at p
{
node* child = p->leftChild;
node* grandChild = child->rightChild;
// perform the rotation
child->rightChild = p;
p->leftChild = grandChild;
// update the height for the nodes
p->height = max(height(p->leftChild), height(p->rightChild)) + 1;
child->height = max(height(child->leftChild), height(child->rightChild)) + 1;
// return new root
return child;
}
node* leftRotate(node* p) // function to left rotate a tree rooted at p
{
node* child = p->rightChild;
node* grandChild = child->leftChild;
// perform the rotation
child->leftChild = p;
p->rightChild = grandChild;
// update heights
p->height = max(height(p->leftChild), height(p->rightChild)) + 1;
// return new root
return child;
}
int getBalance(node *p)
{
if(p == NULL)
return 0;
else
return height(p->leftChild) - height(p->rightChild);
}
// recursive version of BST insert to insert the element in a sub tree rooted with root
// which returns new root of subtree
node* insert(node*& n, int element)
{
// perform the normal BST insertion
if(n == NULL) // if the tree is empty
return(newNode(element));
if(element< n->data)
{
n->leftChild = insert(n->leftChild, element);
}
else
{
n->rightChild = insert(n->rightChild, element);
}
// update the height for this node
n->height = 1 + max(height(n->leftChild), height(n->rightChild));
// get the balance factor to see if the tree is unbalanced
int balance = getBalance(n);
// the tree is unbalanced, there are 4 different types of rotation to make
// Single Right Rotation (Left Left Case)
if(balance > 1 && element < n->leftChild->data)
{
return rightRotate(n);
}
// Single Left Rotation (Right Right Case)
if(balance < -1 && element > n->rightChild->data)
{
return leftRotate(n);
}
// Left Right Rotation
if(balance > 1 && element > n->leftChild->data)
{
n->leftChild = leftRotate(n->leftChild);
return rightRotate(n);
}
// Right Left Rotation
if(balance < -1 && element < n->rightChild->data)
{
n->rightChild = rightRotate(n->rightChild);
return leftRotate(n);
}
// cout << "Height: " << n->height << endl;
// return the unmodified root pointer in the case that the tree does not become unbalanced
return n;
}
最佳答案
“调试”此类问题的最佳方法是 use a performance profiler tool ,但是在这种情况下,我想我可以给你一个很好的假设:
您的 AVL 树需要很多内存分配,and these are expensive
总之,您的比较不“公平”。
如何“修复”这个?:
- 尝试使用内存管理库,例如 Boost.Pool .
例如,如果您事先知道您的树将有多少个节点,您可以在算法开始时立即分配所有需要的节点,并使用它们创建一个节点池(如果您使用 Boost this应该比每次都调用标准的 new
运算符要快得多)。
每次您需要一个新节点时,您都从池中取出它。然后,您可以从不需要额外内存分配的点开始“比较”算法。
关于c++ - 为什么我的 AVL 树排序算法比插入排序算法花费的时间更长?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43547996/