Click here to Skip to main content
11,412,833 members (71,932 online)
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C GCC
I need help understanding Union of Intervals based on Advanced Data Structures Book by Peter Brass. Attached is the section of the book that Im trying to Understand starting from the middle of the page 163 where it says "A fully dynamic structure to maintain the measure of a union of intervals..."

Im trying to make the Measure of all Unions of Intervals Calculate Properly.

This is basically what I understood,
1) Start with any Balanced Search Tree. Therefore I used height balanced search tree.
example, for interval [1,9], I insert a 1 into the tree. Then I Insert a 9 into the tree.

2) during insertion of for interval [1,9]
a) i record the path of 1 into a stack, insert 1 into the tree, rebalance the tree, use the stack to trace back to the root while calculating the leftmin, rightmax and measure.

-b) record the path of 9 into a stack, insert 1 into the tree, rebalance the tree, use the stack to trace back to the root while calculating the leftmin, rightmax and measure.

What's messing me up is it's associated nodes. I can't visualize it correctly.
Anyway, I implemented this in C and its not calculating right. Am I missing something?
Posted 11-Nov-11 9:00am

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
0 OriginalGriff 404
1 Sascha Lefévre 200
2 Maciej Los 185
3 ProgramFOX 130
4 Sergey Alexandrovich Kryukov 110
0 Sergey Alexandrovich Kryukov 9,025
1 OriginalGriff 7,317
2 Maciej Los 3,570
3 Abhinav S 3,298
4 Peter Leow 3,084


Advertise | Privacy | Mobile
Web01 | 2.8.150427.1 | Last Updated 11 Nov 2011
Copyright © CodeProject, 1999-2015
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100