StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You need to extend the data structure otherwise you cannot obtain a O(1) search of the minimum gap between the numbers composing the tree.</p> <p>You have the additional constrain to not increase the time complexity of insert/delete/search function and I assume that you don't want to increase space complexity too.</p> <p>Let consider a generic node <strong>r</strong>, with a left subtree <strong>r.L</strong> and a right subtree <strong>r.R</strong>; we will extend the information in node <strong>r</strong> additional number <strong>r.x</strong> defined as the minimum value between:</p> <ul> <li>(only if r.L is not empty) r value and the value of the rightmost leaf on r.L</li> <li>(only if r.L is deeper than 1) the x value of the r.L root node</li> <li>(only if r.R is not empty) r value and the value of the leftmost leaf on r.R</li> <li>(only if r.R is deeper than 1) the x value of the r.R root node</li> </ul> <p>(or undefined if none of the previous condition is valid, in the case of a leaf node)</p> <p>Additionally, in order to make fast insert/delete we need to add in each internal node the references to its leftmost and rightmost leaf nodes.</p> <p>You can see that with these additions:</p> <ul> <li>the space complexity increase by a constant factor only</li> <li>the insert/delete functions need to update the x values and the leftmost and rightmost leafs of the roots of every altered subtree, but is trivial to implement in a way that need not more than O(log(n))</li> <li>the x value of the tree root is the value that the function needs to return, therefore you can implement it in O(1)</li> </ul> <p>The minimum gap in the tree is the <strong>x</strong> value of the root node, more specifically, for each subtree the minimum gap in the subtree elements only is the subtree root <strong>x</strong> value.</p> <p>The proof of this statement can be made by recursion: Let consider a tree rooted by the node <strong>r</strong>, with a left subtree <strong>r.L</strong> and a right subtree <strong>r.R</strong>. The inductive hypothesis is that the roots of <strong>r.L</strong> and <strong>r.R x</strong> values are the values of the minimum gaps between the node values of the subtree. It's obvious that the minimum gap can be found considering only the pairs of nodes with values adjacent in the value sorted list; the pairs formed by values stored by the nodes of <strong>r.L</strong> have their minimum gap in the <strong>r.L</strong> root <strong>x</strong> value, the same is true considering the right subtree. Given that (any value of nodes in <strong>r.L</strong>) < value of <strong>L</strong> root node < (any value of nodes in <strong>r.R</strong>), the only pairs of adjacent values not considered are two: </p> <ol> <li>the pair composed by the root node value and the higher <strong>r.L</strong> node value</li> <li>the pair composed by the root node value and the lower <strong>r.R</strong> node value</li> </ol> <p>The <strong>r.L</strong> node with the higher value is its rightmost leaf by the AVL tree properties, and the <strong>r.R</strong> node with the lower value is its leftmost leaf. Assigning to <strong>r x</strong> value the minimum value between the four values (r.L root x value, r.R root x value, (r - r.L root) gap, (r - r.R root) gap) is the same to assign the smaller gap between consecutive node values in the whole tree, that is equivalent to the smaller gap between any possible pair of node values. The cases where one or two of the subtree is empty are trivial. The base cases of a tree made of only one or three nodes, it is trivial to see that the x value of the tree root is the minimum gap value.</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