题
我有一个大 AVL树我建立程序期间的某一时间从一个未排序的集合(它将被用于插入/移除后项)。
有没有更好的算法比用在每个项目上的简单的插入?这将是更有效的第一排序集合,然后尝试以不同的方式构建它?
我的应用程序的性能分析告诉我,这AVL建设是一个热点的位置。
解决方案
如果数据方便地装入内存,我的确会想到,首先进行快速排序,并建立从树会比做所有的常规插入得更快。
要从阵列构建树,操作以递归方式,将树分割为三个部分:一个中间元件,所述左部和右部;两个部件必须具有相同的大小(+ -1),然后形成树木这些零件。这保证了所得到的树是接近平衡(这将是完全平衡的,如果元件的数目是2 ^ N-1)。树的创建应该返回树的高度,这样就可以把平衡方便到每个节点。
修改强>:假设伊恩Piumarta的 tree.h中一>,我相信这个算法应该做的伎俩:
Node* tree_build(int key[], int value[], int L, int R) // L and R inclusive
{
int M;
Node *middle;
int lh, rh;
if(L == R)
return Node_new(key[L], value[L]);
if(L+1 == R) {
Node *left = Node_new(key[L], value[L]);
Node *right = Node_new(key[R], value[R]);
left->tree.avl_right = right;
left->tree.avl_height = 1;
return left;
}
// more than two nodes
M = L + (R-L)/2;
middle = Node_new(key[M], value[M]);
middle->tree.avl_left = tree_build(key, value, L, M-1);
middle->tree.avl_right = tree_build(key, value, M+1, R);
lh = middle->tree.avl_left->tree.avl_height;
rh = middle->tree.avl_right->tree.avl_height;
middle->tree.avl_height = 1 + (lh > rh ? lh:rh);
return middle;
}
不隶属于 StackOverflow