Implement an AVL Tree in JavaScript

This challenge requires you to build a self-balancing binary search tree known as an AVL tree in JavaScript. AVL trees are crucial for efficient data storage and retrieval, guaranteeing logarithmic time complexity for insertion, deletion, and search operations, which is vital for performance-sensitive applications.

Problem Description

Your task is to implement an AVL tree data structure in JavaScript. An AVL tree is a binary search tree with an additional property: for every node, the height difference between its left and right subtrees (the "balance factor") must be no more than 1. To maintain this property, you'll need to implement insertion and deletion operations that include rotations (left, right, left-right, right-left) to rebalance the tree when it becomes unbalanced.

Key Requirements:

• Node Structure: Each node in the tree should store a key, a value (optional, can be the same as the key), left child, right child, and height.
• Insertion (insert(key, value)): Implement a method to insert a new node with a given key-value pair. After insertion, the tree must be rebalanced if necessary.
• Deletion (delete(key)): Implement a method to delete a node with a given key. After deletion, the tree must be rebalanced if necessary.
• Search (search(key)): Implement a method to find and return the value associated with a given key.
• Height Calculation: Each node must correctly track its height.
• Balance Factor Calculation: A helper function to calculate the balance factor of a node is required.
• Rotations: Implement all four rotation types:
  • Left Rotation
  • Right Rotation
  • Left-Right Rotation
  • Right-Left Rotation
• Rebalancing Logic: Integrate rotations into insert and delete operations to ensure the AVL property is maintained.

Expected Behavior:

• The tree should always remain a valid binary search tree.
• The height difference between the left and right subtrees of any node should never exceed 1.
• search operations should return the correct value or null/undefined if the key is not found.
• Insertion and deletion should handle duplicate keys appropriately (e.g., overwrite existing value or ignore). For this challenge, assume overwriting is the desired behavior for duplicate keys during insertion.

Edge Cases to Consider:

• Inserting into an empty tree.
• Deleting from an empty tree.
• Deleting the root node.
• Deleting a leaf node.
• Deleting a node with one child.
• Deleting a node with two children.
• Scenarios that trigger each of the four rotation types.
• Keys with different data types (if applicable, though typically keys are comparable types like numbers or strings). For this challenge, assume keys are comparable numbers.

Examples

Example 1: Inserting a sequence of numbers.

Input: Insert keys: 10, 20, 30, 40, 50, 25
Output: A string representation of the AVL tree structure (e.g., In-order traversal or a visual representation). For simplicity, let's define a `toString` method that performs an in-order traversal.
Output (In-order Traversal): "10, 20, 25, 30, 40, 50"

Explanation:
1. Insert 10: Tree is [10]
2. Insert 20: Tree is [10, 20]
3. Insert 30: Tree becomes unbalanced at 10. A left rotation around 10 occurs. Tree: [20, 10, 30]
4. Insert 40: Tree is [20, 10, 30, 40]
5. Insert 50: Tree becomes unbalanced at 20. A left rotation around 20 occurs. Tree: [30, 20, 10, 40, 50]
6. Insert 25: Tree becomes unbalanced at 20 (height difference at 20 is 2: left subtree height is 1 (node 10), right subtree height is 2 (nodes 40, 50)). This triggers a right-left rotation.
   - Right rotation around 20: Tree becomes [30, 40, 20, 10, 50, 25] (temporarily unbalanced, right subtree of 30 is larger)
   - Left rotation around 30: Tree becomes [25, 20, 10, 30, 40, 50] (balanced)
   The in-order traversal remains: 10, 20, 25, 30, 40, 50.

Example 2: Deleting from a balanced tree.

Input:
AVL Tree initially built with: [10, 20, 30, 40, 50, 25]
Delete key: 10

Output (In-order Traversal): "20, 25, 30, 40, 50"

Explanation:
The tree is initially:
      25
     /  \
    20   40
   /    /  \
  10   30   50

Deleting 10 (a leaf node) is straightforward. The tree remains balanced.
      25
     /  \
    20   40
        /  \
       30   50
In-order traversal: 20, 25, 30, 40, 50.

Example 3: Deletion triggering rebalancing.

Input:
AVL Tree initially built with: [10, 20, 30]
Delete key: 30

Output (In-order Traversal): "10, 20"

Explanation:
Initial balanced tree after inserting 10, 20, 30 (triggers left rotation at 10):
      20
     /  \
    10   30

Deleting 30 (a leaf node).
      20
     /
    10

The tree is still balanced. In-order traversal: 10, 20.

Constraints

• The number of nodes in the tree can range from 0 to 10,000.
• Keys will be integers.
• Values can be any JavaScript type.
• Your implementation should aim for an average and worst-case time complexity of O(log N) for insertion, deletion, and search operations, where N is the number of nodes in the tree. This is the defining characteristic of an AVL tree.

Notes

• You'll likely want to create a Node class or constructor function to represent individual tree nodes.
• The height of a null node is typically considered -1 or 0, depending on your convention. Be consistent. Using -1 for null nodes simplifies height calculations.
• When implementing rotations, ensure you correctly update parent pointers (if you use them, though not strictly necessary if the recursive approach is used) and node heights after the rotation.
• A common approach for AVL tree implementation is to use recursion for insert and delete operations, returning the new root of the subtree after modifications and rebalancing.
• Consider implementing a getHeight(node) helper function that safely returns the height of a node (handling null nodes).
• Think carefully about the order of operations during rotations to avoid losing track of nodes.