1 Introduction to Trees

What is a tree data structure?

A tree data structure is a hierarchical model that organizes data in a way that resembles a tree, with a single “root” node at the top and subsequent layers of nodes that branch out like the limbs of a tree.

Definition and Structure

  1. Hierarchical Organization:
    A tree is used to represent data with a natural hierarchy. Each tree consists of nodes connected by edges. The topmost node is called the root, and every other node in the tree has a parent node and may have zero or more child nodes.
  2. Nodes and Edges:
    The basic building blocks of a tree are nodes, which store data, and edges, which establish relationships between these nodes. This structure allows trees to model relationships like family ancestries, folder structures, and organizational charts.

Real-world applications and use cases

2 Basic Terminology and Concepts

Nodes
The fundamental units or elements of a tree that store data and may connect to other nodes.
Edges
The connections or links between nodes that define the relationship between parent and child nodes.
Root
The topmost node of a tree, which does not have a parent. It serves as the starting point for the tree structure.
Leaf
A node that does not have any children. Leaf nodes typically mark the end of a branch in the tree.
Parent
A node that has one or more child nodes directly connected below it in the hierarchy.
Child
A node that is a descendant of another node (its parent) in the tree structure.
Sibling
Nodes that share the same parent node. They exist at the same level in the hierarchy.
Depth
The number of edges from the root node to a specific node. It represents the level of a node within the tree.
Height
The length of the longest path from a node down to a leaf. The height of the tree is measured from the root.
Levels
The different layers or tiers in a tree, starting from the root (level 0) and increasing by one with each subsequent layer of child nodes.
Degree
The number of children a node has. For the entire tree, the degree can refer to the maximum number of children any node possesses.

3 Tree Representations

Linked representations

In Linked representations, each node in the tree is typically represented by an object or a structure that contains data and pointers (or references) to its child nodes.

In a linked representation, every node in the tree is created as a separate entity that “links” to its children.

For example, in a binary tree (a common type of tree where each node has at most two children), each node contains:

  • Data: The value or information stored in the node.
  • Left Pointer: A reference to the left child node.
  • Right Pointer: A reference to the right child node.

For trees that are not strictly binary, you might have a list or an array of pointers to all child nodes.

Consider a simple binary tree node written in a language like Python:

</>
Copy
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

In this example:

  • data holds the integer value.
  • left is a pointer to the left child.
  • right is a pointer to the right child.

Imagine we want to build a simple tree with the following structure: 

      10
     /  \
    5    15

Step 1: Create the root node.

</>
Copy
root = TreeNode(10)

Step 2: Create the left and right child nodes.

</>
Copy
root.left = TreeNode(5)
root.right = TreeNode(15)

Now, root is a node containing the value 10, with its left child pointing to a node containing 5 and its right child pointing to a node containing 15.

Visualize the tree as follows: 

       [10]
       /  \
    [5]    [15]

Each node “knows” about its children through pointers. This direct linkage makes it easy to traverse the tree, add nodes, or modify the structure dynamically.

Benefits of Linked Representations:

  • Dynamic Memory Allocation: Nodes are created on the heap, allowing the tree to grow as needed without allocating a large contiguous block of memory.
  • Easy Modification: Adding or removing nodes is straightforward because you only update a few pointers.
  • Intuitive Structure: The linked representation mirrors the natural hierarchical structure of trees, making the code easier to understand and maintain.

Array Representations of Tree

While linked representations use nodes with pointers, array representations store tree elements in a contiguous block of memory. This method is especially common for complete binary trees, where the structure of the tree allows you to calculate the position of parent and child nodes using simple arithmetic.

In an array representation of a binary tree, if a node is stored at index i:

  • left child is stored at index 2*i + 1
  • right child is stored at index 2*i + 2
  • parent is stored at index (i - 1) // 2

Let’s see how this works with a Python example.

Consider a binary tree structured like this: 

          10
         /  \
        5    15
       / \
      3   7

We can represent this tree in an array as:

</>
Copy
tree = [10, 5, 15, 3, 7]

In this array:

  • The root 10 is at index 0.
  • The left child of 10 is 5 at index 1 (2*0+1=1).
  • The right child of 10 is 15 at index 2 (2*0+2=2).
  • The left child of 5 is 3 at index 3 (2*1+1=3).
  • The right child of 5 is 7 at index 4 (2*1+2=4).

To access these nodes programmatically, you can write simple functions in Python. For example:

</>
Copy
def get_left_child(index, tree):
    child_index = 2 * index + 1
    if child_index < len(tree):
        return tree[child_index]
    return None

def get_right_child(index, tree):
    child_index = 2 * index + 2
    if child_index < len(tree):
        return tree[child_index]
    return None

# Example usage:
tree = [10, 5, 15, 3, 7]
print("Left child of 10:", get_left_child(0, tree))   # Outputs 5
print("Right child of 10:", get_right_child(0, tree))  # Outputs 15

This approach leverages the properties of complete binary trees to efficiently compute child and parent positions using simple index calculations.

Note: Array representations work best when the tree is complete (all levels are fully filled except possibly the last, which is filled from left to right). For sparse trees, this method might waste space as many positions in the array could be unused.

4 Types of Trees

General Tree

A general tree is a tree data structure where each node can have an arbitrary number of children. It is flexible and can model hierarchies that are not strictly binary.

</>
Copy
class GeneralTreeNode:
    def __init__(self, data):
        self.data = data
        self.children = []

# Example: Creating a general tree node with two children
root = GeneralTreeNode("Root")
child1 = GeneralTreeNode("Child 1")
child2 = GeneralTreeNode("Child 2")
root.children.append(child1)
root.children.append(child2)

This example shows a basic node for a general tree where the children attribute is a list that can hold any number of child nodes.

