5. Non-Binary Trees¶

6. Non-Binary Trees ¹¶

General Trees are trees that are not binary trees, each node can have any number of children.
In-order traversal is not defined for general trees.

6.1 General Tree ADT¶

/** General tree node ADT */
interface GTNode<E> {
    public E value();
    public boolean isLeaf();
    public GTNode<E> parent();
    public GTNode<E> leftmostChild();
    public GTNode<E> rightSibling();
    public void setValue(E value);
    public void setParent(GTNode<E> par);
    public void insertFirst(GTNode<E> n);
    public void insertNext(GTNode<E> n);
    public void removeFirst();
    public void removeNext();
}

/** General tree ADT */
interface GenTree<E> {
    public void clear(); // Clear the tree
    public GTNode<E> root(); // Return the root
    // Make the tree have a new root, give first child and sib
    public void newRoot(E value, GTNode<E> first, GTNode<E> sib);
    public void newLeftChild(E value); // Add left child
}

PreOrder traversal is defined for general trees.

/** Preorder traversal for general trees */
static <E> void preorder(GTNode<E> rt) {
    PrintNode(rt);
    if (!rt.isLeaf()) {
        GTNode<E> temp = rt.leftmostChild();
        while (temp != null) { // recursively traverse each subtree, one by one, from left to right
            preorder(temp);
            temp = temp.rightSibling();
        }
    }
}

6.2 The Parent Pointer Implementation¶

Each node has a pointer to its parent.
Use Case: maintain a collection of disjoint sets, which requires two operations: determine if two objects are in the same set, and merge two sets.

/** General Tree class implementation for UNION/FIND */
class ParPtrTree {
    private Integer [] array; // Node array
    public ParPtrTree(int size) {
        array = new Integer[size]; // Create node array
        for (int i=0; i<size; i++)
        array[i] = null;
    }

    /** Determine if nodes are in different trees */
    public boolean differ(int a, int b) {
        Integer root1 = FIND(a); // Find root of node a
        Integer root2 = FIND(b); // Find root of node b
        return root1 != root2; // Compare roots
    }

    /** Merge two subtrees */
    public void UNION(int a, int b) {
        Integer root1 = FIND(a); // Find root of node a
        Integer root2 = FIND(b); // Find root of node b
        if (root1 != root2) array[root2] = root1; // Merge
    }

    /** @return The root of curr’s tree */
    public Integer FIND(Integer curr) {
        if (array[curr] == null) return curr; // At root
        while (array[curr] != null) curr = array[curr];
        return curr;
    }
}

6.3 General Tree Implementations¶

List Of Children implementation:
- Each node stores a liked-list to its children.
- Nodes are stored in array of Node objects, each of theses Node objects stores a value, a pointer (or index) to its parent and a pointer to a linked list of children.
Left-Child/Right-Sibling implementation:
- Nodes are stored in array of Node objects, each of theses Node objects stores a value, pointer to its parent, pointer to its leftmost child and pointer to its right sibling.
Dynamic Node implementation:
- To represent nodes into a tree that supports the operation we had on our binary tree, we can use a general tree with fixed number of children under each node (k-ary tree), but it has two problems:
  - What if some nodes need more than k children? they can not be represented in this tree.
  - What if some nodes need less than k children? we will waste memory.
- The second representation is to allow for dynamic number of children under each nod, this can be done in two ways:
  - Each node stores an array of pointers to its children, this works if the number of children remains the same, but if changes, extra work must be done to resize the array and maintain the tree structure.
  - Each node stores a linked list of pointers to its children, but it requires more space eventually.
Dynamic Left-Child/Right-Sibling implementation:
- Each node stores a binary tree points to its leftmost child and a pointer to its right sibling.

6.4 K-ary Trees¶

K-ary trees are trees whose internal nodes all have exactly K children.
The PR Quad-Tree is an example of a 4-ary tree.
The binary tree is an example of a 2-ary tree.
They are must useful if the tree either full or complete.

6.5 Sequential Tree Implementations¶

This approach stores no pointers which saves space, but accessing a node requires all nodes before it to be sequentially accessed first.
Use Cases:
1. save trees to disk (minimize space), then when the tree is accessed from the disk, it is loaded into memory and reconstructed into a different representation that guarantee O(log n) access time.
2. Serialization of trees, which is the process of converting a tree into a sequence of bytes that can be stored in a file or transmitted over a network, then the tree can be reconstructed from the sequence of bytes.
Sequential representation saves the tree as it appears in a preorder traversal, along with any data needed to reconstruct the tree.
For binary trees, the sequential representation very simple and uses little space, for general trees it is more complicated and uses more space (as general trees are more flexible than binary trees).

Union-Find Operation ³¶

Find the root of a tree that contains a given node, then Union two trees together into a single tree.
This is useful in organizing indexes in an array representation of a general tree, where subtree can be linked together to form a single tree.
Rules that controls the uni
- Weighted Union Rule:
  - joins the tree with the fewer nodes to the tree with the more nodes, making the smaller tree’s root point to the larger tree’s root.
  - It Does affect the height of the tree.
- Path Compression:
  - Makes the tree height shorter.
  - Merge the second tree or trees to the first one, making the root of the second tree point to the root of the first tree, then do a path compression on the second tree, by making all nodes in the second tree point to the root of the first tree.

Balancing a binary tree¶

Tree Re-balancing in Optimal Time and Space ²¶

Perfect Balance: for each node in th tree, the number of nodes in its left subtree and the number of nodes in its right subtree differ by at most 1.
In a perfectly balanced tree, the height of the tree is O(log n), and for each level d, there are exactly 2^d nodes.
Route Balanced Trees are binary trees that minimize the maximum depth of the nodes and the average depth of the nodes.
Every perfectly balanced tree is also route balanced, but not vice versa.
Steps:
1. Transform the tree into a vine (each parent only points to a right child and nodes are in sorted order).
2. Transform the vine into a route balanced tree.

References¶

Shaffer, C. (2011). A Practical Introduction to Data Structures and Algorithm Analysis. Blacksburg: Virginia. Tech. https://people.cs.vt.edu/shaffer/Book/JAVA3e20130328.pdf. Chapter 6. ↩
Bruno J. (1986). Tree Re-balancing in Optimal Time and Space. ACM. ↩
UoPeople. (2023). CS 3303 Data Structures. Unit 5: Non Binary Trees. Video Lecture. https://my.uopeople.edu/mod/kalvidres/view.php?id=359060 ↩

5. Non-Binary Trees¶

6. Non-Binary Trees 1¶

6.1 General Tree ADT¶

6.2 The Parent Pointer Implementation¶

6.3 General Tree Implementations¶

6.4 K-ary Trees¶

6.5 Sequential Tree Implementations¶

Union-Find Operation 3¶

Balancing a binary tree¶

Tree Re-balancing in Optimal Time and Space 2¶

References¶

6. Non-Binary Trees ¹¶

Union-Find Operation ³¶

Tree Re-balancing in Optimal Time and Space ²¶