Data Structures - Introduction
- Abstract data types
- Linear Data Structures
- Linked List Introduction
- Single Linked List
- Stacks using Array
- Stacks using linkedlist
- Queues using array
- Queues using linkedlist
- Stack Applications
- Infix to Postfic Converstion
- Postfix Evaluation
- Dictionaries
- Introduction to Dictionaries
- Linear list representation
- Skip list representation
- Hash Table
- Introduction Hash Table
- Hash functions
- Collision Resolution
- Separate chaining
- Open addressing
- Rehashing
- Extendible hashing
- Trees
- Introduction to Tree
- Binary trees Representation
- Binary tree traversals
- Binary Search Tree
- AVL Tree
- Red Black Tree
- Splay Tree
- B Tree
- B+ Tree
- Comparison of Trees
- Graphs
- Introduction to Graph
- Graph Representation
- Breadth-First Search
- Depth-First Search
- Sorting
- Quick Sort
- Merge Sort
- Heap Sort
- Pattern Matching
- Introduction to pattern Matching
- Brute force Pattern Matching
- Boyer–Moore Pattern Matching
- KMP Pattern Matching
- Tries
- Introduction to Tries
- Standard Trie
- Compressed tries
- Suffix Trie
Introduction to Tree
A tree data structure is a nonlinear hierarchical data structure that consists of nodes connected by edges. The topmost node of the tree is called the root, and the nodes below it are called the child nodes. Each node can have multiple child nodes, and these child nodes can also have their own child nodes, forming a recursive structure.
DefinitionA tree is a finite set of one or more nodes such that, there is a specially designated node called root. The remaining nodes are partitioned into n>=0 disjoint sets T1, T2,..Tn, where each of these set is a tree T1,...Tn are called the subtrees of the root.
Basic Tree Terminologies
- Node: The basic unit of a tree. Each node can contain data and have links (edges) to other nodes.
- Root: The topmost node of a tree, from which all other nodes descend. It does not have a parent.
- Parent Node: A node that has one or more child nodes.
- Child Node: A node that is a descendant of another node.
- Leaf Node (Terminal Node): A node that does not have any children.
- Siblings: Nodes that share the same parent are called siblings.
- Internal Node: A node that has at least one child (i.e., it is not a leaf).
- Edge: The link between two nodes.
- Path: A sequence of nodes and edges connecting a node with a descendant.
- Level: The level of a node is defined by 1 + the number of connections between the node and the root. The root is at level 1.
- Height of a Node: The height of a node is the number of edges on the longest path from the node to a leaf. The height of a tree is the height of its root.
- Depth of a Node: The number of edges from the root to the node.
- Degree of a Node: The number of children a node has.
Types of Trees data structures
- General Trees
- Binary Trees
- Binary Search Trees
General Trees
General trees are unordered tree data structures where the root node has minimum 0 or maximum ‘n’ subtrees. The General trees have no constraint placed on their hierarchy. The root node thus acts like the superset of all the other subtrees.
Binary Tree
A tree where each node has at most two children, often referred to as the left and right children.
DefinitionA binary tree is a finite set of nodes that either is empty or consists of a root and two disjoint binary trees called the left subtree and right subtree.
- Full Binary Tree: A full binary tree is a binary tree type where every node has either 0 or 2 child nodes.
- Complete Binary Tree:If all the nodes of a binary tree consist of two nodes each and the nodes at the last level does not consist any nodes, then that type of binary tree is called a complete binary tree.
- Perfect Binary Tree: A perfect binary tree is a binary tree type where all the leaf nodes are on the same level and every node except leaf nodes have 2 children.
- Strictly binary tree: If the binary tree has each node consisting of either two nodes or no nodes at all, then it is called a strictly binary tree.
- Skewed Binary tree: If the new nodes in the tree are added only to one side of the binary tree then it is a skewed binary tree.
Binary Search Tree
A binary tree in which each node has a value greater than all values in its left subtree and less than all values in its right subtree. i.e. left subtree < root node ≤ right subtree.
DefinitionA Binary tree T is a Binary Search Tree (BST), if each node N of T has the following property : The value at N is greater than every value in the left subtree of N and is less than every value in the right subtree of N.
Balanced Binary Search Trees (BSTs)
BSTs are an enhancement over standard binary search trees. They incorporate mechanisms to maintain balance, ensuring the tree remains efficient for operations like search, insertion, and deletion. The term "balanced" in this context refers to ensuring that the tree's height (the longest path from the root node to a leaf node) is kept as small as possible.
Types of balanced BSTs
- AVL Trees (Adelson-Velsky and Landis Trees)
- Red-Black Trees
- B Trees
- B+ Trees
- Splay Trees
Basic Operation Of Tree Data Structure
- Create – create a tree in the data structure.
- Insert − Inserts data in a tree.
- Search − Searches specific data in a tree to check whether it is present or not.
-
- Traversal:
- Preorder Traversal – perform Traveling a tree in a pre-order manner in the data structure.
- In order Traversal – perform Traveling a tree in an in-order manner.
- Post-order Traversal –perform Traveling a tree in a post-order manner.
Next Topic :Binary trees Representation