Skip to content

Latest commit

 

History

History
43 lines (34 loc) · 1.53 KB

README.md

File metadata and controls

43 lines (34 loc) · 1.53 KB

Package binomial

GoDoc

Tree Structure

Each box below is a Tree struct. Each Tree's child pointer is its first child in a linked list of direct children. The subsequent child in the list is the current child's sibling. Each child has a pointer back to its parent.

The rank, k, of each node is the rank of the tree below that node if you consider that node a root.

This entire diagram represents a rank 2 or degree 2 binomial tree. The Node pointers on each Tree are omitted for simplicity.

      +---------+
+----->k: 2     |
|     +---------+
|     |parent   |
|     |sibling  |
|  +--+child    |
|  |  +---------+
|  |
|  |  +---------+        +---------+
|  +-->k: 0     | +------>k: 1     <--+
|     +---------+ |      +---------+  |
+-----+parent   | | +----+parent   |  |
|     |sibling  +-+ |    |sibling  |  |
|     |child    |   | +--+child    |  |
|     +---------+   | |  +---------+  |
|                   | |               |
+-------------------+ |               |
                      |  +---------+  |
                      +-->k: 0     |  |
                         +---------+  |
                         |parent   +--+
                         |sibling  |
                         |child    |
                         +---------+

Heap Structure

A Heap contains a standard library doubly linked list where the Value for each list Element is a pointer to a Tree.