How best to display a nested red/black tree?

0 votes
asked Mar 15, 2023 in Question / help by Beakerboy

I would like to create a UML diagram of a family of red/black trees.

Essentially the diagram will consist of a number of circles or ovals with some value inside. The color of the circle is either red or black. Each node May have arrows that either points down into the left, down into the right, or straight down to point to the next node. The orientation must not be arbitrary but must be able to be specified by the user.

Here’s an example that I made some time ago (forgot how and I can’t figure out how to see the code behind this diagram)

The issue with this (besides not having the code that generated it) is I was forced to add the “nil” node to ensure the other nodes at that level pointed the correct direction. I would want to be able to specify the direction for each edge of the graph.

Any help is appreciated

commented Mar 16, 2023 by The-Lu (64,340 points)

Here is your code:

digraph G {
    PROJECT [fillcolor="red" style="filled" fontcolor="white"];
    Module1 [fillcolor="red" style="filled" fontcolor="white"];
    Sheet1 [fillcolor="red" style="filled" fontcolor="white"]
    ThisWorkbook [fillcolor="red" style="filled" fontcolor="white"]
    "Root Entry" -> PROJECT
    VBA -> Module1
    Module1 -> Sheet1
    Module1 -> ThisWorkbook
    Sheet1 -> dir
    Sheet1 -> nil
    ThisWorkbook -> nil

    ThisWorkbook -> _VBA_PROJECT



  • What are your request (except to suppress the nil node) ?
    only right down or left down arrows?
    never straight down line (as between 'VBA' and 'Module1')?


commented Mar 17, 2023 by Beakerboy
edited Mar 17, 2023

Thanks! I think the code part is related to being on a mobile device. If I copy and paste the compressed code on desktop the website allows me to edit it.

The nil node is an issue, but also, when rendering the uml, the image will rearrange the nodes at times, flipping left and right. I want to be able to specify orientation. Each node should be able to point to the next node as either left/right, or straight down as a child.

in the full theory of red/black trees, all nodes have terminating nil nodes, so if there were a way to attach small black nil nodes at the end, that would be even better.

Wikipedia has some good diagrams which would be perfect to emulate. (–black_tree). I’m working on a red/black tree library for python and want to be able to export the structure in a visual way.

The child relationship (up/down arrow) is not part of red/black trees, so not as big of a deal if that makes it harder. I’m trying to visualize a nested series of red/black trees, where some nodes can contain other isolated trees.

commented Mar 17, 2023 by Beakerboy

Here's a larger example using the wbs template, which might be easier to work with?

*[#white] __SRP_10
**[#white] __SRP_c
***[#white] __SRP_4
****[#white] __SRP_0
*****[#red] Sheet1
*****[#red] __SRP_1
******[#white] dir
****[#white] __SRP_6
*****[#red] __SRP_5
*****[#red] __SRP_7
***[#white] __SRP_e
****[#white] __SRP_d
****[#white] __SRP_f
**[#white] DrupalFile
***[#white] __SRP_14
****[#white] __SRP_12
*****[#red] __SRP_11
*****[#red] __SRP_13
****[#white] __SRP_15
*****[#red] DrupalUser
***[#white] ThisWorkbook
****[#white] DrupalEntity
****[#red] DrupalDatabase
*****[#white] DrupalFactory
******[#red] _VBA_PROJECT
******[#red] iDrupalEntity
*****[#white] DrupalHelper

commented Mar 18, 2023 by Beakerboy
A mind map with rotated text would probably work well as long as the order of each node is guaranteed by its position in the source file. I tried a latex trick suggested on the forum but it did not work on the demo server.
commented Mar 19, 2023 by Beakerboy
Here’s the best I’ve got. I need to figure out how to get the text color to be white when decorated with #black.

*[#red] <latex>\rotatebox{90}{Root Entry}</latex>
**[#black] <latex>\rotatebox{90}{}</latex>
**[#white] <latex>\rotatebox{90}{PROJECT}</latex>
***[#red] <latex>\rotatebox{90}{PROJECTwm}</latex>
****[#black] <latex>\rotatebox{90}{}</latex>
****[#black] <latex>\rotatebox{90}{}</latex>
***[#red] <latex>\rotatebox{90}{VBA}</latex>
****[#black] <latex>\rotatebox{90}{}</latex>
****[#white] <latex>\rotatebox{90}{Module1}</latex>
*****[#white] <latex>\rotatebox{90}{ThisWorkbook}</latex>
******[#red] <latex>\rotatebox{90}{\_VBA\_PROJECT}</latex>
*******[#black] <latex>\rotatebox{90}{}</latex>
*******[#black] <latex>\rotatebox{90}{}</latex>
******[#black] <latex>\rotatebox{90}{}</latex>
*****[#white] <latex>\rotatebox{90}{Sheet1}</latex>
******[#black] <latex>\rotatebox{90}{}</latex>
******[#red] <latex>\rotatebox{90}{dir}</latex>
*******[#black] <latex>\rotatebox{90}{}</latex>
*******[#black] <latex>\rotatebox{90}{}</latex>
****[#black] <latex>\rotatebox{90}{}</latex>
**[#black] <latex>\rotatebox{90}{}</latex>
commented Apr 28, 2023 by The-Lu (64,340 points)

Hello B. and all,

1/ To color the text

You can use: <color:white>

2/ To change the orientation

You can also use `top to bottom direction` with mindmap.

3/ Here is the combined result

top to bottom direction
*[#red] Root Entry
**[#black] <color:white> //Text on White//
**[#white] PROJECT
***[#red] PROJECTwm
****[#black] -
****[#black] -
***[#red] VBA
****[#black] -
****[#white] Module1
*****[#white] ThisWorkbook
******[#red] VBA_PROJECT
*******[#black] -
*******[#black] -
******[#black] -
*****[#white] Sheet1
******[#black] -
******[#red] dir
*******[#black] -
*******[#black] -
****[#black] -
**[#black] -

[Thanks to @johny-tee]


Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:

[Antispam2 Feature: please please wait 1 or 2 minutes (this message will disappear) before pressing the button otherwise it will fail](--------)
To avoid this verification in future, please log in or register.