Data Structures: Tree Fundamentals and Binary Trees

Introduction to Trees

• General Definition: A tree is a non-linear data structure in which items are arranged in a sorted sequence. It is used to represent hierarchical relationships existing amongst several data items.
• Graph Theoretic Definition: A tree is a finite set of one or more data items (nodes) such that:     * There is a special data item called the root of the tree.     * The remaining data items are partitioned into a number of mutually exclusive (disjoint) subsets, each of which is itself a tree, known as subtrees.
• Growth Direction: Natural trees grow upwards from the ground into the air; however, tree data structures grow downwards from top to bottom.

Tree Terminology

• Root: A specially designed data item in a tree and the first in the hierarchical arrangement. In an example tree, node $A$ is the root.
• Node: The basic structure in a tree representing each data item. It specifies the data information and links (branches) to other data items.
• Degree of a Node: The number of subtrees of a node in a given tree.     * Example: In a specific tree, node $A$ has a degree of $3$, node $C$ has a degree of $1$, node $B$ has a degree of $2$, node $H$ has a degree of $0$, and node $I$ has a degree of $3$.
• Degree of a Tree: The maximum degree among all nodes in the tree. If node $A$ and node $I$ both have a maximum degree of $3$, the degree of the tree is $3$.
• Terminal Node (Leaf): A node with a degree of zero. In an example tree, terminal nodes include $E$, $J$, $G$, $H$, $K$, $L$, and $M$.
• Non-Terminal Node: Any node (except the root) whose degree is not zero. These are intermediate nodes encountered when traversing from the root to the terminal nodes.
• Siblings: Children nodes belonging to the same parent node, also referred to as brothers.     * Examples: $E$ and $F$ are siblings of parent node $B$; $K$, $L$, and $M$ are siblings of parent node $I$.
• Level: A hierarchy where the root node is at level $0$. Immediate children are at level $1$, and their children are at level $2$. In general, if a node is at level $n$, its children are at level $n+1$.
• Edge: The connecting line drawn from one node to another.
• Path: A sequence of consecutive edges from a source node to a destination node.     * Example: For a path between node $A$ and node $J$, the node pairs are $(A, B)$, $(B, F)$, and $(F, J)$.
• Depth (Height): The maximum level of any node in a given tree. It represents the number of levels one can descend from the root to the leaves.
• Forest: A set of disjoint trees. Removing the root node from a tree results in a forest of its subtrees.

Binary Trees

• Definition: A binary tree consists of a finite set of elements partitioned into three distinct sub-sets: the root, the left sub-tree, and the right sub-tree.
• Empty Binary Tree: A binary tree with no elements.
• Recursive Nature: The left and right sub-sets are themselves binary trees and can be empty.
• Structural Visuals: Left and right sub-trees are shown using branches from the root node. If no branch exists, the sub-tree is empty.
• Father and Son: If node $A$ is the root and node $B$ is the root of its left sub-tree, $A$ is the father of $B$, and $B$ is the left son of $A$.
• Ancestor and Descendant:     * Node $A$ is an ancestor of node $B$ if $A$ is the father of $B$ or the father of some ancestor of $B$.     * Node $B$ is a left descendant of node $A$ if $B$ is the left son of $A$ or a descendant of the left son of $A$. Right descendants are defined similarly.
• Directional Convention: "Down" refers to moving from the root to leaf nodes; "Up" refers to moving from leaves toward the root.
• Climbing and Descending: Traversing from a leaf to the root is climbing; traversing from the root to leaves is descending.

Specialized Binary Tree Types

• Strictly Binary Trees: A binary tree where every non-leaf node has non-empty left and right sub-trees. Each non-leaf node must have exactly two children.
• Degree in Binary Trees: The number of nodes connected to a particular node. The degree of a leaf node is always $1$.
• Complete Binary Tree: A strictly binary tree in which all leaf nodes are at the same level.
• Extended Binary Tree (2-Tree):     * Created by adding new nodes to leaf nodes and nodes with only one child so that every node has either $0$ or $2$ children.     * Internal Nodes: Original nodes of the tree.     * External Nodes: The new nodes added to create the 2-tree (often represented by square shapes).     * Mathematical Properties of Extended Binary Trees:         1. If a tree has $n$ nodes, it has $n-1$ branches.         2. Every node except the root has exactly one parent.         3. Any two nodes are connected by only one single path.         4. For a binary tree of height $h$, the maximum number of nodes is $2^{h+1}-1$.         5. A binary tree with $n$ internal nodes has $n+1$ external nodes.

Binary Tree Representation

Array Representation

• Nodes are stored sequentially in an array, specified by a maximum size MAXSIZE.
• Indexing: Starting from root at index $0$. Nodes are numbered left to right, level by level, top to bottom. Empty nodes are included in the numbering to maintain structural integrity.
• Formulas for index $n$ (where $0 \le n \le MAXSIZE-1$):     * Father(n): Given by $\lfloor \frac{n-1}{2} \rfloor$, provided $n \ne 0$. If $n=0$, it is the root.     * Left Child (Lchild): Given by $(2n + 1)$.     * Right Child (Rchild): Given by $(2n + 2)$.     * Siblings: if a left child is at index $n$, its right sibling is at $n+1$. If a right child is at index $n$, its left sibling is at $n-1$.

