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
Binary trees Representation
Binary trees can be represented in computer memory in mainly two ways:
- Array Representation
- Linked List Representation.
1. Array Representation
In the array representation of a binary tree, the tree elements are stored in an array, and the parent-child relationship is maintained through the indices of the array.
Indexing Rules
- If the root node is stored at index 0, then for any node stored at index i, its left child is stored at index 2i + 1 and its right child at index 2i + 2.
- Conversely, the parent of a node at index i can be found at index floor((i-1)/2).
Characteristics
- Space Efficiency: For complete or nearly complete binary trees, array representation is space-efficient. However, for sparse trees, it can waste a lot of space due to the empty slots in the array.
- Performance: Accessing nodes, as well as their children and parents, is fast because it involves simple arithmetic operations on indices.
- Limitations: The size of the tree is fixed and needs to be known in advance, or resizing the array might be required, which is a costly operation.
Use Cases: This representation is often used in implementations of binary heaps, where the tree is mostly complete and the array-based approach is space-efficient and fast.
2. Linked List Representation
In the linked list representation, each node of the tree is represented as an object with typically three attributes: the data part, a pointer/reference to the left child, and a pointer/reference to the right child.
Node Structure
- Each node contains the element and two pointers or references, one for each child.
- The pointers are set to null (or a similar sentinel value) for leaf nodes for their non-existing children.
Characteristics
- Space Efficiency: This method is more space-efficient for sparse trees, as it allocates memory only for existing nodes.
- Dynamic Size: The tree can grow or shrink dynamically, allowing for more flexibility in operations like addition or deletion of nodes.
- Performance: Accessing children or parent nodes requires following pointers, which might be slightly slower than direct index-based access in arrays.
- Overhead: Each node requires extra memory for the pointers, in addition to the data it stores.
Use Cases: The linked list representation is the more common and general-purpose approach, especially when the tree is dynamic, or its shape cannot be predicted or is highly variable.
Next Topic :Binary tree traversals