Skip to content

avl_tree.md

Latest commit

 

History

History
125 lines (91 loc) · 4.98 KB

avl_tree.md

File metadata and controls

125 lines (91 loc) · 4.98 KB

The Self-Balancing Bookshelf of Libraria: Unveiling AVL Trees! 📚🌳

Hello, book lovers and organization enthusiasts! Today, we're exploring the magical library of Libraria, where books arrange themselves on a special bookshelf that always stays perfectly balanced. This enchanted bookshelf is our AVL Tree! 🧙‍♂️📖

The Magical Bookshelf of Libraria 📚

Imagine a bookshelf where:

  • Each book is placed carefully to keep the shelf balanced.
  • The shelf automatically rearranges itself to stay balanced when you add or remove books.
  • You can always find any book super quickly!

Key Elements of Our Magical Bookshelf:

  1. Books: Individual items stored in our tree.
  2. Shelves: Nodes that hold books and connect to other shelves.
  3. Balance Factor: The magical measure that tells us if a shelf is balanced.
class Book:
    def __init__(self, title, height):
        self.title = title
        self.height = height
        self.left_shelf = None
        self.right_shelf = None
        self.balance = 0  # Balance factor

class MagicalBookshelf:
    def __init__(self):
        self.root = None

    def height(self, shelf):
        return 0 if not shelf else 1 + max(self.height(shelf.left_shelf), self.height(shelf.right_shelf))

    def update_balance(self, shelf):
        shelf.balance = self.height(shelf.left_shelf) - self.height(shelf.right_shelf)

Keeping Our Bookshelf Balanced 📏

The Golden Rule of Balance

A shelf is considered balanced if its balance factor is -1, 0, or 1. If it's not, we need to rearrange!

Balancing Acts (Rotations)

When a shelf gets out of balance, we perform magical rotations:

  1. Left Rotation: When the right side is too heavy.
  2. Right Rotation: When the left side is too heavy.
  3. Left-Right Rotation: A special two-step dance for tricky imbalances.
  4. Right-Left Rotation: Another two-step move for the opposite tricky case.
def left_rotate(self, z):
    y = z.right_shelf
    T2 = y.left_shelf
    y.left_shelf = z
    z.right_shelf = T2
    z.balance = self.height(z.left_shelf) - self.height(z.right_shelf)
    y.balance = self.height(y.left_shelf) - self.height(y.right_shelf)
    return y

# Similar functions for right_rotate, left_right_rotate, and right_left_rotate

Adding a New Book 📖✨

When we add a new book:

  1. We place it on the shelf like in a normal binary search tree.
  2. Then, we check the balance of each shelf we passed.
  3. If any shelf is unbalanced, we perform the necessary rotation(s).
def add_book(self, title, height):
    def _add(shelf, book):
        if not shelf:
            return book
        if book.height < shelf.height:
            shelf.left_shelf = _add(shelf.left_shelf, book)
        else:
            shelf.right_shelf = _add(shelf.right_shelf, book)
        
        self.update_balance(shelf)
        
        if shelf.balance > 1:
            if book.height < shelf.left_shelf.height:
                return self.right_rotate(shelf)
            return self.left_right_rotate(shelf)
        if shelf.balance < -1:
            if book.height > shelf.right_shelf.height:
                return self.left_rotate(shelf)
            return self.right_left_rotate(shelf)
        
        return shelf

    self.root = _add(self.root, Book(title, height))

The Magic of Our Self-Balancing Bookshelf 🌟

  • Always Balanced: No matter how many books you add or remove, the shelf stays balanced.
  • Quick Book Finding: You can find any book in O(log n) time.
  • Efficient Updates: Adding and removing books is also O(log n).
  • Predictable Performance: Unlike regular BSTs, AVL Trees don't degrade over time.

Real-World Library Tasks Using AVL Trees 🌍

  1. Dictionary Implementation: Quick word lookups and updates.
  2. Database Indexing: Efficient searching in large databases.
  3. File System Organization: Managing files and directories efficiently.
  4. Network Routing Tables: Optimizing path finding in computer networks.

Librarian Challenges 🏆📚

  1. The Book Counter: Implement a function to count the total number of books on the shelf.
  2. The Genre Sorter: Modify the tree to group books by genre while maintaining balance.
  3. The Series Finder: Create a method to find all books in a series quickly.

The Head Librarian's Wisdom 🧠📚

"In the grand library of data structures, the AVL Tree teaches us that balance is not just a goal, but a continuous process. By staying vigilant and making small adjustments, we can maintain order and efficiency no matter how our collection grows or changes." - Sage Balancia, Head Librarian of Libraria

Remember, future master librarians, the AVL Tree is like a magical assistant that ensures your library stays perfectly organized with minimal effort. It's all about making small, smart adjustments to keep everything in harmony!

Are you ready to become the ultimate curator of the Self-Balancing Bookshelf? Your adventure in efficient and balanced data management starts now! 🚀📚🌳