Linked Representation

• Uses a linked list where each node is a structure with three fields:     * Data: Holds the value.     * Left Child: Pointer to the address of the left node.     * Right Child: Pointer to the address of the right node.
• C Structure Definition:

struct tree {
    char info;
    struct node *left;
    struct node *right;
};

• Optional Father Field: In some applications, a fourth field is added to store the parent address:

struct tree {
    char data;
    struct node *father;
    struct node *lchild;
    struct node *rchild;
};

• Internal vs External: Terminal nodes (external) have their lchild and rchild pointers set to NULL.

Binary Tree Operations

• Additional Operations: Tree traversal, insertion, deletion, searching, and copying the tree.

Binary Tree Traversals

Recursive Traversals

Traversal involves visiting each node exactly once. Because of the recursive nature of trees, methods use recursive functions.

1. Pre-order (NLR - Node, Left, Right):     * Algorithm: Visit root $R$, traverse left sub-tree in pre-order, traverse right sub-tree in pre-order.     * C Code Implementation: c void preorder(struct tree *root) { if(root != NULL) { printf("%c\t", root->info); preorder(root->left); preorder(root->right); } }     
2. In-order (LNR - Left, Node, Right):     * Algorithm: Traverse left sub-tree in in-order, visit root $R$, traverse right sub-tree in in-order.     * Values are processed in ascending order if applied to a Binary Search Tree.     * C Code Implementation: c void inorder(struct tree *root) { if(root != NULL) { inorder(root->left); printf("%c\t", root->info); inorder(root->right); } }     
3. Post-order (LRN - Left, Right, Node):     * Algorithm: Traverse left sub-tree in post-order, traverse right sub-tree in post-order, visit root $R$.     * C Code Implementation: c void postorder(struct tree *root) { if(root != NULL) { postorder(root->left); postorder(root->right); printf("%c\t", root->info); } }     

Non-Recursive Traversals using Stacks

Uses a STACK to store node addresses and a PTR for the current node.

• Preorder Algorithm: Push NULL onto stack. Set PTR=ROOT. While PTR is not NULL: process the node, push its right child (if any) onto the stack, update PTR to the left child. If left child is NULL, pop from stack and assign to PTR.
• Inorder Algorithm: Push NULL. Set PTR=ROOT. Descend left-most path, pushing nodes onto the stack until NULL left child. Pop and process node. If node has right child, set PTR to it and repeat.
• Postorder Algorithm: More complex. Push N or its negative -N to distinguish states. A node is processed only when positive when popped.

Binary Search Tree (BST)

• Property: For every node $n$, all elements in the left sub-tree are less than the contents of $n$, and all elements in the right sub-tree are greater than or equal to the contents of $n$.
• Sorting Application: If a BST is traversed in-order, numbers are printed in ascending order.
• Construction Example: Given the list $20$, $17$, $6$, $8$, $10$, $7$, $18$, $13$, $12$, $5$, the first number $20$ becomes the root. Subsequent numbers are placed left if smaller, and right if greater/equal.

Advanced Tree Structures

B-Tree

• A balanced N-way search tree (not a binary tree).
• Purpose: Reduces disk accesses in external sorting.
• Conditions:     1. Height is kept to a minimum; no empty sub-trees above leaves.     2. Leaves are all on the same level.     3. Non-leaf nodes (except root) have at least $\frac{n}{2}$ and at most $n$ children.     4. Root has at most $n$ and at least $2$ children.     5. If a node has $n$ children, it contains $n-1$ values in increasing order.     6. Values in the $(i+1)^{th}$ sub-tree are between the $i^{th}$ and $(i+1)^{th}$ values of the parent.

B+ Tree

• Implementation technique for indexed sequential organization.
• Structure: Indexed part (interior nodes) and sequence set (leaves linked as a list).
• Allows both direct and efficient sequential access to keys.

AVL Tree

• Invented in 1962 by G. M. Adelson-Velskii and E. M. Landis.
• Definition: A balanced binary search tree where the height difference between the left and right sub-trees of all nodes is at most one.
• Balance Factor: Calculated as (Height of Left Sub-tree) - (Height of Right Sub-tree).
• Node contains four fields: Data, Left Pointer, Right Pointer, and Balance Factor.

Threaded Binary Tree

• Eliminates stack/recursion overhead for traversals by using empty pointer fields.
• Right Threads: Replace NULL right pointers with a pointer to the in-order successor.
• Left Threads: Replace NULL left pointers with a pointer to the in-order predecessor.

Constructing Trees from Traversal Sequences

• Root Identification: The first node in a Preorder sequence is the root of the tree.
• Subtree Identification: Locating the root in the Inorder sequence separates elements into the Left Subtree (elements to the left of the root) and Right Subtree (elements to the right).
• Example (Example 4):     * Inorder: $E$, $A$, $C$, $K$, $F$, $H$, $D$, $B$, $G$     * Preorder: $F$, $A$, $E$, $K$, $C$, $D$, $H$, $G$, $B$     * Root is $F$. Left subtree nodes: $E, A, C, K$. Right subtree nodes: $H, D, B, G$.