Datastructures: trees

A hierarchical graph.

Documentation

wikipedia: trees

https://en.wikipedia.org/wiki/Category:Trees_(data_structures)

Self Balancing Binary Search Tree

A balanced binary search tree is one that is equally distributed. A self balancing binary search tree is composed of:

• nodes
• nodes contain keys
• nodes have child nodes

                    +-nodeA--------+                        --+
                    | +key-+key--+ |                          |
                    | |  5 | 10  | |                          | parent
                    | +----+-----+ |                          |
                    | |    |     | |                          |
                    +--------------+                        --+
                      |    |     |                          --+
        +-------------+    |     +-------------+              |
        |                  |                   |              |
        |                  |                   |              |
 +-nodeB--------+    +-nodeC--------+    +-nodeD--------+     | children
 | +key-+key--+ |    | +key-+key--+ |    | +key-+key--+ |     |
 | |  2 |  4  | |    | |  7 |  8  | |    | | 13 |  19 | |     |
 | +----+-----+ |    | +----+-----+ |    | +----+-----+ |     |
 +--------------+    +--------------+    +--------------+     |

--+

Nodes have an order of M.

• Nodes have a max of M children
• Non-leaf-node children have a max of M-1 keys

Keys are added to nodes based on ordering.

• less than 5 are in node nodeB
• between 5/10 in nodeC
• greater than 10 in nodeD

When a key is added, if it exceeds the key-allowance, it is added to the parent.
If it exceeds the parent key allowance, it is promoted splitting the parent into two nodes.
This recurses all the way to the root of the tree, if necessary.

TODO:

expand on this more. consider generating/embedding a gif