Trees as a Special Kind of Graphs

2.1 Main Components of a Tree

Tree — is a special kind of graph that is acyclic and connected. In a tree, there is a unique path between any pair of nodes, making its structure hierarchical.

Main components of a tree:

1. Nodes:

• The main elements of a tree that hold data.
• For instance, each circle in the diagram represents a node.

2. Root:

• A node that has no parent nodes. It serves as the starting point of the tree.
• For example, the top node in the diagram.

3. Leaves:

• Nodes that have no child nodes. They are located at the "ends" of the tree.
• For instance, the nodes at the bottom of the diagram.

4. Edges:

• Connections between nodes. They define parent-child relationships between nodes.
• For instance, the lines connecting nodes in the diagram.

5. Subtrees:

• Any subset of a tree consisting of a node and all its descendants.
• For instance, a branch of the tree emanating from a single node.

Important characteristics of a tree:

1. Height of the tree:

• Length of the path from the root to the farthest leaf.
• For instance, the number of levels in the diagram.

2. Depth of a node:

• Length of the path from the root to a given node.
• For instance, the number of levels from the root to a specific node.

2.2 Binary Trees

We can distinguish different types of trees. Let's start with the simplest ones.

Binary Tree — is a tree where each node has at most two child nodes, referred to as left and right children.

Example of a binary tree:

Special types of binary trees:

Full Binary Tree:

All levels of the tree, except possibly the last, are fully filled, and all nodes at the last level are as far left as possible.

Perfect Binary Tree:

All internal nodes have exactly two children, and all leaves are at the same level.

Balanced Binary Tree:

The difference in height between the subtrees of any node does not exceed 1.

Binary Search Tree:

For any node, its left subtree contains only nodes with lesser values, and its right subtree contains only nodes with greater values.

2.3 n-ary Trees

An n-ary tree is a tree where each node can have at most n child nodes.

Special types of n-ary trees:

1. Ternary Tree (Ternary Tree):

Each node can have at most three child nodes.

2. k-ary Tree (k-ary Tree):

Each node can have at most k child nodes.

Example of a 3-ary tree (each node can have at most three child nodes):

2.4 Examples of Using Trees

1. File System

Uses of trees: Representing the hierarchical structure of files and folders in an operating system.

The root node represents the root directory, internal nodes represent folders, and leaves represent files. Operations include creating, deleting, and moving files and folders.

2. Decision Tree

Uses of trees: Analytics and machine learning for decision making.

Internal nodes represent questions or conditions, branches represent possible answers, and leaves represent final decisions or actions. For example, diagnosing diseases in medicine based on symptoms.

3. XML/HTML Document

Uses of trees: Structured representation of data in XML or HTML format.

The root node represents the entire document, internal nodes represent tags and elements, and leaves represent text nodes and attributes. This helps in parsing and manipulating document contents.

4. Organizational Structure

Uses of trees: Representing hierarchy in organizations and companies.

The root node represents the CEO, internal nodes represent managers and departments, and leaves represent employees. This helps to visualize and manage the organizational structure.

5. Chess Game

Uses of trees: Representing possible moves in the game.

The root node represents the initial state of the game, internal nodes represent possible moves, and leaves represent final game states. This helps in strategizing and decision-making in chess programs.