insert method

void insert(Interval<T> interval)

Inserts a single interval.

Implementation

void insert(Interval<T> interval) {
  if (root == null) {
    root = IntervalNode<T>(interval);
    return;
  }

  // 1. Iterative Downward Path
  final path = <IntervalNode<T>>[];
  IntervalNode<T>? current = root;

  while (current != null) {
    path.add(current);
    if (interval.start.compareTo(current.interval.start) < 0) {
      if (current.left == null) {
        current.left = IntervalNode<T>(interval);
        break;
      }
      current = current.left;
    } else {
      if (current.right == null) {
        current.right = IntervalNode<T>(interval);
        break;
      }
      current = current.right;
    }
  }

  // 2. Backtrack & Balance
  for (int i = path.length - 1; i >= 0; i--) {
    final node = path[i];
    node.update();

    final balance = _getBalance(node);
    IntervalNode<T>? newSubtreeRoot;

    if (balance > 1) {
      final leftChild = node.left!;
      if (_getBalance(leftChild) >= 0) {
        newSubtreeRoot = _rotateRight(node);
      } else {
        node.left = _rotateLeft(leftChild);
        newSubtreeRoot = _rotateRight(node);
      }
    } else if (balance < -1) {
      final rightChild = node.right!;
      if (_getBalance(rightChild) <= 0) {
        newSubtreeRoot = _rotateLeft(node);
      } else {
        node.right = _rotateRight(rightChild);
        newSubtreeRoot = _rotateLeft(node);
      }
    }

    if (newSubtreeRoot != null) {
      if (i == 0) {
        root = newSubtreeRoot;
      } else {
        final parent = path[i - 1];
        if (parent.left == node) {
          parent.left = newSubtreeRoot;
        } else {
          parent.right = newSubtreeRoot;
        }
      }
    }
  }
}