4. Complete Binary Trees #

Created Friday 14 February 2020

• CBT is always balanced. So one overhead of BST is resolved.
• The CBT is stored in an array, i.e heap is a virtual tree. Consequently, children can be reached like so:
  • leftChild is at 2*i+1
  • rightChild is at 2*i+2

Proof - why 2i+1, 2i+2 Suppose that we are a node, now:

• Number of nodes before this node = i in array and 2^h-1^-1 in the tree
• Number of nodes in this level = 2^h-1^ in tree
• index of Left child of the node = number of nodes before it = before + this_level = 2^h-1^-1 + 2^h-1^=2*i+1 ; because i = 2^h-1^-1;
• Similarly, right child = left child+1 = 2*i+2

Using induction, Base step: For the root, left = 20+1 = 1; right = 20+2 = 2. Hypothesis step: This is true for any node: left = 2i+1, right = 2i+2 Inductive step: For the second node, we have left = 2i+2+1 = 2(i+1)+1, right = left +1 = 2*(i+1)+2 And so on for all, until we reach the first of another level.

Proved by induction.

We now know how to calculate indices for the left and right child. We also need a way to know the parent, because this is used in deletion, the formula is simple. p = (c - 1)//2 Note: We are truncating decimals here, which is the norm in C++.

We store data in an array for fast accesses, i.e O(1) access as well as fast insert and update.