Implement Fibonacci generator, balanced BST, frozenset

You are coding in Python. Implement the following three tasks. Unless explicitly allowed, do not use Python built-in container types (list, dict, set, tuple) or library data structures to store your core data; instead use your own node/linked structures and primitive fields (e.g., int, bool, references).

1) Fibonacci generator

Implement a generator function:

def fib():
    """Yield the infinite Fibonacci sequence: 0, 1, 1, 2, 3, 5, ..."""
    ...

Requirements:

• Must be a generator (use yield ).
• Must run in O(1) extra space.

2) Balanced binary search tree (BST) without built-in data structures

Implement a self-balancing BST (e.g., AVL or Red-Black) to store integers.

Define an API similar to:

class BalancedBST:
    def insert(self, x: int) -> None: ...
    def remove(self, x: int) -> None: ...  # no-op if not present
    def contains(self, x: int) -> bool: ...
    def min(self) -> int | None: ...
    def max(self) -> int | None: ...

Requirements:

• insert , remove , contains should be O(log n) worst-case.
• You must maintain balance via rotations and any metadata needed (height / color, etc.).
• You may implement your own Node class.

3) Implement an immutable set ("frozenset")

Implement an immutable, hashable set type supporting at least:

class FrozenSet:
    def __init__(self, iterable=None): ...
    def __contains__(self, x) -> bool: ...
    def __len__(self) -> int: ...
    def __iter__(self): ...
    def __hash__(self) -> int: ...
    def union(self, other: "FrozenSet") -> "FrozenSet": ...
    def intersection(self, other: "FrozenSet") -> "FrozenSet": ...

Requirements:

• Instances are immutable after construction.
• Equal sets must have equal hashes.
• union / intersection must return new FrozenSet instances.

Clarify any assumptions you need (e.g., whether elements must be hashable, how to handle duplicates in input, and expected behavior for empty sets).