7.1 Search, Insertion, Deletion, and Sorting

In discrete mathematics and computer science, a tree is a fundamental data structure for representing hierarchical relationships. We refer to a tree as a connected, acyclic graph. This means it is a set of nodes (also called vertices) connected by edges. There are no cycles (i.e., no paths that start and end at the same node). It is connected, meaning there is a path between any two nodes. Formally, a tree with [latex]n[/latex] nodes has exactly [latex]n - 1[/latex] edges.

A rooted tree is a tree in which one node is designated as the root. From this root, every other node is reachable by a unique path. This structure introduces a natural hierarchy:

• Root: The topmost node.
• Parent: A node that has children.
• Child: A node that descends from a parent.
• Leaf: A node with no children.
• Subtree: A tree formed by a node and all its descendants.

Rooted trees are directional, meaning that their edges implicitly point away from the root toward the leaves.

The level of a vertex (or node) in a rooted tree is defined as the number of edges from the root to that vertex. The root is at level 0. Its immediate children are at level 1. Their children are at level 2, and so on. This concept helps describe the depth of nodes in a hierarchical structure.

The height of a tree is the maximum level of any vertex in the tree. It represents the longest path from the root to a leaf. A tree with only the root has a height of 0. A tree where the deepest leaf is at level 3 has height 3. Height is a key measure of a tree’s efficiency, especially in search operations, where time complexity often depends on tree height.

A hierarchical tree is a rooted tree that represents relationships in a top-down structure, where each node may have one parent and zero or more children.

In a rooted tree, nodes are connected hierarchically. Understanding the relationships between nodes is essential for analyzing and manipulating tree structures. The following definitions are used throughout this chapter:

• A parent is a node that has one or more children.
• A child is a node that descends directly from another node.
• Ancestors are all nodes along the path from a given node to the root.
• Descendants are all nodes that descend from a given node.
• Siblings are nodes that share the same parent.
• A terminal vertex (leaf) is a node with no children.
• An internal vertex (branch) is a node that has at least one child.
• A subtree of [latex]T[/latex] rooted at [latex]x[/latex] is a tree consisting of node [latex]x[/latex] and all its descendants.

A graph that contains no cycles is called acyclic. This means no path starts and ends at the same vertex while traversing each edge exactly once. In the context of undirected graphs (see Section 9.2), this means the graph does not loop back on itself. A tree is a special kind of acyclic graph that is also connected, meaning there is a path between every pair of vertices.

The following theorem provides several methods for determining whether a graph is a tree. These properties are foundational in graph theory and are often used in algorithm design.

A binary tree is a type of rooted tree in which each node has at most two children. These children are typically referred to as the left and right children. Binary trees are widely used in IT for searching and sorting.

The left child is the child node that appears on the left side of a parent node. The right child is the child node that appears on the right side of a parent node. Each node in a binary tree may have no children (a leaf), one child (left or right), or two children (left and right)

A full binary tree is a binary tree in which every internal vertex has exactly two children. This means each node is either a leaf (no children) or an internal node with two children. No node has only one child. Full binary trees are important in both theoretical and applied computer science.

The following theorem provides a simple way to determine the size and shape of a full binary tree given the number of internal nodes.

A binary tree in which all internal nodes have two children and all leaves are at the same level is called a perfect binary tree.

The next theorem is an inequality that expresses a fundamental limit: the number of leaves in a binary tree is bounded by the height. In other words, to accommodate more leaves, the tree must be taller. This theorem is useful in analyzing the efficiency of tree-based algorithms, especially in search and decision trees.

A binary search tree (BST) is a type of binary tree in which each node contains a key (or value), and the tree satisfies the following ordering property:

• The left child of a node contains a key less than the node’s key.
• The right child of a node contains a key greater than the node’s key.
• This property holds recursively for all nodes in the tree.

BSTs are widely used in searching, sorting, and maintaining ordered data structures. They allow efficient operations such as search, insertion, and deletion.

To search for a value in a BST, follow these steps:

1. Start at the root node.
2. Compare the target value with the current node’s key.
   1. If the target equals the current key, the search is successful.
   2. If the target is less than the current key, move to the left child.
   3. If the target is greater than the current key, move to the right child.
3. Repeat the comparison at each node until the value is found or a leaf is reached (i.e., the search fails).

This process leverages the BST’s ordering property and is efficient, especially in balanced trees.

To insert a new value into a BST, follow these steps:

1. Start at the root node.
2. Compare the value to be inserted with the current node’s key.
   1. If the value is less than the current key, move to the left child.
   2. If the value is greater than the current key, move to the right child.
3. Repeat the comparison until you reach a null (empty) child position.
4. Insert the new value at that position as a new leaf node.

This process maintains the BST property: left children are smaller, right children are larger.

Deleting a node from a BST must preserve the binary search tree property. There are three cases to consider:

Case 1: Node to be deleted is a leaf (no children)

Remove the node.

Case 2: Node has one child

Remove the node and connect its parent directly to its child.

Case 3: Node has two children

Replace the node with either:

• • • Its in-order predecessor (maximum value in the left subtree), or
    • Its in-order successor (minimum value in the right subtree)

Then delete the predecessor/successor node (which will now fall under Case 1 or 2).

A binary search tree can be used to sort a list of values by traversing it in order. In-order traversal visits nodes in the following order:

1. Traverse the left subtree
2. Visit the current node
3. Traverse the right subtree

When applied to a BST, this traversal yields the values in ascending order.

The steps to sort using a BST are as follows:

1. Insert all values into a binary search tree.
2. Perform in-order traversal to retrieve the values in sorted order.

This method is known as tree sort.

While we have demonstrated in-order traversal, which retrieves values from a binary search tree in sorted order, two other common traversal methods are pre-order traversal and post-order traversal. Pre-order traversal visits the nodes in the order: node, left subtree, then right subtree, and is commonly used when copying a tree. Post-order traversal visits the nodes in the order left subtree, right subtree, and then the node and is typically used when deleting trees.