Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <h2>Edit</h2> <p>On second thought, I am more inclined to believe there's a typo in your example than this is not intended to be a BST. The location of the <code>10</code> doesn't make sense. Up until then it is a perfectly valid BST. If the 10 were inserted as the left leaf of the <code>12</code> node instead then the BST-ness would be preserved.</p> <p>If <code>leftNode.value &lt; value &lt;= rightNode.value</code> only applies to immediate children and not to all descendants then this is a useless data structure. I mean I guess it's usable, but since you'll end up traversing the entire tree on both inserts and lookups it seems rather pointless.</p> <hr> <p>I imagine the outline of your insertion algorithm will look like the following pseudo-Python. The gist of it is to try adding the node as a leaf where possible, or inserting it on either sub-tree. Left or right, it doesn't matter.</p> <p>Basically we're just looking down the entire tree for anywhere the new value can be added as a leaf node. As you say, the ordering criterion only applies to immediate children. You have to be picky about adding new leaf nodes. But you will try both left and right sub-trees indiscriminately.</p> <pre><code>class TreeNode: def insert(self, value): # Can we add it as the left leaf of this node? if self.left is None and value &lt; self.value: self.left = TreeNode(value) return True # Can we add it as the right leaf of this node? if self.right is None and value &gt;= self.value: self.right = TreeNode(value) return True # Can we add it somewhere down the left sub-tree? if self.left.insert(value): return True # Can we add it somewhere down the right sub-tree? if self.right.insert(value): return True # Didn't find anywhere to add the node. return False </code></pre> <p>I guess where it becomes tricky is if you have to attempt to balance the sub-trees and not just haphazardly insert new nodes at any arbitrary point in the tree. If that's an issue, then you could amend the above algorithm to insert at the shallowest point possible.</p> <p>Pretend there is a <code>insert_depth</code> method which returns the depth a node would be inserted at <em>if</em> it were inserted down a particular sub-tree, or returns &infin; if insertion is impossible. Again, this is just pseudo-code:</p> <pre><code>left_depth = self.left .insert_depth(value) right_depth = self.right.insert_depth(value) if left_depth &lt; right_depth: return self.left .insert(value) else: return self.right.insert(value) </code></pre> <p>In real code I'd write an "if you were going to insert a node, where would you insert it?" helper method. Run that method on both sub-trees, compare the insertion points, and pick one (i.e. the shallowest). The code would be a bit awkward but it would save you from traversing each sub-tree twice.</p>
    singulars
    1. This table or related slice is empty.
    1. POTraversing and inserting into a weird binary tree
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJohn Kugelman
    1. USJohn Kugelman
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThat was my original thought, but according to your algorithm, once you start down the left node, (if it doesn't find a place to insert beforehand) it will encounter a leaf, and will ALWAYS be set as a left or right child. Your right subtree insert will never be reached. From the example above, the insertion of 12, if following your algorithm, would have placed it as the right child of 5.
      singulars
      1. PO
      1. USInverseFalcon
 

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