StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The specific arrangement of numbers isn't canonical (i.e., other valid arrangements exist). The only requirement is that the left subtree of each node contains only smaller nodes, and the right subtree contains only larger nodes.</p> <p>The way you come about a particular arrangement depends on the algorithm(s) used to populate it and the order in which the values are inserted. This is partly explained in the article in the "Balancing the tree" section. As you insert, you need to keep the tree balanced. How often you rebalance, and how you rebalance is the subject of millions of pages of textbooks, research papers and lines of code.</p> <p>In short, the answer to your question is, "It depends."</p> <p>For the naïve implementation, which doesn't necessarily produce balanced trees, each insertion simply walks the tree, going left if the number is smaller than the currently visited node, or right if it's larger (ignoring equal values, which you'd need to either ensure don't happen or decide on a policy for handling them). When you reach a dead end (i.e., a null left- or right-pointer), plonk a new node there with the inserted value.</p> <blockquote> <p>Sidebar: It's worth noting that the naïve algorithm can, on rare occasions, be just what you need, thanks to its simplicity. You can avoid unbalanced trees simply by randomly shuffling the input data before inserting. In most cases, however, you're better off not even using a binary tree. Hash tables are almost always preferable.</p> </blockquote>

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