Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>(I've completely rewritten this answer because, as the commenters noted, it was initially incorrect.)</p> <p>I think it might help to think about this problem by using the <a href="https://www.cs.purdue.edu/homes/ayg/CS251/slides/chap13b.pdf" rel="nofollow">isometry between red-black trees and 2-3-4 trees</a>. Specifically, a red-black tree with black height h corresponds to a 2-3-4 tree with height h, where each red node corresponds to a key in a multi-key node.</p> <p>This connection makes it easier for us to make a few neat observations. First, any 2-3-4 tree node in the bottom layer corresponds to a black node with either no red children, one red child, or two red children. These are the only nodes that can be leaf nodes in the red-black tree. If we wanted to maximize the number of total nodes in the tree, we'd want to make the 2-3-4 tree have nothing but 4-nodes, which (under the isometry) maps to a red/black tree where every black node has two red children. An interesting effect of this is that it makes the tree layer colors alternate between black and red, with the top layer (containing the root) being black. </p> <p>Essentially, this boils down to counting the number of internal nodes in a complete binary tree of height 2h - 1 (2h layers alternating between black and red). This is equal to the number of nodes in a complete binary tree of height 2h - 2 (since if you pull off all the leaves, you're left with a complete tree of height one less than what you started with). This works out to 2<sup>2h - 1</sup> - 1, which differs from the number that you were given (which I'm now convinced is incorrect) but matches the number that you're getting.</p>
    singulars
    1. This table or related slice is empty.
    1. POLargest and smallest number of internal nodes in red-black tree?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. UStemplatetypedef
    1. UStemplatetypedef
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POLargest and smallest number of internal nodes in red-black 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. 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+1. I took it for granted that the tree he posted had a maximum number of internal nodes.
      singulars
      1. PO
      1. USIVlad
    2. COI think I could not express it well, in the second image black height is 1 so if we follow the formula we have 2^2-1 which 3 so it means there is 3 internal nodes but you can see that there is 7
      singulars
      1. PO
      1. USHamed Minaee
    3. CO@user2860721- I think you have the definition of "black height" wrong. The black height of a red-black tree is the number of black nodes on any path from the root to the leaves, not the height of the highest black node. (If you know about the connection to 2-3-4 trees, the black height of the red-black tree is the height of the 2-3-4 tree that corresponds to the red-black tree). Does that make sense?
      singulars
      1. PO
      1. UStemplatetypedef
 

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