Tree Data Structures – Comparison Table
Tree Type Definition / Ordering Usage / Time Complexity
Structure Property Application (Search/Insert/Delete)
Binary Each node has No strict General O(n) (not balanced)
Tree at most 2 order hierarchical data
children
Full Every node No strict Special cases in O(n)
Binary has 0 or 2 order memory &
Tree children parsing
Complete All levels No strict Heap O(n)
Binary filled except order implementation
Tree possibly last
(filled left to
right)
Perfect All internal Symmetric Ideal cases in O(log n) height
Binary nodes have 2 structure analysis
Tree children, all
leaves at same
level
Binary Left child < Ordered by Searching, Avg O(log n), Worst
Search parent < right keys dynamic sets O(n)
Tree child
(BST)
AVL Tree Self-balancing Keys Faster search, O(log n)
BST (height- ordered balanced
balanced) structure
Red-Black Self-balancing Keys Used in maps, O(log n)
Tree BST with ordered sets (C++, Java,
color property Linux kernel)
B-Tree Multi-way Keys sorted Database, disk O(log n)
search tree in nodes storage indexing
(nodes can
have >2
children)
B+ Tree Variant of B- Linked leaf Databases, file O(log n)
Tree, all data nodes for systems
1
stored in range
leaves queries
Heap Complete Parent ≥/≤ Priority queues, Insert/Delete O(log n),
(Binary binary tree children scheduling Find min/max O(1)
Heap) with heap
property
(min/max)
Trie Each edge Ordered by Autocomplete, O(m) where m = length
(Prefix represents prefix dictionary of string
Tree) character in matching
string
Segment Binary tree Ordered by Range queries O(log n) per
Tree storing range segments (sum, min, max) query/update
information
Suffix Tree Stores all Ordered by Pattern matching, O(n) build, O(m) query
suffixes of a suffixes string algorithms
string
Sorting Algorithms – Comparison Table
Algorithm Type Best Avg Worst Stability Extra Use Case
Case Case Case Space
Bubble Comparison O(n) O(n²) O(n²) Stable O(1) Teaching
Sort basics, small
datasets
Selection Comparison O(n²) O(n²) O(n²) Not O(1) Simple but
Sort Stable inefficient
Insertion Comparison O(n) O(n²) O(n²) Stable O(1) Nearly sorted
Sort data, small
datasets
Merge Divide & O(n O(n log O(n Stable O(n) External
Sort Conq log n) n) log n) sorting, linked
lists
Quick Divide & O(n O(n log O(n²) Not O(log General-
Sort Conq log n) n) Stable n) purpose, fast
in practice
2
Heap Sort Comparison O(n O(n log O(n Not O(1) Priority-based
log n) n) log n) Stable tasks, large
datasets
Counting Non- O(n+k) O(n+k) O(n+k) Stable O(k) Small integer
Sort compare ranges
Radix Non- O(nk) O(nk) O(nk) Stable O(n+k) Sorting
Sort compare integers,
strings
Bucket Non- O(n+k) O(n+k) O(n²) Stable O(n+k) Uniformly
Sort compare distributed
floating
values
Shell Sort Comparison O(n O(n^1.5) O(n²) Not O(1) Improves
log n) Stable insertion sort
with gaps
Tim Sort Hybrid O(n) O(n log O(n Stable O(n) Used in
n) log n) Python
(sort()) &
Java
(Arrays.sort())
