Index Trees
Moderator: Board moderators
Index Trees
Can someone explain me the Idea of the Index Trees and if possible to give some link to read for this thing , or some problem which is solveable with this structure ? Thank you.
-
Alessandro
- New poster
- Posts: 27
- Joined: Mon Jun 14, 2004 10:33 pm
- Location: Latina, Italy
Excuse me if this reply is very late; last moths I had things to do and I didn't visited the forum.
An Index Tree is a binary tree with every node "controlling" a certain interval, and its children control the two halves of the interval. Example: a node controls interval [1,1000], its left son controls [1,500] and its right son controls [501, 1000]. Obviously, if a node controls an interval [x,x] it hasn't got any children.
With the Interval Tree (or index tree) we can obtain logN-complexity operations for inserting and querying. Well, what "insert" and "query" mean depends from the problem
Usually, it's not easy to understand how an interval tree must be used (obviously for me but I think it's common).
Simple example: you have a vector of N elements and want to know the lesser in a range [x,y], sometimes changing an element of the vector. You can do every operation in log N time.
An Index Tree is a binary tree with every node "controlling" a certain interval, and its children control the two halves of the interval. Example: a node controls interval [1,1000], its left son controls [1,500] and its right son controls [501, 1000]. Obviously, if a node controls an interval [x,x] it hasn't got any children.
With the Interval Tree (or index tree) we can obtain logN-complexity operations for inserting and querying. Well, what "insert" and "query" mean depends from the problem
Usually, it's not easy to understand how an interval tree must be used (obviously for me but I think it's common).Simple example: you have a vector of N elements and want to know the lesser in a range [x,y], sometimes changing an element of the vector. You can do every operation in log N time.
Alessandro Piva, Member of the Italian Team at the International Olimpiad in Informatics 2004
Email: alex.ander@infinito.it
Email: alex.ander@infinito.it