Class AVLTree<T>

AVLTree is a self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one. It maintains O(log n) time complexity for insert, delete, and search operations through automatic rebalancing.

Example

const avlTree = new AVLTree<number>((a, b) => a - b);
avlTree.insert(10);
avlTree.insert(20);
avlTree.insert(5);
avlTree.contains(10); // true
avlTree.delete(10);
avlTree.contains(10); // false

Type Parameters

  • T

Hierarchy

  • AVLTree

Constructors

constructor

Properties

comparator nodeCount root

Methods

balance clear contains delete deleteNode findMin getBalance getHeight getTreeHeight inorderHelper inorderTraversal insert insertNode isEmpty max min postorderHelper postorderTraversal preorderHelper preorderTraversal rotateLeft rotateRight search size updateHeight

Constructors

constructor

  • Creates a new AVL Tree with the specified comparator function.

    Type Parameters

    • T

    Parameters

    • comparator: ((a, b) => number)

      Function to compare two values. Should return: - negative number if a < b - zero if a === b - positive number if a > b

        • (a, b): number

        • Parameters

          • a: T
          • b: T

          Returns number

    Returns AVLTree<T>

Properties

Private Readonly comparator

comparator: ((a, b) => number)

Type declaration

    • (a, b): number

    • Parameters

      • a: T
      • b: T

      Returns number

Private nodeCount

nodeCount: number = 0

Private root

root: null | AVLNode<T> = null

Methods

Private balance

  • Balances a node if necessary based on its balance factor.

    Parameters

    • node: AVLNode<T>

      The node to balance

    Returns AVLNode<T>

    The balanced node (may be a different node after rotation)

clear

contains

  • Searches for a value in the tree.

    Parameters

    • value: T

      The value to search for

    Returns boolean

    true if the value exists, false otherwise

delete

  • Deletes a value from the AVL tree.

    Parameters

    • value: T

      The value to delete

    Returns boolean

    true if the value was found and deleted, false otherwise

Private deleteNode

  • Internal method to delete a node recursively.

    Parameters

    • node: null | AVLNode<T>

      The current node

    • value: T

      The value to delete

    Returns null | AVLNode<T>

    The new root of this subtree

Private findMin

  • Finds the node with the minimum value in a subtree.

    Parameters

    • node: AVLNode<T>

      The root of the subtree

    Returns AVLNode<T>

    The node with minimum value

Private getBalance

  • Returns the balance factor of a node (height of left subtree - height of right subtree).

    Parameters

    • node: null | AVLNode<T>

      The node to get balance factor from

    Returns number

    The balance factor

Private getHeight

  • Returns the height of a node. Null nodes have height 0.

    Parameters

    • node: null | AVLNode<T>

      The node to get height from

    Returns number

    The height of the node

getTreeHeight

Private inorderHelper

  • Helper method for inorder traversal.

    Parameters

    • node: null | AVLNode<T>

      The current node

    • result: T[]

      The array to store values

    Returns void

inorderTraversal

  • Performs an inorder traversal of the tree (left, root, right).

    Returns T[]

    An array of values in inorder sequence

insert

  • Inserts a value into the AVL tree.

    Parameters

    • value: T

      The value to insert

    Returns void

Private insertNode

  • Internal method to insert a node recursively.

    Parameters

    • node: null | AVLNode<T>

      The current node

    • value: T

      The value to insert

    Returns AVLNode<T>

    The new root of this subtree

isEmpty

  • Checks if the tree is empty.

    Returns boolean

    true if the tree has no nodes, false otherwise

max

  • Finds the maximum value in the tree.

    Returns null | T

    The maximum value, or null if tree is empty

min

  • Finds the minimum value in the tree.

    Returns null | T

    The minimum value, or null if tree is empty

Private postorderHelper

  • Helper method for postorder traversal.

    Parameters

    • node: null | AVLNode<T>

      The current node

    • result: T[]

      The array to store values

    Returns void

postorderTraversal

  • Performs a postorder traversal of the tree (left, right, root).

    Returns T[]

    An array of values in postorder sequence

Private preorderHelper

  • Helper method for preorder traversal.

    Parameters

    • node: null | AVLNode<T>

      The current node

    • result: T[]

      The array to store values

    Returns void

preorderTraversal

  • Performs a preorder traversal of the tree (root, left, right).

    Returns T[]

    An array of values in preorder sequence

Private rotateLeft

  • Performs a left rotation on the given node.

    Parameters

    • x: AVLNode<T>

      The node to rotate

    Returns AVLNode<T>

    The new root after rotation

Private rotateRight

  • Performs a right rotation on the given node.

    Parameters

    • y: AVLNode<T>

      The node to rotate

    Returns AVLNode<T>

    The new root after rotation

Private search

  • Internal method to search for a value recursively.

    Parameters

    • node: null | AVLNode<T>

      The current node

    • value: T

      The value to search for

    Returns null | AVLNode<T>

    The node containing the value, or null if not found

size

Private updateHeight

  • Updates the height of a node based on its children's heights.

    Parameters

    • node: AVLNode<T>

      The node to update height for

    Returns void

Settings

Member Visibility

Theme

On This Page

Generated using TypeDoc