A tree data structure is a widely used abstract data type in computer science that consists of a set of nodes connected by edges. In a tree, one node is designated as the root node, and all other nodes are either parent nodes or child nodes. Each node in the tree can have multiple child nodes, but only one parent node. A tree data structure is hierarchical in nature, which means that the nodes are organized in levels.
A tree data structure can be used to represent hierarchical relationships, such as file systems, organization charts, or the structure of a web page. Trees are also used in search algorithms, decision trees, and many other applications.
Tree Terminologies
Path
A path in a tree is a sequence of nodes that can be traversed from one node to another node by following the edges of the tree. For example, in the binary tree below, the path from node 2 to node 6 is [2, 3, 6].
5
/ \
3 7
/ / \
2 6 8
Root
The root of a tree is the topmost node of the tree, from which all other nodes are descendants. In the binary tree above, the root node is 5.
Parent
The parent of a node in a tree is the node that is connected to it by an edge going towards the root. For example, in the binary tree above, the parent of node 2 is node 3.
Child
A child of a node in a tree is a node that is connected to it by an edge going away from the root. For example, in the binary tree above, the children of node 3 are nodes 2 and 4.
Leaf
A leaf in a tree is a node that has no children. For example, in the binary tree above, the leaves are nodes 2, 4, 6, and 8.
Subtree
A subtree of a tree is a tree that consists of a node and all of its descendants. For example, in the binary tree above, the subtree rooted at node 3 consists of nodes 3, 2, and 4.
Visiting
Visiting a node in a tree means accessing or processing the data stored in the node. For example, in a binary search tree, visiting a node may involve comparing its key with a search key to determine whether to traverse to its left or right child.
Traversing
Traversing a tree means visiting all the nodes of the tree in a certain order. There are different ways to traverse a tree, such as depth-first traversal and breadth-first traversal.
Levels
The level of a node in a tree is the number of edges on the path from the root to that node. The root node is at level 0, its children are at level 1, their children are at level 2, and so on.
Keys
In a tree that stores key-value pairs, the key is a unique identifier used to locate a specific value in the tree. For example, in a binary search tree, the keys are arranged in a specific order so that searching for a key can be done efficiently by traversing the tree based on the comparison of keys.
5
/ \
3 7
/ / \
2 6 8
Path: [5, 3, 2]
Root: 5
Parent:
3 is the parent of 2
5 is the parent of 3 and 7
7 is the parent of 6 and 8
Child:
2 and 3 are the children of 3
6 and 8 are the children of 7
3 and 7 are the children of 5
Leaf: 2, 6, 8
Subtree:
Subtree rooted at node 3:
3
/ \
2 -
Visiting: Accessing or processing data stored in a node
Traversing: Visiting all nodes of the tree in a certain order
Levels:
Level 0: 5
Level 1: 3, 7
Level 2: 2, 6, 8
Keys: Unique identifier used to locate a specific value in the tree
Types Of Trees
Binary Tree
A binary tree is a tree data structure in which each node has at most two children. Here's an example of a binary tree:
5
/ \
3 7
/ \ / \
2 4 6 8
In this binary tree, the root node is 5, and it has two children, 3 and 7. The node 3 has two children, 2 and 4, and the node 7 has two children, 6 and 8. The nodes 2, 4, 6, and 8 are leaf nodes.
Balanced Tree
A balanced tree is a tree in which the height of the left and right subtrees of any node differ by at most one. Here's an example of a balanced tree:
5
/ \
3 7
/ \ / \
2 4 6 8
This is the same tree as the binary tree example above, and it is also a balanced tree.
Binary Search Tree
A binary search tree is a binary tree in which the left subtree of a node contains only nodes with values less than the node's value, and the right subtree contains only nodes with values greater than the node's value. Here's an example of a binary search tree:
5
/ \
3 7
/ \ \
2 4 9
/ \
8 10
In this binary search tree, each node satisfies the binary search tree property. For example, the left subtree of the node 5 contains only nodes with values less than 5, and the right subtree contains only nodes with values greater than 5.
AVL Tree
An AVL tree is a self-balancing binary search tree in which the heights of the left and right subtrees of any node differ by at most one. Here's an example of an AVL tree:
5
/ \
3 8
/ \ / \
2 4 7 9
In this AVL tree, each node satisfies the binary search tree property and the AVL tree balancing property. The heights of the left and right subtrees of each node differ by at most one.
B-Tree
A B-tree is a self-balancing tree data structure that is commonly used in database systems and file systems. Here's an example of a B-tree:
[5]
/ \
[2,3] [7,9]
/ | \ / | \
[1] [2] [6] [7] [10]
In this B-tree, each node has multiple keys and child nodes. The keys are sorted in ascending order within each node, and the child nodes between each adjacent pair of keys represent the corresponding ranges of keys. The number of keys and child nodes in each node is within a certain range specified by the order of the B-tree.
Summarizing Up
A tree is a hierarchical data structure that consists of nodes connected by edges or branches. It has a single root node, and every other node in the tree is either a direct or indirect descendant of the root. Each node may have zero or more child nodes, which are connected to it by edges. Nodes with no children are called leaves. Trees are used to represent hierarchical relationships between data, such as the file system on a computer, or the organization of elements in a web page. They are also used in algorithms such as search, sorting, and decision-making.