AlgoFlow — Algorithms, Visualized

treebalancedmultiway

Press play to start

1void btree_insert(BTree* t, int val) {
  if (t->root->num_keys == MAX_KEYS) {
      BNode* s = new_node();
      s->children[0] = t->root;
      split_child(s, 0); t->root = s;
  }
  BNode* curr = t->root;
  while (!curr->is_leaf) {
      int i = find_index(curr, val);
      if (curr->children[i]->num_keys == MAX_KEYS)
          { split_child(curr, i); if (val > curr->keys[i]) i++; }
      curr = curr->children[i];
  }
  insert_key(curr, val);
15}

Step 1/0

Practice

LeetCode·#700 Search in a BSTEasy LeetCode·#938 Range Sum of BSTEasy

Operation	Best	Average	Worst
search	O(log n)	O(log n)	O(log n)
insert	O(log n)	O(log n)	O(log n)

SpaceO(n)