Implementing an AVL Tree in JavaScript

AVL trees are self-balancing binary search trees that maintain a balanced structure to ensure efficient search, insertion, and deletion operations. This challenge asks you to implement an AVL tree data structure in JavaScript, focusing on the core functionalities of insertion, deletion, and balancing. A well-implemented AVL tree provides logarithmic time complexity for these operations, making it a valuable data structure for applications requiring fast lookups and updates.

Problem Description

You are tasked with creating an AVL tree class in JavaScript. The class should support the following operations:

• insert(key, value): Inserts a new node with the given key and value into the tree. The tree should maintain its AVL property (balance factor between -1 and 1 for every node) after insertion.
• delete(key): Deletes the node with the given key from the tree. The tree should maintain its AVL property after deletion.
• search(key): Searches for a node with the given key and returns its value if found. Returns undefined if the key is not found.
• height(): Returns the height of the tree (root node's height).
• getBalanceFactor(node): (Helper function - you can use this) Returns the balance factor of a given node (height of left subtree - height of right subtree).
• rotateLeft(node): (Helper function - you can use this) Performs a left rotation on the given node.
• rotateRight(node): (Helper function - you can use this) Performs a right rotation on the given node.

Key Requirements:

• The tree must be a binary search tree (BST).
• The tree must be self-balancing, maintaining the AVL property.
• The implementation should be efficient, aiming for logarithmic time complexity for all operations.
• Handle edge cases gracefully (e.g., empty tree, key not found, duplicate keys - consider how you want to handle duplicates).

Expected Behavior:

• Insertion should maintain the BST property and AVL balance.
• Deletion should maintain the BST property and AVL balance. Consider the different cases for deletion (leaf node, node with one child, node with two children).
• Search should return the correct value or undefined.
• Height should return the correct height of the tree.

Edge Cases to Consider:

• Empty tree: Handle insertion, deletion, and search on an empty tree.
• Duplicate keys: Decide how to handle duplicate keys (e.g., overwrite the value, ignore the insertion, store multiple values in a list). Document your choice.
• Deletion of the root node: Handle the case where the root node needs to be deleted.
• Deletion of nodes with one or two children: Implement the appropriate deletion logic for these cases.

Examples

Example 1:

Input:
  - insert(10, "A")
  - insert(20, "B")
  - insert(30, "C")
Output:
  - search(20) returns "B"
  - height() returns 1

Explanation: The tree is initially unbalanced. Insertion of 30 triggers a left rotation at node 10, balancing the tree.

Example 2:

Input:
  - insert(10, "A")
  - insert(5, "B")
  - insert(15, "C")
  - delete(10)
Output:
  - search(15) returns "C"
  - height() returns 1

Explanation: Deletion of the root (10) requires rebalancing.

Example 3: (Edge Case - Empty Tree)

Input:
  - new AVLTree()
  - search(5)
Output:
  - undefined
Explanation: The tree is empty, so searching for any key returns undefined.

Constraints

• Key Type: Keys must be numbers.
• Value Type: Values can be any JavaScript data type.
• Tree Size: The tree can contain up to 1000 nodes.
• Time Complexity: Insertion, deletion, and search operations should have an average time complexity of O(log n), where n is the number of nodes in the tree.
• Space Complexity: The space complexity should be O(n).

Notes

• You can use helper functions to simplify the implementation (e.g., getBalanceFactor, rotateLeft, rotateRight, updateHeight).
• Consider using recursion for tree traversal and balancing operations.
• Pay close attention to the AVL balancing conditions and ensure that rotations are performed correctly to maintain the balance factor within the range of -1 to 1.
• Document your assumptions about how duplicate keys are handled.
• Focus on code clarity and readability. Use meaningful variable names and comments to explain your logic.
• The updateHeight function should be called after any insertion or deletion to ensure the height of each node is correct. This is crucial for maintaining the AVL property.