Data Structures and Algorithms

Data Structures and Algorithms

• Familiarity with order of running time, Big-Oh function, and amortized analysis is assumed
• Storing elements in a linear fashion is possible with vectors and lists
• Position, containers, and iterators are related concepts

Trees

• A tree data structure is a hierarchical structure used to represent and organize data in a way that is easy to navigate and search
• A tree consists of nodes connected by edges, with a topmost node called the root and nodes below it called child nodes
• Each node can have multiple child nodes, forming a recursive structure

Types of Trees

• Binary tree: a node can have a maximum of two child nodes
• Balanced tree: the height of the left sub-tree and the right sub-tree is equal or differs at most by 1
• Binary search tree: used for searching and sorting algorithms

Applications of Tree Data Structures

• Spanning trees: used in routers to direct packets to their destination
• Binary Search Tree: helps maintain a sorted stream of data
• Storing hierarchical data: tree data structures are used to store data in a hierarchical order
• Syntax tree: represents the structure of a program's source code, used in compilers
• Heap: a tree data structure used to implement priority queues
• Artificial intelligence: decision trees and other tree-based models are used to make predictions and classify data
• Database: some databases use trees to organize data for efficient searching and sorting
• Network: routing algorithms for networks use trees to find the best path for data to travel

Tree Traversal Algorithms

• Preorder traversal: visits a node before its descendants
• Postorder traversal: visits a node after its descendants
• Inorder traversal: visits a node after its left subtree and before its right subtree

Traversal Computations

• Depth of a node: the distance from the root to the node
• Height of a tree: the maximum depth of its leaves

Tree Traversal Example

• "du" command: prints the aggregate file sizes from the current directory

Tree Traversal Complexity

• Preorder traversal: O(n)
• Postorder traversal: O(n)
• Inorder traversal: O(n)

Implementation of Tree Traversal

• See https://www.programiz.com/dsa/tree-traversal for implementation details

Binary Trees

• A binary tree is a tree with each internal node having at most two children
• Applications include arithmetic expressions and decision processes

Trees in Data Structures

• A tree is a hierarchical data structure used to represent and organize data in a way that is easy to navigate and search.
• A tree consists of nodes connected by edges, with a hierarchical relationship between nodes.
• The topmost node is called the root, and nodes below it are called child nodes.

Types of Nodes

• Root node: the topmost node in a tree.
• Internal node: a node with at least one child node.
• External node (leaf): a node without children.

Tree Terminology

• Ancestors of a node: parent, grandparent, grand-grandparent, etc.
• Descendants of a node: child, grandchild, grand-grandchild, etc.
• Depth of a node: the number of ancestors.
• Height of a tree: the maximum depth of any node.

Recursive Definition of a Tree

• A tree consists of a root, and zero or more subtrees T1, T2, … , Tk, with an edge from the root to the root of each subtree.

Preorder and Inorder Traversal

• Preorder traversal: a node is visited before its descendants.
• Inorder traversal: a node is visited after its left subtree and before its right subtree.

Binary Trees

• A binary tree is a tree with each internal node having at most two children (exactly two for proper binary trees).
• Applications: arithmetic expressions, decision processes, searching.

Properties of Proper Binary Trees

• Notation: n (number of nodes), e (number of external nodes), i (number of internal nodes), h (height).
• Properties: e = i + 1, n = 2e - 1, h ≤ i, h ≤ (n - 1)/2, e ≤ 2h, h ≥ log2 e, h ≥ log2 (n + 1) - 1.

BinaryTree ADT

• Extends the Tree ADT, inheriting all its methods.
• Additional methods: position p.left(), position p.right().
• Proper binary tree: each node has either 0 or 2 children.

Evaluating Arithmetic Expressions

• Specialization of a postorder traversal, returning the value of a subtree.
• Recursive method combining the values of subtrees when visiting an internal node.