LEARNING OUTCOME 7

Tree Data Structure

A tree is a non-linear data structure that consists of nodes connected by edges. It resembles an inverted tree, with a root node at the top and branches extending downwards. Each node can have zero or more child nodes.

Properties of a Tree Data Structure

• Root Node: The topmost node of the tree.
• Parent Node: A node that has one or more child nodes.
• Child Node: A node that has a parent node.
• Leaf Node: A node with no children.
• Degree of a Node: The number of children of a node.
• Level of a Node: The distance of a node from the root node.
• Height of a Tree: The maximum level of any node in the tree.
• Depth of a Node: The number of edges from the root node to the node.

Different Types of Trees

Binary Trees

• Binary Tree: A tree where each node has at most two children, referred to as the left child and the right child.
• Binary Search Tree (BST): A binary tree where the left subtree contains nodes with keys less than the root node's key, and the right subtree contains nodes with keys greater than the root node's key.
• Complete Binary Tree: A binary tree in which all levels are completely filled except possibly the last level, which is filled from left to right.
• Full Binary Tree: A binary tree in which every node has either 0 or 2 children.
• Perfect Binary Tree: A binary tree in which all internal nodes have two children, and all leaves are at the same level.

Specialized Trees

• AVL Tree: A self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one.
• Red-Black Tree: A self-balancing binary search tree that uses color coding (red or black) to maintain balance.
• B-Tree: A self-balancing tree that maintains sorted data and allows efficient insertions, deletions, and searches.
• Heap: A specialized tree-based data structure that satisfies the heap property: the parent node is always greater than or equal to (in a max heap) or less than or equal to (in a min heap) its children.
• Trie: A tree-like data structure used to store strings. Each node represents a character, and the path from the root to a leaf represents a word.

Binary Tree Operations

A binary tree is a fundamental data structure in computer science. It consists of nodes, where each node has at most two children: a left child and a right child. The topmost node is called the root. Nodes without children are called leaves.

1. Insertion

To add a new node to a Binary Search Tree, you start at the root and traverse down the tree. If the new value is less than the current node's value, you go left; otherwise, you go right. This continues until an empty spot (a null pointer) is found, where the new node is then inserted.

2. Deletion

Deleting a node from a BST involves three cases:

1. Node is a leaf: Simply remove the node.
2. Node has one child: Replace the node with its child.
3. Node has two children: Find the node's inorder successor (the smallest node in its right subtree), copy its value to the node being deleted, and then delete the inorder successor.

3. Searching

Searching for a value in a BST is efficient. You start at the root and compare the target value. If the target is smaller, you go left; if it's larger, you go right. You repeat this until the value is found or you reach a null pointer, meaning the value isn't in the tree.

4. Tree Traversals

Tree traversals are methods to visit every node in a tree exactly once.

• Inorder Traversal (Left, Root, Right): Visits nodes in ascending order in a BST.
• Preorder Traversal (Root, Left, Right): Useful for creating a copy of the tree.
• Postorder Traversal (Left, Right, Root): Used for deleting nodes from the tree.

Applications of Binary Search Trees

• Efficient Searching: BSTs allow for logarithmic time search operations.
• Sorting: In-order traversal of a BST yields a sorted list of elements.
• Symbol Tables: Used to store key-value pairs efficiently.
• Set and Map Implementations: Many standard library implementations are based on BSTs.
• Huffman Coding: Used to compress data.