Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Unfortunately, we programmers are literal beasts.</p> <blockquote> <p>make it a "Balanced" tree.</p> </blockquote> <p>"Balanced" is context dependent. The introductory data structures classes typically refer to a tree being "balanced" when the difference between the node of greatest depth and the node of least depth is minimized. However, as mentioned by Sir Templatetypedef, a splay tree is considered a balancing tree. This is because it can balance trees rather well in cases that few nodes accessed together at one time frequently. This is because it takes less node traversals to get at the data in a splay tree than a conventional binary tree <em>in these cases</em>. On the other hand, its worst-case performance on an access-by-access basis can be as bad as a linked list.</p> <p>Speaking of linked lists...</p> <blockquote> <p>Because otherwise without the "Balancing" it's the same as a linked-list I read and defeats the purpose.</p> </blockquote> <p>It <em>can</em> be as bad, but for randomized inserts it isn't. If you insert already-sorted data, most binary search tree implementations will store data like an bloated and ordered linked list. However, that's only because you're building one side of the tree continually. (Imagine inserting 1, 2, 3, 4, 5, 6, 7, etc... into a binary tree. Try it on paper and see what happens.)</p> <p>If you have to balance in a theoretical worst-case-must-guaranteed sense, I recommend looking up red-black trees. (Google it, second link is pretty good.)</p> <p>If you have to balance it in a reasonable way for this particular scenario, I'd go with integer indices and a decent hash function -- that way the balancing will happen probabilistically without any extra code. That is to say, make your comparison function look like hash(strA) &lt; hash(strB) instead of what you've got now. (For a quick but effective hash for this case, look up FNV hashing. First hit on Google. Go down until you see useful code.) You can worry about the details of implementation efficiency if you want to. (For example, you don't have to perform both hashes every single time you compare since one of the strings never changes.)</p> <p>If you can get away with it, I strongly recommend the latter if you're in a crunch for time and want something fast. Otherwise, red-black trees are worthwhile since they're extremely useful in practice when you need to roll your own height-balanced binary trees.</p> <p>Finally, addressing your code above, see the comments in the code below:</p> <pre><code>int IntBinaryTree::numberNodes(TreeNode *root) { if(root = NULL) // You're using '=' where you want '==' -- common mistake. // Consider getting used to putting the value first -- that is, // "NULL == root". That way if you make that mistake again, the // compiler will error in many cases. return 0; /* if(TreeNode.left=null &amp;&amp; TreeNode.right==null) // Meant to use '==' again. { return 1; } return numberNodes(node.left) + numberNodes(node.right); */ int count = 1; // our actual node if (left != NULL) { // You likely meant 'root.left' on the next line, not 'TreeNode.left'. count += numberNodes(TreeNode.left); // That's probably the line that's giving you the error. } if (right != NULL) { count += numberNodes(root.right); } return count; } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POBalancing String based Binary Search Tree (For Spellchecking)
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USKaganar
    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. COthanks for the detailed explanation and the help!! Reading that hashing link on google now. Fixed everything you mentioned in the code (Re-posted the new code in my post) and it works now! :) Except...how do I call it in main? I can't figure it out. Also another question, should I use "if(nodePtr->left !=NULL)" or "if(left !=NULL)"??? It doesn't say either is wrong (Then again I haven't been able to call the function yet so).
      singulars
      1. PO
      1. USRiotson
    2. COSorry, there were some obvious errors I failed to observe. TreeNode is the name of the class, so you mean root->left instead of TreeNode.left. Likewise, root.right doesn't work since root is a pointer, so you mean root->right. Also, during your if() checks you mean root->left and root->right instead of left/right. (I suspect you've already fixed these due to the fact that you'll get compiler errors for most of them if you don't.)
      singulars
      1. PO
      1. USKaganar
    3. COYes I did! Thanks to your help! And thanks for the explanation. Only thing left I don't understand is, how do I call this function in main? tree.numberNodes(); ....says too few arguments, but I can't figure out what to pass to it.
      singulars
      1. PO
      1. USRiotson
 

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