Efficient algorithm for constructing AVL tree from a large collection
I have a large AVL Tree that I create several times during the program from an unsorted collection (it will be used to insert / remove items later).
Is there a better algorithm than using simple insertion for each element? Would it be more efficient to sort the collection first and then try to build it differently?
Profiling my app tells me this AVL building is the hotspot location.
source to share
If the data fits comfortably into memory, I would really expect to do quicksort first, and building a tree from that would be faster than doing all the normal inserts.
To build a tree from an array, work in a recursive manner, splitting the tree into three parts: the middle element, the left side, and the right side; both parts must be the same size (+ -1) and then form trees from these parts. This ensures that the resulting tree is nearly balanced (it will be perfectly balanced if the cardinality is 2 ^ n-1). The tree creation should return the height of the tree so that you can conveniently place the balance at each node.
Edit . Assuming Ian Piumarta tree.h , I believe this algorithm should do the trick:
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;
}
source to share