Containers-AVL-Tree

A self-balancing AVL Tree implementation providing guaranteed O(log n) performance for all operations. Features automatic rebalancing, range queries, and full Collection protocol compliance.

What is an AVL Tree?

An AVL Tree is a self-balancing binary search tree where the height difference between left and right subtrees of any node is at most 1. This guarantees O(log n) worst-case performance for all operations, unlike regular BSTs which can degrade to O(n).

To install Container-AVL, go to the Playground (Ctrl+OW) in your Pharo image and execute the following Metacello script (select it and press Do-it button or Ctrl+D):

Metacello new
  baseline: 'ContainersAVLTree';
  repository: 'github://pharo-containers/Container-AVL/src';
  load

How to depend on it

spec 
   baseline: 'ContainersAVLTree' 
   with: [ spec repository: 'github://pharo-containers/Container-AVL/src' ].

Why use Containers-AVL-Tree?

AVL Trees maintain sorted data with guaranteed efficient operations, perfect for applications requiring consistent performance regardless of input order.

Key Benefits

• Guaranteed Performance: O(log n) worst-case for all operations
• Self-Balancing: Automatic rebalancing through rotations
• Ordered Iteration: Automatic sorted traversal
• Range Queries: Efficient retrieval of value ranges

Basic Usage

"Create and populate an AVL Tree"
tree := CTAVLTree new.
tree addAll: #(50 30 70 20 40 60 80).

"Search operations"
tree includes: 30. "=> true"
tree findMin. "=> 20"
tree findMax. "=> 80"

"Range queries"
tree elementsFrom: 35 to: 65. "=> #(40 50 60)"

"Tree automatically stays balanced"
tree validate. "=> true"
tree height. "=> 3 (logarithmic height)"

Real-World Use Case

"Order book for trading system - needs guaranteed fast operations"
orderBook := CTAVLTree new.
orderBook addAll: #(100.50 100.75 100.25 101.00 99.75).

"Fast operations regardless of market conditions"
bestPrice := orderBook findMax. "=> 101.00"
competitivePrices := orderBook elementsGreaterThan: 100.40.
"=> #(100.50 100.75 101.00)"

"Remove filled orders - tree rebalances automatically"
orderBook remove: 101.00.
orderBook validate. "=> still perfectly balanced"

Performance Advantage

AVL Trees excel with sorted or nearly-sorted data where regular BSTs fail:

"Worst case for regular BST: sorted input"
sortedData := 1 to: 10000.

avlTree := CTAVLTree new.
avlTree addAll: sortedData.
avlTree height. "=> ~14 (logarithmic)"

"Regular BST would have height 10000 (linear)!"

Contributing

This is part of the Pharo Containers project. Feel free to contribute by implementing additional methods, improving tests, or enhancing documentation.