Skip to content

Files

Latest commit

ad36d6a · Aug 26, 2018

History

History

binomial

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Aug 26, 2018
Aug 26, 2018
Aug 26, 2018
Aug 26, 2018
Aug 26, 2018

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.