Advanced Data Structures

What You’ll Learn 📚

• Core concepts of advanced data structures
• Key terminology and definitions
• Simple to complex examples with explanations
• Common questions and troubleshooting tips

Introduction to Advanced Data Structures

Data structures are ways of organizing and storing data so that they can be accessed and worked with efficiently. Advanced data structures build on basic ones like arrays and linked lists to solve more complex problems. They are crucial for optimizing algorithms and improving performance.

Core Concepts

Let’s break down some core concepts:

• Trees: A hierarchical structure with a root value and subtrees of children, represented as a set of linked nodes.
• Graphs: A set of nodes connected by edges, used to represent pairwise relationships.
• Hash Tables: A data structure that maps keys to values for efficient data retrieval.

Key Terminology

• Node: Basic unit of a data structure, such as a tree or graph.
• Edge: Connection between two nodes in a graph.
• Root: The top node in a tree.
• Leaf: A node with no children in a tree.

Simple Example: Binary Tree 🌳

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

# Create root
root = Node(1)
# Add nodes
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)

Progressively Complex Examples

Example 1: Binary Search Tree (BST)

class BSTNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

    def insert(self, key):
        if self.val:
            if key < self.val:
                if self.left is None:
                    self.left = BSTNode(key)
                else:
                    self.left.insert(key)
            elif key > self.val:
                if self.right is None:
                    self.right = BSTNode(key)
                else:
                    self.right.insert(key)
        else:
            self.val = key

# Create root
root = BSTNode(10)
# Insert elements
root.insert(6)
root.insert(14)
root.insert(3)

Example 2: Graph Representation

class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v):
        if u in self.graph:
            self.graph[u].append(v)
        else:
            self.graph[u] = [v]

# Create a graph
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)

Example 3: Hash Table

class HashTable:
    def __init__(self):
        self.table = [None] * 10

    def hash_function(self, key):
        return key % len(self.table)

    def insert(self, key, value):
        index = self.hash_function(key)
        self.table[index] = value

# Create a hash table
h = HashTable()
h.insert(10, 'Value1')
h.insert(20, 'Value2')

Common Questions and Answers

1. What is the difference between a tree and a graph?

   Trees are a type of graph with no cycles, a single root, and a hierarchical structure. Graphs can have cycles and multiple connections between nodes.

2. Why use a binary search tree?

   Binary search trees allow for efficient searching, insertion, and deletion, making them ideal for dynamic datasets.

3. How do hash tables handle collisions?

   Collisions are handled using techniques like chaining (linked lists) or open addressing (finding another open slot).

4. What is the time complexity of searching in a binary search tree?

   On average, the time complexity is O(log n), but it can degrade to O(n) if the tree becomes unbalanced.

Troubleshooting Common Issues

If your binary search tree operations are slow, check if the tree is balanced. An unbalanced tree can degrade performance.

For hash tables, ensure your hash function distributes keys uniformly to minimize collisions.

Practice Exercises

1. Create a binary tree and implement a function to traverse it in-order.
2. Implement a graph using an adjacency matrix and perform a depth-first search.
3. Design a hash table with a custom hash function and handle collisions using chaining.

Remember, practice makes perfect! Keep experimenting with these data structures to deepen your understanding. Happy coding! 😊