Trees

 What is Tree Data Structure?

A tree is a hierarchical data structure that consists of nodes connected by edges such that there exists exactly one path between any two nodes. Each node in a tree has a parent-child relationship with other nodes, except for the topmost node, called the root, which has no parent, and the nodes at the bottom, called leaves, which have no children.

Here are some key terms associated with trees:

Node:A fundamental part of a tree that holds data and may have a link to other nodes.Each node contain some key data.

Edge:The connection between two nodes.

Root:The topmost node in a tree, from which all other nodes are descended.Parent: A node in a tree that has one or more child nodes.

Parent:A node in the tree with at least one child.

Child: A node in a tree that has a parent node.

Siblings: Nodes that share the same parent in a tree.

Leaf: A node in a tree that has no children, i.e., it is at the bottom of the hierarchy.
Subtree: A tree formed by a node and its descendants.

Depth: The level or distance of a node from the root. The root is at depth 0, its children are at depth 1, and so on.

Height:The length of the longest path from the root to a leaf.
Depth:The level or distance of a node from the root.

Visiting − Visiting refers to checking the value of a node when control is on the node.

Traversing − Traversing means passing through nodes in a specific order.

Picture courtesy: geeksforgeeks

Trees are widely used in computer science and programming for representing hierarchical relationships and structures. They are used in various algorithms and data structures like binary search trees, heaps, expression trees, etc. Understanding trees is fundamental to many areas of computer science and is crucial for developing efficient algorithms for tasks such as searching, sorting, and representing hierarchical relationships in data.

There are several types of trees in computer science, each with its specific characteristics and use cases. Here are some common types of trees:

Binary Tree:A tree in which each node has at most two children, referred to as the left child and the right child.

Binary Search Tree (BST):A binary tree in which the left child of a node contains only nodes with keys less than the node's key, and the right child contains only nodes with keys greater than the node's key. This property allows for efficient searching.

AVL Tree (Adelson-Velsky and Landis Tree):A self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one. Balancing is performed through rotations to maintain the balance property, ensuring logarithmic height and efficient operations.

Red-Black Tree:Another type of self-balancing binary search tree with additional constraints. Nodes in a red-black tree are labeled with colors (red or black), and certain properties are maintained to ensure balance. It guarantees logarithmic height and efficient operations.

B-Tree:A balanced tree structure designed for use in databases and file systems. B-trees are optimized for systems that read and write large blocks of data, making them suitable for storage structures.

Trie (Prefix Tree):A tree-like data structure used to store a dynamic set or associative array where the keys are usually strings. The structure of the trie allows for efficient search, insertion, and deletion operations.

N-ary Tree:A tree in which each node can have more than two children. The number of children a node can have is not fixed and can vary.

Quadtree and Octree:Spatial trees used in computer graphics, geographic information systems, and other applications to partition space into regions with varying levels of detail. Quadtrees are used in 2D, and octrees extend the concept to 3D.

Heap:A specialized tree-based data structure that satisfies the heap property. Heaps are often used in priority queues and for heap-sort algorithms.

Expression Tree:A binary tree used to represent expressions in a way that facilitates their evaluation. Each leaf node represents an operand, and internal nodes represent operators.

Suffix Tree:A tree data structure that represents all the suffixes of a given string. It is commonly used in string processing and pattern matching.

These are just a few examples, and there are many other variations and specialized tree structures based on specific requirements and applications in computer science and data structures.

Generic Trees

Generic trees are a collection of nodes where each node is a data structure that consists of records and a list of references to its children(duplicate references are not allowed). Unlike the linked list, each node stores the address of multiple nodes. Every node stores address of its children and the very first node’s address will be stored in a separate pointer called root.

The Generic trees are the N-ary trees which have the following properties:

1. Many children at every node.
2. The number of nodes for each node is not known in advance.

To represent the above tree, we have to consider the worst case, that is the node with maximum children (in above example, 6 children) and allocate that many pointers for each node.

Disadvantages of the above representation are:

• Memory Wastage – All the pointers are not required in all the cases. Hence, there is lot of memory wastage.
• Unknown number of children – The number of children for each node is not known in advance.

Simple Approach:

For storing the address of children in a node we can use an array or linked list. But we will face some issues with both of them.

• In Linked list, we can not randomly access any child’s address. So it will be expensive.
• In array, we can randomly access the address of any child, but we can store only fixed number of children’s addresses in it.

Efficient Approach:

First child / Next sibling representation

In the first child/next sibling representation, the steps taken are:

At each node-link the children of the same parent(siblings) from left to right.Remove the links from parent to all children except the first child.

Since we have a link between children, we do not need extra links from parents to all the children. This representation allows us to traverse all the elements by starting at the first child of the parent.

Advantages: 

• Memory efficient – No extra links are required, hence a lot of memory is saved.
• Treated as binary trees – Since we are able to convert any generic tree to binary representation, we can treat all generic trees with a first child/next sibling representation as binary trees. Instead of left and right pointers, we just use firstChild and nextSibling.
• Many algorithms can be expressed more easily because it is just a binary tree.
• Each node is of fixed size ,so no auxiliary array or vector is required.