Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Does the tree have to be balanced? Does the algorithm need to be efficient?</p> <p>If not, then the simplest thing to do is make a tree in which all the left children are null, i.e., a tree that devolves to a linked list.</p> <p>To insert, recursively look go to the right child, and then update the size of the node on the way back out. Something like (pseudocode)</p> <pre><code>function insert(node, value, index, depth) if depth &lt; index create the rightchild if necessary insert( rightchild, value, index, depth + 1) if depth == size node.value = value node.size = rightchild.size + 1 </code></pre> <p>After you have this working, you can modify it to be more balanced. When increasing the length of the list, add nodes to the left or right child nodes depending on which currently has the least, and update the size on the way out of the recursion.</p> <p>To generalize to be more efficient, you need to work on the index in terms of its binary representation.</p> <p>For example, and empty list has one node, without children with value null and size 0.</p> <p>Say you want to insert "hello" at index 1034. Then you want to end up with a tree whose root has two children, with sizes 1024 and 10. The left child has no actual children, but the right node has a right child of its own of size 2. (The left of size 8 is implied.) That node in turn, has one right child of size 0, with the value "hello". (This list has a 1-based index, but a 0-based index is similar.)</p> <p>So you need to recursively break down the index into its binary parts, and add nodes as necessary. When searching the list, you need to take care when traversing a node with null children</p>
    singulars
    1. This table or related slice is empty.
    1. POList implemented using an inorder binary tree
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USUncleO
    1. USUncleO
    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. This table or related slice is empty.
    1. COIt doesn't need to be balanced though getting and inserting has to be a O(n) where n is the height of the tree. It's entirely possible to have a very unbalanced tree but the prof said it shouldn't be something we're to worry about at this point in the course. Thanks for the suggestion though - I'll think about this approach also
      singulars
      1. PO
      1. USthezhaba
    2. COThis answer sounds like it woudl be a bad one for homework. Homework assignments are usually about learning a concept and forcing a "tree" into a linked list would have guaranteed I wouldn't get an A with any of the profs i had.
      singulars
      1. PO
      1. USDolphin
    3. COTrue — we just studied linked lists mirroring which with binary trees would be somewhat redundant. I think uncleo's point is that it can be made into a more balanced version easily.
      singulars
      1. PO
      1. USthezhaba
 

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