Binary Tree Variants

Binary Tree–Based Data Structures

Type	Description	Key Characteristic	Typical Use Case	Access Pattern	Memory Behavior	Notes
Binary Tree	Each node has ≤ 2 children	Hierarchical structure	Expression trees	Traversal-based	Pointer-based	No ordering
Binary Search Tree	Ordered binary tree	Left < Root < Right	Searching, sorting	Logarithmic (avg)	Pointer-based	Can become skewed
Self-balancing BST	Auto-balanced BST	Height control	Databases, indexes	Logarithmic	Pointer-based	Category, not specific
AVL Tree	Strictly balanced BST	Height difference ≤ 1	Read-heavy systems	Logarithmic	Pointer-based	Frequent rotations
Red-Black Tree	Loosely balanced BST	Color-based rules	Language runtimes	Logarithmic	Pointer-based	Fewer rotations
AA Tree	Simplified red-black tree	Level-based balancing	Ordered maps	Logarithmic	Pointer-based	Easier implementation
Scapegoat Tree	Rebuild-on-imbalance	No rotations	Amortized search	Pointer-based	Rebuilds subtrees
Splay Tree	Self-adjusting BST	Recently used near root	Caches	Amortized log	Pointer-based	No explicit balance
Treap	BST + heap	Randomized priority	Randomized sets	Expected log	Pointer-based	Probabilistic
Zip Tree	Randomized BST	Rank-based balancing	Ordered maps	Expected log	Pointer-based	Simpler treap
WAVL Tree	Weak AVL variant	Relaxed balancing	Databases	Logarithmic	Pointer-based	Fewer rebalances
Weight-balanced Tree	Balanced by subtree weight	Weight constraints	Ordered collections	Logarithmic	Pointer-based	Rebalancing cost
Order Statistic Tree	Augmented BST	Rank queries	Rankings	Logarithmic	Pointer-based	Stores subtree sizes
Cartesian Tree	Heap-ordered tree	Sequence-based	RMQ problems	Traversal-based	Pointer-based	Built from array
Randomized BST	Random insertion order	Expected balance	Sets/maps	Expected log	Pointer-based	Probabilistic
Left-child Right-sibling	Binary encoding of trees	Multi-child support	General trees	Traversal-based	Pointer-based	Tree representation
Threaded Binary Tree	Uses null pointers	Faster traversal	In-order traversal	Traversal-based	Pointer-based	No recursion
T-tree	Balanced BST for memory	Cache optimized	In-memory DBs	Logarithmic	Pointer-based	AVL hybrid
Tango Tree	BST + preferred paths	Dynamic optimality	Theoretical research	Logarithmic	Pointer-based	Complex
Top Tree	Dynamic tree structure	Path queries	Dynamic graphs	Logarithmic	Pointer-based	Advanced use
Pagoda	Heap-like BST	Priority search	Experimental	Logarithmic	Pointer-based	Rarely used
Rope	Tree of strings	Fast concat/split	Text editors	Logarithmic	Tree-based	String structure
Conc-tree List	Tree-based list	Fast concatenation	Functional lists	Indexed	Tree-based	Persistent structure