Databases
StackOverflow2013
Postsdbo
POKeeping a binary tree balanced when elements are insert in order
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POKeeping a binary tree balanced when elements are insert in order
    primarykey
    data
    text
    <p>I was wondering if there is a suitable algorithm for maintaining the balance of a binary tree, when it is known that elements are <em>always</em> inserted in order.</p> <p>One option for this would be to use the standard method of creating a balanced tree from a sorted array or linked list, as discussed in <a href="https://stackoverflow.com/questions/4235013/create-balanced-binary-search-tree-from-sorted-linked-list">this</a> question, and also <a href="https://stackoverflow.com/questions/2893318/building-a-balanced-binary-search-tree">this</a> other question. However, I would like a method where a few elements can be inserted into the tree, lookups then performed on it, and other elements then added later, without having to decompose the tree to a list and re-make the whole thing.</p> <p>Another option would be to use one of the many self-balancing tree implementations, AVL, AA, Red-Black, etc. etc. However, all of these impose some sort of overhead in the process of insertion, and I was wondering if there may be a way to avoid this given the constraint that elements are <em>always</em> inserted in increasing order.</p> <p>So, for clarity, I would like know if there is a method by which I can maintain a balanced binary tree, such that I can insert an arbitrary new element into it at any point and keep the balance of the tree, providing that the new element is greater in the ordering of the tree than <em>all</em> elements already present in the tree.</p> <p>As an example, suppose I had the following tree:</p> <pre><code> 4 / \ / \ 2 6 / \ / \ 1 3 5 7 </code></pre> <p>Is there a simple way to maintain the balance when inserting a new element, if I know that the element will be larger than 7?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. This table or related slice is empty.
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POKeeping a binary tree balanced when elements are insert in order
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POKeeping a binary tree balanced when elements are insert in order
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POKeeping a binary tree balanced when elements are insert in order
      1. This table or related slice is empty.
      1. VTUpMod
    1. COIs it homework? theoretical question? If it is for real usage, I would have used a [skip list](http://en.wikipedia.org/wiki/Skip_list) instead of a BST with these conditions, and addition is always the last element. If that helps, though it is not a tree, let me know and I'll write it as an answer.
      singulars
      1. POKeeping a binary tree balanced when elements are insert in order
      1. USamit
    2. CO@amit, that was my first guess as well.
      singulars
      1. POKeeping a binary tree balanced when elements are insert in order
      1. USphimuemue
    3. CO@amit, it isn't a homework question, mainly out of curiosity / theoretical. As such although you are right that other data structures such as skip lists (or possibly even finger trees) may be well suited, I was more interested in a way of doing this to a BST.
      singulars
      1. POKeeping a binary tree balanced when elements are insert in order
      1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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