what is non-linear data structure?

Nonlinear data structures stand in contrast to their linear counterparts by allowing each data element to connect with multiple others, creating a complex web-like arrangement. 

Unlike linear structure where data is organized sequentially, nonlinear structures embrace a more intricate relationship among elements, offering a versatile approach to storing and retrieving information.

Some types of Nonlinear Data Structures:

Trees:

a tree is a non-linear data structure in which items are arranged in a sorted sequence.

it is a way to represent the hierarchal relationship existing among several data items.

Several elements work together to define its organization and relationships

Node: A fundamental building block of a tree, a node represents an individual element within the structure. Nodes contain data and may have links (references or pointers) to other nodes.

Edge: It is a connecting line of two nodes.

Root: The topmost node in a tree is called the root. It serves as the starting point for traversing the tree and is the only node without a parent.


Parent: A node in a tree can have zero or more child nodes. The node that is directly above a given node is referred to as its parent.


Child: Nodes that are directly below another node are its children. A node can have zero or more children, depending on the type of tree.

Terminal node: A node with degree zero is called a terminal node.

Non-terminal node: A node not with degree zero is called a terminal node.

Siblings: Nodes that share the same parent are called siblings. They are at the same level in the hierarchy.


Leaf: Nodes that have no children are called leaves or leaf nodes. They are the terminal nodes at the bottom of the tree.


Subtree: A subtree is a portion of a tree, including a node and all its descendants. In other words, a subtree is a tree within a tree.


Depth: The depth of a node is the length of the path from the root to that particular node. The root node has a depth of 0.


Height: The height of a node is the length of the longest path from that node to a leaf. The height of the tree is the height of the root node.


Level: The level of a node is its depth plus one. The root is at level 1, its children are at level 2, and so on.

Degree: The degree of a node is the number of children it has. A leaf node has a degree of 0.

Binary Trees

A binary tree is a finite set of data item which is either:

 1. empty or 

 2. consists of a single item called root or

 3. nodes have at most two children.

Traversing of a binary tree

Traversing a binary tree involves visiting all the nodes of the tree and performing an operation at each node. 

There are three common methods for traversing a binary tree: 

1. Inorder traversal: 

• Visit the:

• left subtree.
• root node.
• right subtree.
• 

    In the above example : D, B, E, A, C

1. pre-order traversal :

• Visit the:
• root node.
• left subtree.
• right subtree.

    In the above example: A , B, D , E, C

    3.post-order traversal:

•     Visit the:
• left subtree.
• right subtree.
• root node.

In the above example: D, E, B, C, A

                                   

AVL Trees: 

The AVL tree is named after its inventors, Georgy Adelson-Velsky and Evgenii Landis, who introduced it in 1962.

Self-balancing binary search trees to maintain optimal search times.
B-Trees: Balanced trees used in databases and file systems for efficient searching and insertion.

An AVL tree (Adelson-Velsky and Landis tree) is a self-balancing binary search tree. 

In a binary search tree, each node has at most two child nodes: a left child and a right child. 

The key property of an AVL tree is that the heights of the two child subtrees of any node differ by at most one.

Graphs

The graph is a non-linear data structure.

A graph is a collection of vertices and arcs in which vertices are connected with arcs.

Vertex or Node: a data element of a graph

Edge or Arc: an edge is a connecting link between vertices.