Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Red-black Trees properties

  1. Oct 16, 2015 #1
    I don't understand the requirements for a red-black tree.
    Using this photo:
    https://upload.wikimedia.org/wikipedia/commons/6/66/Red-black_tree_example.svg

    One of the 5 required properties is that all leaves are black.
    A leaf is a node without a child, so that would only be 11 and 15 two links down from the root. So why is 1 and 25 black? They clearly have a child, so they are not leaves. Similarly, why is 6, 22, and 27 not black. They don't have children so they should be black.
     
  2. jcsd
  3. Oct 16, 2015 #2
    That all leaves are black does not imply that all black nodes are leaves.

    6, 22, and 27 do have child nodes, which are leaves marked NIL. Whether a given red-black tree has explicit leaves does not affect their role in balancing the tree.
     
  4. Oct 16, 2015 #3
    So if a node is not a leaf, then the color can be chosen at random?
     
  5. Oct 16, 2015 #4

    Borg

    User Avatar
    Gold Member

    What are the other rules?
     
  6. Oct 18, 2015 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    That all leaf nodes are black says something quite different than all black nodes are leaves. You apparently misread that property as the latter.

    A leaf node in a binary search tree contains no data and has no children. The black nodes that contain 11 and 15, along with the red nodes that contain 6, 22, and 27 are not leaf nodes. Each of those nodes contains data (11, 15, 6, 22, and 27, respectively) and each has two children (all of which are leaf nodes).


    You need to look at the other properties. The root node is black, so it's color cannot be chosen at random. Both child nodes of a red node must be black, so the colors of those child nodes cannot be chosen at random. Finally, there's the balancing rule. Just because a tree obeys the basic properties of a binary search tree and first four properties of a red-black tree does not necessarily mean that it is a red-black tree.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Red-black Trees properties
  1. Binary Search Tree C++ (Replies: 1)

  2. Binary tree (Replies: 5)

Loading...