getMaxBalance method

int getMaxBalance()
override

Get the maximum balance of an node in the tree. The balance is the difference in height of the two children of a node.

Implementation

int getMaxBalance() {
  int maxBalance = 0;
  for (int i = 0; i < _nodeCapacity; ++i) {
    final DynamicTreeNode node = _nodes[i];
    if (node.height <= 1) {
      continue;
    }

    assert((node.child1 == null) == false);

    DynamicTreeNode child1 = node.child1;
    DynamicTreeNode child2 = node.child2;
    int balance = (child2.height - child1.height).abs();
    maxBalance = Math.max(maxBalance, balance);
  }

  return maxBalance;
}