add method

Implementation

bool add(V element) {
  if (_root == null) {
    AvlNode<V> node = new AvlNode<V>(object: element);
    _root = node;
    ++_length;
    ++_modCount;
    return true;
  }

  AvlNode<V> x = _root;
  while (true) {
    int compare = comparator(element, x.object);
    if (compare == 0) {
      return false;
    } else if (compare < 0) {
      if (x._left == null) {
        AvlNode<V> node = new AvlNode<V>(object: element).._parent = x;
        x
          .._left = node
          .._balanceFactor -= 1;
        break;
      }
      x = x.left;
    } else {
      if (x._right == null) {
        AvlNode<V> node = new AvlNode<V>(object: element).._parent = x;
        x
          .._right = node
          .._balanceFactor += 1;
        break;
      }
      x = x.right;
    }
  }

  ++_modCount;

  // AVL balancing act (for height balanced trees)
  // Now that we've inserted, we've unbalanced some trees, we need
  //  to follow the tree back up to the _root double checking that the tree
  //  is still balanced and _maybe_ perform a single or double rotation.
  //  Note: Left additions == -1, Right additions == +1
  //  Balanced Node = { -1, 0, 1 }, out of balance = { -2, 2 }
  //  Single rotation when Parent & Child share signed balance,
  //  Double rotation when sign differs!
  AvlNode<V> node = x;
  while (node._balanceFactor != 0 && node.parent != null) {
    // Find out which side of the parent we're on
    if (node.parent._left == node) {
      node.parent._balanceFactor -= 1;
    } else {
      node.parent._balanceFactor += 1;
    }

    node = node.parent;
    if (node._balanceFactor == 2) {
      // Heavy on the right side - Test for which rotation to perform
      if (node.right._balanceFactor == 1) {
        // Single (left) rotation; this will balance everything to zero
        _rotateLeft(node);
        node._balanceFactor = node.parent._balanceFactor = 0;
        node = node.parent;
      } else {
        // Double (Right/Left) rotation
        // node will now be old node.right.left
        _rotateRightLeft(node);
        node = node.parent; // Update to new parent (old grandchild)
        if (node._balanceFactor == 1) {
          node.right._balanceFactor = 0;
          node.left._balanceFactor = -1;
        } else if (node._balanceFactor == 0) {
          node.right._balanceFactor = 0;
          node.left._balanceFactor = 0;
        } else {
          node.right._balanceFactor = 1;
          node.left._balanceFactor = 0;
        }
        node._balanceFactor = 0;
      }
      break; // out of loop, we're balanced
    } else if (node._balanceFactor == -2) {
      // Heavy on the left side - Test for which rotation to perform
      if (node.left._balanceFactor == -1) {
        _rotateRight(node);
        node._balanceFactor = node.parent._balanceFactor = 0;
        node = node.parent;
      } else {
        // Double (Left/Right) rotation
        // node will now be old node.left.right
        _rotateLeftRight(node);
        node = node.parent;
        if (node._balanceFactor == -1) {
          node.right._balanceFactor = 1;
          node.left._balanceFactor = 0;
        } else if (node._balanceFactor == 0) {
          node.right._balanceFactor = 0;
          node.left._balanceFactor = 0;
        } else {
          node.right._balanceFactor = 0;
          node.left._balanceFactor = -1;
        }
        node._balanceFactor = 0;
      }
      break; // out of loop, we're balanced
    }
  } // end of while (balancing)
  _length++;
  return true;
}