Binary Trees

COSC220 Binary Search Trees and Heaps

1. Tree Structures

  • Overview of Tree Structures:

    • Trees provide a hierarchical structure for storing data, contrasting with linear structures like arrays, vectors, and lists where elements follow each other sequentially.

  • Binary Expression Tree Example:

    • For the expression a*b + (c-d) / e, the binary expression tree is structured to illustrate operations performed.

2. Tree Terminology

  • Definition of a Tree:

    • A tree is a collection of nodes, which can be empty or contain a distinguished node known as the root. All other nodes originate from this root, forming zero or more non-empty subtrees denoted as T1, T2, …, Tk, connected by directed edges from the root.

  • Components of a Tree:

    • Nodes in subtrees are referred to as successors or descendants of the root node.

    • An immediate successor is termed a child. A leaf node has no children, while an interior node has at least one child.

    • The connection between nodes illustrates the parent-child relationship termed an edge.

    • A path from a parent P to a node N consists of a sequence of nodes P = X0, X1, …, Xk = N, where k is the path length; each node Xi is the parent of Xi+1.

    • The size of a tree is quantified by the number of nodes it contains.

3. Tree Node Level and Depth

  • Node Levels in a Tree:

    • Level of a node N is defined as the length of the path from the root to N. The root is at level 0.

    • The depth of a tree is the length of the longest path from the root to any node.

4. Binary Trees

  • Definition of a Binary Tree:

    • A binary tree restricts each node to having no more than two children. Each child is designated as either left or right.

    • Properties of a Binary Tree (T):

    1. If the set of nodes is empty, T is a tree.

    2. The structure includes a root R and two distinct binary trees: the left subtree TL and the right subtree TR, which may be empty.

  • Examples of Binary Trees:

    • Tree A: Size = 9, Depth = 3

    • Tree B: Size = 5, Depth = 4

5. Complete and Non-Complete Trees

  • Complete Tree Characteristics:

    • A complete tree has all levels filled except possibly the last, filled from left to right.

  • Non-Complete Tree Examples:

    • Example of a non-complete tree missing nodes at level 2 or having nodes that do not follow leftmost positions at level 3.

6. Tree Depth Characteristics

  • Depth Relations:

    • For a complete binary tree with n nodes and depth d:

    1. A perfect complete binary tree will contain 2^{d+1} - 1 nodes.

    2. The smallest complete binary tree with depth d will contain 2^{(d-1)} + 1 - 1 = 2^{d} nodes.

7. Tree Traversals

  • Definition of Tree Traversal:

    • Visiting each node in a tree in some order, performing an operation (e.g., print or modify values).

  • Types of Tree Traversals:

    1. Recursive Traversals:

    • In-Order: (LNR) - Traverse left subtree, visit node, traverse right subtree.

    • Pre-Order: (NLR) - Visit node, traverse left subtree, traverse right subtree.

    • Post-Order: (LRN) - Traverse left subtree, traverse right subtree, visit node.

  • Example Traversing:

    • Given an in-order traversal output of binary tree: Inorder: 2, 3, 4, 5, 7, 9

    • Preorder: 5, 3, 2, 4, 7, 9

    • Postorder: 2, 4, 3, 9, 7, 5

8. Binary Search Trees (BSTs)

  • Binary Search Tree Property:

    • The binary search tree property dictates that if node y is in the left subtree of node x, then key[y] ≤ key[x]. Similarly, if y is in the right subtree of x, key[y] ≥ key[x].

  • BST Operations:

  • BST supports multiple dynamic set operations, including SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, DELETE.

  • Average running time for these operations is O( ext{log} n) whereas the worst case can escalate to O(n) when the tree structure is skewed.

9. Traversing a Binary Search Tree

  • Inorder Tree Walk Algorithm:

INORDER-TREE-WALK(x)
1. if x ≠ NIL
2. then INORDER-TREE-WALK(left[x])
3. print key[x]
4. INORDER-TREE-WALK(right[x])

  • Output Example:
    Printing the keys yields sorted order: 2, 3, 4, 5, 7, 9.

10. Key Searching in a BST

  • TREE-SEARCH Algorithm:

TREE-SEARCH(x, k)
1. if x = NIL or k = key[x]
2. then return x
3. if k < key[x]
4. then return TREE-SEARCH(left[x], k)
5. else return TREE-SEARCH(right[x], k)

  • Running Time:
    O(h) with h representing the height of the tree, which can worsen to O(n) in the worst scenarios.

11. Finding Minimum and Maximum in a BST

  • Finding Minimum:
    Follow left child pointers from the root, utilizing the algorithm:

TREE-MINIMUM(x)
1. while left[x] ≠ NIL
2. do x ← left[x]
3. return x

  • Finding Maximum:
    Follow right child pointers from the root, using a similar logic with the algorithm for maximum.

12. Finding Successors and Predecessors in a BST

  • Successor Definition: The successor of node x is node y such that key[y] is the smallest key > key[x]. Cases include:

    1. If right[x] is non-empty, the successor is TREE-MINIMUM(right[x]).

    2. If right[x] is empty, navigate up until a parent is found for which x is in the left child position.

  • Predecessor Definition:
    The predecessor of node x is node y such that key[y] is the largest key < key[x]. This too follows two cases, similar to successor identification.

13. Insertion into a BST

  • Insertion Logic:
    The new value v traverses the tree by comparing with key[x] and moving left or right accordingly, inserting the new node at the position marked NIL.

14. Deletion in a BST

  • Deletion Cases:

    1. If z has no children, it is deleted by linking the parent to NIL.

    2. If z has one child, its parent is linked directly to its child, bypassing z.

    3. If z has two children, identify its successor (smallest in the right subtree) and integrate it to replace z.

15. Summary of BST Operations

  • Time Complexity for Operations:

    • Search, Predecessor, Successor, Minimum, Maximum, Insert, Delete operations all perform in expected time of O(h) where h is the height of the tree.

  • Problems arising include understanding the height and structure manipulation of BSTs.

16. Building Trees

  • As an exercise, constructing trees based on insertion order demonstrates how structure adjusts with each new value:

    • Example: Insert values in order: 3, 4, 5, 6, 2, 7, 8, 9, 10.

17. Heapsort Algorithm

  • A special algorithm for sorting an array using heap data structures. The process involves building max-heaps from the array and iterating through the array while maintaining heap properties.

18. Special Types of Trees

  • Full Binary Tree:

    • A tree where each node is a leaf or has exactly two children.

  • Complete Binary Tree:

    • All leaves are on the same level, and all internal nodes have two children.

19. Definitions and Properties of Heaps

  • Heap Characteristics:

    • Defined as a nearly complete binary tree with a structural property and an order property about nodes. The root contains the maximum value in a max-heap.

  • Array Representation:

    • Stored as an array with specific index relationships for parent/child mappings:

    • Left Child: A[2i]

    • Right Child: A[2i + 1]

    • Parent: A[floor(i/2)]

20. Heap Operations

  • Heap Property Maintenance:

    • Adjust structures using specific algorithms to uphold the max-heap property after insertions, deletions, or other modifications, notably using MAX-HEAPIFY.

21. Priority Queues Based on Heaps

  • Priority queues leverage heaps for efficiently managing queue elements based on priority.

22. Problems Related to Heaps

  • Tasks may involve theoretical exercises in heap properties and operations such as insertion, extraction, and identification of structural limits.

23. Conclusion

  • Understanding trees and heaps is crucial in efficiently organizing and managing data, focusing on properties enabling quick access and manipulation.

  • Mastery of these concepts paves the path for tackling advanced data structure challenges and optimization tasks.