Can anyone explain (or provide relevant link) of how a non complete
binary tree cannot correspond to an optimal prefix code ?
Do we have to give some sort of contradictory proof ?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to thi
@Navin Naidu: you are wrong in your preprocessing it will take log(n) for
insertion in red black so
creating a red black it will take O(n log n)
who it is O(n)?
On Thu, Apr 1, 2010 at 1:50 PM, Navin Naidu wrote:
> I think preprocessing time of O(n) will be required to construct the data
> st
Hello,
I am trying to find time complexity of Kruskal's algorithm in the following
implementations
1. Linked lis
2. Linked list with weighted union heuristic
3. Trees
4. Trees with only union by rank
5. Trees with union by rank and path compression.
All 5 implementations considering for connecte
for a particular query it will be O(log n+k).Where k is the no. of
elements to be reported.
On Wed, Mar 31, 2010 at 11:54 PM, BlackdiamonD wrote:
> Binary Indexed Trees or Segment Interval trees. building them also it will
> take O(n log(n))
> ..i feel for a particular query it will be difficult
my mistake, it will modify the structure.
On Thu, Apr 1, 2010 at 1:50 PM, Navin Naidu wrote:
> I think preprocessing time of O(n) will be required to construct the data
> structure.
>
> *Data Structure used:* R-B tree.
> *
> The additional data that will be stored in each node is : *
> a) the si
I think preprocessing time of O(n) will be required to construct the data
structure.
*Data Structure used:* R-B tree.
*
The additional data that will be stored in each node is : *
a) the size of subtree at each node
b) parent node.
*New Query:*
Find the kth element in the tree: Complexity will be