StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You could use a threaded balanced binary search tree. However in search, instead of checking a number <code>x</code> against a single number in node <code>n</code>, you would be checking a page <code>px</code> against a page <code>pn</code>. Since your pages are none-overlapping, this is quite simple. Take an id in <code>px</code> of your choice (<code>x</code>) and check it against the minimum and maximum of <code>pn</code> (<code>pn_min</code>, <code>pn_max</code>). Then:</p> <pre><code>if pn_min <= x <= pn_max the page you are looking for if x < pn_min go left if x > pn_max go right </code></pre> <p>To be able to retrieve ids in a range, you'd first find the minimum of that range in the tree (<code>x</code>) (using a normal search). If it didn't exist, it means that you had searched down to a leaf. Call that <code>pn</code>:</p> <pre><code>if x < pn_min start from pn if x > pn_max start from pn->next </code></pre> <p>where <code>pn->next</code> is the next node in the threaded tree. Now you have a starting page. Simply go through the page and retrieve ids until you reach the maximum of the range. If the page ends, go to the <code>next</code> page in the threaded tree and continue as above.</p> <p>Since the tree is balanced, this should give you <code>O(logn)</code> in search/insert/delete operations and since it's threaded, it should give you <code>O(logn + k)</code> (where <code>k</code> is the number of ids in a given range) in interval queries.</p> <hr> <p>Note: your tree doesn't need to have threads in both directions. <a href="http://adtinfo.org/libavl.html/index.html" rel="nofollow">GNU's libavl</a> seems to have the tools you need, but if it's simpler, or if you have to write it yourself, you could consider a right-threaded tree only.</p> <hr> <p><strong>Edit</strong>: Querying for a range based on the <code>r</code>th to <code>s</code>th id.</p> <p>With a slight modification, you can achieve this also. The algorithm is the same as finding a range of actual ids, except finding the first element is different.</p> <p>Let's append a number to each node that says how many ids are inserted to the left of this node. Call this <code>pn_before</code>. Also, call <code>pn_size</code> as the number of ids in <code>pn</code>. Now searching for the <code>rth</code> id (which is the first in range of <code>[rth, sth]</code> ids) becomes as follows:</p> <pre><code>passed = 0 pn = root while pn not leaf if passed + pn_before < rth <= passed + pn_before + pn_size the node you are looking for if rth <= passed + pn_before go left if rth > passed + pn_before + pn_size passed += pn_before + pn_size go right </code></pre> <p>To explain what is <code>passed</code>, imagine the following tree</p> <pre><code> __________ p3 {5, 6} before: 4___________ / \ ______p2 {2, 3, 4} before: 1 _______p5 {9}: before 2_____ / / \ p1 {1} before: 0 p4 {7, 8}: before 0 p6 ... </code></pre> <p>Now let's say you are looking for the 7th element (which also has id 7 in this example). If you look at the root (<code>p3</code>), you will see that there are 4 ids before it, 2 ids inside it. Therefore, the 3rd if applies and you go right. Now in this new tree, you know that you have already passed 4+2 ids, so instead of looking for 7th element, you have to look for 1st element. The variable <code>passed</code> helps keep track of what ids are jumped over when you go right.</p> <p>Alternatively, you could have reduced <code>pn_before</code> and <code>pn_size</code> from <code>rth</code>, so <code>rth</code> actually becomes smaller every time. It's the same (but remember to back up <code>rth</code> because you'd need it later)</p> <p>Once you found the position of the <code>rth</code> element, you continue as the previous interval query algorithm.</p> <p>Only remaining problem now is updating <code>pn_before</code>. Well this is quite simple. Since each root of each subtree keeps track of only it's left sub-tree, then on insert/delete, you would need to go upwards to the root of the tree and add/remove <code>pn_before</code> of that node by the amount of ids just inserted/deleted. Remember to only change parents where you go up from the left child. If you go up to a parent and you are on the right child, the parent doesn't need to keep track of you. Note that in that case you shouldn't stop because the parent may be the left child of its own parent.</p> <p>Do it on paper and you'll get it ;)</p> <p>Another note: pay attention to <code>pn_before</code> when you rebalance the tree.</p> <p>The search is again <code>O(logn + k)</code> where <code>k</code> is the number of ids in the interval you are querying (<code>s - r</code>). The additional step backwards to the root in insert/delete doesn't change the order of those algorithms since the step backwards is also <code>O(logn)</code>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload