Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>To squabble about the performance of <em>binary-trees</em> is meaningless - they are not a data structure, but a family of data structures, all with different performance characteristics. While it is true that <em>unbalanced binary trees</em> perform much worse than <em>self-balancing binary trees</em> for searching, there are many binary trees <em>(such as binary tries)</em> for which <em>"balancing"</em> has no meaning.</p> <h2>Applications of binary trees</h2> <ul> <li><a href="http://en.wikipedia.org/wiki/Binary_search_tree" rel="noreferrer">Binary Search Tree</a> - Used in <em>many</em> search applications where data is constantly entering/leaving, such as the <code>map</code> and <code>set</code> objects in many languages' libraries.</li> <li><a href="http://en.wikipedia.org/wiki/Binary_space_partitioning" rel="noreferrer">Binary Space Partition</a> - Used in almost every 3D video game to determine what objects need to be rendered.</li> <li><a href="http://en.wikipedia.org/wiki/Radix_tree" rel="noreferrer">Binary Tries</a> - Used in almost every high-bandwidth router for storing router-tables.</li> <li><a href="http://en.wikipedia.org/wiki/Hash_tree" rel="noreferrer">Hash Trees</a> - used in p2p programs and specialized image-signatures in which a hash needs to be verified, but the whole file is not available.</li> <li><a href="http://en.wikipedia.org/wiki/Heap_(data_structure)" rel="noreferrer">Heaps</a> - Used in implementing efficient priority-queues, which in turn are used for scheduling processes in many operating systems, Quality-of-Service in routers, and A* <em>(path-finding algorithm used in AI applications, including robotics and video games)</em>. Also used in heap-sort.</li> <li><a href="http://en.wikipedia.org/wiki/Huffman_coding" rel="noreferrer">Huffman Coding Tree</a> (<a href="https://stackoverflow.com/questions/2130416/what-are-the-applications-of-binary-trees/2174096#2174096">Chip Uni</a>) - used in compression algorithms, such as those used by the .jpeg and .mp3 file-formats.</li> <li><a href="http://www.wisdom.weizmann.ac.il/~/oded/ggm.html" rel="noreferrer">GGM Trees</a> - Used in cryptographic applications to generate a tree of pseudo-random numbers.</li> <li><a href="http://en.wikipedia.org/wiki/Abstract_syntax_tree" rel="noreferrer">Syntax Tree</a> - Constructed by compilers and (implicitly) calculators to parse expressions.</li> <li><a href="http://en.wikipedia.org/wiki/Treap" rel="noreferrer">Treap</a> - Randomized data structure used in wireless networking and memory allocation.</li> <li><a href="http://en.wikipedia.org/wiki/T-tree" rel="noreferrer">T-tree</a> - Though most databases use some form of B-tree to store data on the drive, databases which keep all (most) their data in memory often use T-trees to do so.</li> </ul> <hr> <p>The reason that binary trees are used more often than n-ary trees for searching is that n-ary trees are more complex, but usually provide no real speed advantage.</p> <p>In a (balanced) binary tree with <code>m</code> nodes, moving from one level to the next requires one comparison, and there are <code>log_2(m)</code> levels, for a total of <code>log_2(m)</code> comparisons.</p> <p>In contrast, an n-ary tree will require <code>log_2(n)</code> comparisons <em>(using a binary search)</em> to move to the next level. Since there are <code>log_n(m)</code> total levels, the search will require <code>log_2(n)*log_n(m)</code> = <code>log_2(m)</code> comparisons total. So, though n-ary trees are more complex, they provide no advantage in terms of total comparisons necessary.</p> <p><em>(However, n-ary trees are still useful in niche-situations. The examples that come immediately to mind are <a href="http://en.wikipedia.org/wiki/Quadtree" rel="noreferrer">quad-trees</a> and other space-partitioning trees, where divisioning space using only two nodes per level would make the logic unnecessarily complex; and <a href="http://en.wikipedia.org/wiki/B-tree" rel="noreferrer">B-trees</a> used in many databases, where the limiting factor is not how many comparisons are done at each level but how many nodes can be loaded from the hard-drive at once)</em></p>
    singulars
    1. This table or related slice is empty.
    1. POWhat are the applications of binary trees?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USBlueRaja - Danny Pflughoeft
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POWhat are the applications of binary trees?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO> Treap - Randomized data structure used in wireless networking and memory allocation. How exactly they are used in memory allocation and wireless networking?
      singulars
      1. PO
      1. USfrp
 

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