Binary Tree

A binary tree is a tree structure in which each node has at most two children, commonly referred to as the left child and the right child.

</>
Copy
class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Example: Creating a simple binary tree
root = BinaryTreeNode(10)
root.left = BinaryTreeNode(5)
root.right = BinaryTreeNode(15)

This code creates a binary tree with a root node of 10, a left child of 5, and a right child of 15. Each node has at most two children.

Binary Search Tree (BST)

A Binary Search Tree is a binary tree where for every node, the values in the left subtree are less than the node’s value, and the values in the right subtree are greater.

</>
Copy
class BSTNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def insert(root, data):
    if root is None:
        return BSTNode(data)
    if data < root.data:
        root.left = insert(root.left, data)
    else:
        root.right = insert(root.right, data)
    return root

# Example: Inserting elements into a BST
root = BSTNode(10)
insert(root, 5)
insert(root, 15)
insert(root, 3)
insert(root, 7)

This BST example includes an insertion function that places new nodes into the tree based on their value, maintaining the BST property.

AVL Tree

An AVL Tree is a self-balancing Binary Search Tree where the height difference between the left and right subtrees (balance factor) is at most one for all nodes.

</>
Copy
class AVLNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1

def get_height(node):
    return node.height if node else 0

def right_rotate(y):
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    y.height = max(get_height(y.left), get_height(y.right)) + 1
    x.height = max(get_height(x.left), get_height(x.right)) + 1
    return x

# Example: Performing a right rotation
node = AVLNode(30)
node.left = AVLNode(20)
node.left.left = AVLNode(10)
rotated_root = right_rotate(node)

This snippet demonstrates a right rotation in an AVL Tree, which is one of the key operations used to maintain tree balance after insertions or deletions.

Red-Black Tree

A Red-Black Tree is a self-balancing Binary Search Tree that uses an extra bit (red or black) to ensure the tree remains approximately balanced during insertions and deletions.

</>
Copy
class RBNode:
    def __init__(self, data, color="red"):
        self.data = data
        self.color = color  # "red" or "black"
        self.left = None
        self.right = None
        self.parent = None

# Note: A full implementation involves additional functions for rotations and color fixes.
# This is a simplified node structure for a Red-Black Tree.

This simplified example shows the node structure for a Red-Black Tree. A complete implementation would include rotation and color-fixing methods to maintain the red-black properties.

B-Tree

B-Trees are self-balancing trees that generalize the concept of binary search trees by allowing more than two children per node. They are commonly used in databases and file systems.

</>
Copy
class BTreeNode:
    def __init__(self, t, leaf=False):
        self.t = t  # Minimum degree (defines the range for number of keys)
        self.keys = []
        self.children = []
        self.leaf = leaf

# Example: Creating a B-Tree node with minimum degree 3
node = BTreeNode(t=3, leaf=True)

This example demonstrates the basic structure of a B-Tree node. The node can hold multiple keys and has multiple children, which makes B-Trees highly efficient for systems that read and write large blocks of data.

Heap

A Heap is a specialized tree-based data structure that satisfies the heap property. In a min-heap, every parent node is less than or equal to its children; in a max-heap, every parent node is greater than or equal to its children.

</>
Copy
import heapq

# Example: Creating and using a min-heap in Python
heap = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 15)
min_value = heapq.heappop(heap)  # Returns 5, the smallest element

This example uses Python’s built-in heapq module to demonstrate a min-heap, where the smallest element is always at the root and can be efficiently retrieved.

Trie (Prefix Tree)

A Trie, or prefix tree, is a specialized tree used to store associative data structures, typically strings. It allows efficient retrieval of words by their prefixes.

</>
Copy
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

# Example: Inserting words into a Trie
trie = Trie()
trie.insert("hello")
trie.insert("helium")

This code sets up a Trie for storing strings and demonstrates how to insert words. Each node represents a character, and paths down the tree represent words.

Segment Tree

A Segment Tree is used for storing information about intervals or segments. It allows querying which of the stored segments contain a given point efficiently.

</>
Copy
class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (2 * self.n)
        # Build the tree by inserting leaves
        for i in range(self.n):
            self.tree[self.n + i] = data[i]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def query(self, l, r):
        l += self.n
        r += self.n
        result = 0
        while l < r:
            if l % 2:
                result += self.tree[l]
                l += 1
            if r % 2:
                r -= 1
                result += self.tree[r]
            l //= 2
            r //= 2
        return result

# Example: Creating a segment tree and querying a range
data = [1, 3, 5, 7, 9, 11]
seg_tree = SegmentTree(data)
print("Sum of values in range [1, 5):", seg_tree.query(1, 5))

This segment tree example builds a tree for range sum queries. The tree allows efficient querying and updating of ranges, which is particularly useful in scenarios with frequent interval queries.

Tree Traversals

  • Depth-first search (DFS): Pre-order, In-order, Post-order
  • Breadth-first search (BFS): Level-order

Binary Trees

  • Structure and properties
  • Common operations (insertion, deletion, searching)

Binary Search Trees (BSTs)

  • BST properties
  • Implementation details and operations
  • Complexity analysis

Balanced Trees

  • Need for balancing
  • AVL trees and rotations
  • Red-Black trees and their properties
  • B-Trees (and B+ Trees if applicable)

Specialized Trees

  • Heaps (min-heap, max-heap)
  • Tries (prefix trees)
  • Segment trees and Fenwick trees for range queries

Practical Implementation Examples

  • Code snippets in popular programming languages
  • Use cases and performance benchmarks

Advanced Topics and Optimizations

  • Memory and space optimizations
  • Parallel and concurrent tree algorithms

Conclusion and Further Reading

  • Summary of key points
  • Additional resources and research directions