Binary search tree

AVL tree 
Red–black tree 

Average

Worst case

Average

Worst case

Average

Worst case


Space

O(n)

O(n)

O(n)

O(n)

O(n)

O(n)

Search

O(log n)

O(n)

O(log n)

O(log n)

O(log n)

O(log n)

Insert

O(log n)

O(n)

O(log n)

O(log n)

O(log n)

O(log n)

Delete

O(log n)

O(n)

O(log n)

O(log n)

O(log n)

O(log n)

Splay tree

BTree

Binary Heap


Average

Worst case

Average

Worst case

Average

Worst case


Space

O(n)

O(n)

O(n)

O(n)

O(n)

O(n)

Search

O(log n)

amortized O(log n)

O(log n)

O(log n)

N/A Operation

N/A Operation

Insert

O(log n)

amortized O(log n)

O(log n)

O(log n)

O(log n)

O(log n)

Delete

O(log n)

amortized O(log n)

O(log n)

O(log n)

O(log n)

O(log n)
