WikiGalaxy
Complete Binary Tree
Definition
A complete binary tree is a type of binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
Characteristics
Complete binary trees are efficient for memory usage and often used in heap implementations. They ensure that the tree is balanced, which helps in maintaining logarithmic height.
Applications
Complete binary trees are used in various applications like binary heaps, which are useful in priority queues and heap sort algorithms.
public class CompleteBinaryTree {
static class Node {
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}
Node root;
public static void main(String[] args) {
CompleteBinaryTree tree = new CompleteBinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
}
}
Building a Complete Binary Tree
To construct a complete binary tree, nodes are added from left to right. The tree is filled level by level, ensuring balance.
Traversal Techniques
Common traversal techniques include in-order, pre-order, and post-order traversals, which can be applied to complete binary trees.
Console Output:
Tree constructed with root: 1
Properties of Complete Binary Trees
Height Calculation
The height of a complete binary tree with n nodes is ⌊log₂n⌋. This ensures efficient operations.
Node Count
A complete binary tree of height h has between 2^h and 2^(h+1)-1 nodes.
public class CompleteBinaryTreeProperties {
static int calculateHeight(int n) {
return (int)Math.floor(Math.log(n) / Math.log(2));
}
public static void main(String[] args) {
int nodeCount = 7;
System.out.println("Height of tree with " + nodeCount + " nodes: " + calculateHeight(nodeCount));
}
}
Level-wise Node Addition
Nodes in a complete binary tree are added from left to right at each level, ensuring the tree remains complete.
Console Output:
Height of tree with 7 nodes: 2
Heap Implementation
Binary Heap
A binary heap is a complete binary tree where each node is greater than or equal to its children (max-heap) or less than or equal to its children (min-heap).
Priority Queue
Binary heaps are used to implement priority queues, where the highest (or lowest) priority element is efficiently extracted.
import java.util.PriorityQueue;
public class HeapExample {
public static void main(String[] args) {
PriorityQueue heap = new PriorityQueue<>();
heap.add(10);
heap.add(20);
heap.add(15);
System.out.println("Min value: " + heap.poll());
}
}
Efficiency
Operations like insert, delete, and extract-min/max are efficient due to the complete binary tree structure.
Console Output:
Min value: 10
Array Representation
Efficient Storage
Complete binary trees can be efficiently represented using arrays, where the parent-child relationship is easily maintained.
Index Calculation
For a node at index i, its left child is at 2*i + 1 and right child is at 2*i + 2. The parent is at (i-1)/2.
public class ArrayRepresentation {
public static void main(String[] args) {
int[] tree = {1, 2, 3, 4, 5};
System.out.println("Root node: " + tree[0]);
System.out.println("Left child of root: " + tree[1]);
}
}
Space Utilization
Using arrays for complete binary trees reduces space overhead associated with pointers or references.
Console Output:
Root node: 1
Left child of root: 2
Balancing Techniques
Maintaining Balance
Inserting or deleting nodes in a complete binary tree requires re-balancing to maintain its properties.
Re-Balancing Algorithms
Algorithms like heapify are used to maintain the heap property after insertions or deletions.
public class RebalanceHeap {
static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
public static void main(String[] args) {
int[] arr = {4, 10, 3, 5, 1};
heapify(arr, arr.length, 0);
System.out.println("Root after heapify: " + arr[0]);
}
}
Efficiency
Re-balancing ensures that operations on the complete binary tree remain efficient, maintaining O(log n) complexity.
Console Output:
Root after heapify: 10
