🔁Data Structures Unit 5 – Trees and Binary Trees

What Are Trees?

• Trees are hierarchical data structures consisting of nodes connected by edges
• Each node in a tree has a parent node, except for the root node at the top of the tree
• Nodes with the same parent are called sibling nodes
• Nodes without any children are called leaf nodes or external nodes
• Trees are used to represent hierarchical relationships between data elements
• Trees have a recursive definition: a tree is either empty or consists of a root and zero or more subtrees
• The depth of a node is the number of edges from the root to the node
• The height of a tree is the maximum depth among all nodes in the tree

Tree Terminology and Concepts

• The root is the topmost node in a tree and has no parent node
• An edge is a connection between two nodes in a tree, representing a parent-child relationship
• The degree of a node is the number of children it has
  • Nodes with a degree of zero are called leaf nodes
• A path is a sequence of nodes and edges connecting a node with a descendant
• The level of a node is the number of edges on the path from the root to the node
• The height of a node is the number of edges on the longest path from the node to a leaf
• A subtree is a portion of a tree that can be viewed as a complete tree on its own
• An ordered tree is a tree in which the children of each node have a specific order

Types of Trees

• Binary Trees: Each node has at most two children (left and right)
• Binary Search Trees (BST): A binary tree where the left subtree of a node contains only nodes with keys less than the node's key, and the right subtree contains only nodes with keys greater than the node's key
• AVL Trees: A self-balancing BST where the heights of the left and right subtrees of any node differ by at most one
• Red-Black Trees: A self-balancing BST with an extra bit of data per node, used to ensure the tree remains balanced during insertions and deletions
• B-Trees: A generalization of BSTs that allows nodes to have more than two children, commonly used in databases and file systems
• Trie (Prefix Trees): A tree-like data structure used to store strings, where each node represents a prefix of the strings in its subtree
• Heap: A complete binary tree that satisfies the heap property (min-heap or max-heap)
• Huffman Trees: Used for data compression, based on the frequency of occurrence of each data item

Binary Trees Explained

• Binary trees are a fundamental data structure in computer science
• Each node in a binary tree has at most two children, referred to as the left child and the right child
• The left subtree of a node contains only nodes with keys less than the node's key
• The right subtree of a node contains only nodes with keys greater than the node's key
• Binary trees are used as the basis for more complex tree structures, such as BSTs, AVL trees, and Red-Black trees
• A complete binary tree is a binary tree in which all levels, except possibly the last, are completely filled, and all nodes are as far left as possible
• A perfect binary tree is a binary tree in which all internal nodes have two children, and all leaf nodes are at the same level
• The maximum number of nodes at level $i$ in a binary tree is $2^i$

Tree Traversal Methods

• Tree traversal is the process of visiting each node in a tree exactly once
• There are three main types of tree traversal: preorder, inorder, and postorder
  • Preorder traversal: Visit the root, traverse the left subtree, then traverse the right subtree
  • Inorder traversal: Traverse the left subtree, visit the root, then traverse the right subtree
  • Postorder traversal: Traverse the left subtree, traverse the right subtree, then visit the root
• Level-order traversal (Breadth-First Search) visits nodes level by level, from left to right
• The choice of traversal method depends on the specific application and the desired order of processing the nodes
• Recursive implementations of traversal methods are commonly used due to the recursive nature of trees
• Iterative implementations using stacks or queues are also possible for traversal methods
• The time complexity of all traversal methods is $O(n)$, where $n$ is the number of nodes in the tree

Tree Operations and Algorithms

• Insertion: Adding a new node to the tree while maintaining the tree's properties
  • In a BST, insertion involves comparing the new node's key with the keys of existing nodes to find the appropriate position
• Deletion: Removing a node from the tree while maintaining the tree's properties
  • In a BST, deletion may require restructuring the tree to maintain the BST property
• Search: Finding a node with a specific key in the tree
  • In a BST, search can be performed efficiently by comparing the target key with the keys of nodes traversed
• Minimum and Maximum: Finding the node with the smallest or largest key in the tree
• Successor and Predecessor: Finding the node with the next larger or next smaller key relative to a given node
• Height and Depth calculation: Determining the height of a tree or the depth of a specific node
• Balancing: Adjusting the structure of the tree to maintain a balanced height, improving performance (e.g., AVL trees, Red-Black trees)
• Lowest Common Ancestor (LCA): Finding the lowest common ancestor of two nodes in a tree

Implementing Trees in Code

• Trees can be implemented using various data structures, such as arrays or linked lists
• A common approach is to use a node class or struct that contains data and references to its children
  • In a binary tree, each node typically has a data field and two child pointers (left and right)
• Recursive algorithms are often used to implement tree operations due to the recursive nature of trees
• Iterative implementations can also be used, typically involving stacks or queues
• When using arrays to represent trees, the index of a node's parent, left child, and right child can be calculated based on the node's index:
  • Parent index:

    (i - 1) // 2

  • Left child index:

    2 * i + 1

  • Right child index:

    2 * i + 2

• Linked list representations allow for dynamic memory allocation and efficient insertion and deletion operations
• The choice of implementation depends on factors such as the specific requirements, memory constraints, and the balance between performance and flexibility

Real-World Applications of Trees

• File systems: Directories and files are organized in a hierarchical tree structure
• HTML/XML documents: The structure of HTML and XML documents can be represented as a tree, with elements as nodes and child elements as subtrees
• Organizational hierarchies: Company organizational charts, family trees, and taxonomic classifications are often modeled using trees
• Computer networks: Trees are used to represent network topologies and routing algorithms (e.g., spanning trees)
• Compiler design: Abstract syntax trees (ASTs) are used to represent the structure of source code during compilation
• Artificial Intelligence: Decision trees and game trees are used in AI algorithms for decision making and game playing
• Databases: B-trees and B+ trees are used in database indexing to facilitate efficient search and insertion operations
• Data compression: Huffman coding uses a tree structure to assign variable-length codes to characters based on their frequencies