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:

    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


    User Avatar
    Science Advisor
    Gold Member
    2017 Award

    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 Threads - black Trees properties Date
C/++/# 3d space filling tree Apr 5, 2017
Minimum Spanning Tree in R Mar 3, 2017
Different Node Deletion/Insertion in a Binary Search Tree Oct 23, 2016
C/++/# Djikstra's algorithm with distance 1 between every node Sep 25, 2016
Decision Properties of Languages Jan 11, 2015