Balanced Search Trees Node using arrays: is that possible?
- From: "GRios" <rios.gustavo@xxxxxxxxx>
- Date: 3 Feb 2006 12:32:50 -0800
i am faced with the task to build an indexing enginee (not to invent a
new one). Then, i turn to this newsgroup in order to dig if my approach
I would like to have an array of n positions, a[0...n-1]. Each position
p of such array will be seen as a node.
I would like to be able to insert/delete and retrieve dynymically in
O(log n), using the following schema for addressing node:
LEFT_NODE(x) = 2 * x + 1
RIGHT_NODE(x) = 2 * (x + 1)
UPPER_NODE(x) = (x - 1)/2
Is it possible to approach it using arrays or node and have worst-case
scenario O(log n)?
I was think about Binary BTree or some thing related to BTree.
Thanks in advance.