Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>You are correct in your understanding that an AVL tree is defined by the nearly-uniform height of its edge nodes, but your confusion appears to be about the difference between node position and edge weight.</p> <p>That is: In an AVL tree, the depth of the edge nodes will the same +/- (but not both!) one. This makes no claims as to the cost associated with an edge between the nodes. For an AVL tree with a root node and two children, the left path may be twice as expensive to traverse as the right path. This would make the tree weight-unbalanced, but still maintain the definition of an AVL tree.</p> <p>This page has more information: <a href="http://en.wikipedia.org/wiki/Weight-balanced_tree" rel="nofollow noreferrer">Weight-balanced tree - wikipedia</a></p> <p>From Wikipedia:</p> <blockquote> <p>A Binary Tree is called μ-balanced, with <img src="https://i.stack.imgur.com/Plw1G.png" alt="equation">, if for every node N, the inequality: <img src="https://i.stack.imgur.com/N1JvI.png" alt="mu-balance inequality"></p> <p>holds and μ is minimal with this property. |N| is the number of nodes under the tree with N as root (including the root) and Nl is the left sub-tree of N.</p> </blockquote> <p>Essentially, this means that the children in an AVL tree are not necessarily evenly distributed across the lowest level of the tree. Taking N as indicating the root node of the tree, one could construct a valid AVL tree that has more children to the left of the root than to the right of it. With a very deep tree, there could be many nodes at this bottom level.</p> <p>The definition of an AVL tree would require that they all be within one of the deepest point, but makes no guarantee as to what node they are a child of with respect to a node N.</p>
    singulars
    1. This table or related slice is empty.
    1. POweight-unbalanced AVL tree
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USFiarr
    1. USFiarr
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POweight-unbalanced AVL tree
      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. VTAcceptedByOriginator
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COBut it is written: _AVL trees are height-balanced, but in general not weight-balanced nor μ-balanced;[4] that is,_ **sibling nodes can have hugely differing numbers of descendants.** That does not refer to the cost/weight/expensiveness of the edges but to the number of descendants/child of the siblings. The bold part in the citation is confusing me.
      singulars
      1. PO
      1. UStaktak004
    2. COAh, I missed that part! I have edited my answer to address this. Let me know if it isn't clear.
      singulars
      1. PO
      1. USFiarr
    3. COThanks, it is very clear.
      singulars
      1. PO
      1. UStaktak004
 

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