trees_basics README.md (Markdown)

trees_basics

Clean Java implementations of self-balancing binary search trees:

• AVL Tree — strictly height-balanced BST (avl_trees/)
• Red-Black Tree — probabilistically balanced BST (red_black_trees/)

🧰 Requirements

• JDK 17+ (plain Java, no build tools required)

🧪 How to Compile and Run

# 1) Compile all sources into the out/ folder
mkdir -p out
find src -name "*.java" > sources.txt
javac -encoding UTF-8 -d out @sources.txt

# 2) Run demos (each class already contains a main method)
# AVL:
java -cp out avl_trees.AVLtreeTest

# Red-Black:
java -cp out red_black_trees.RBTtest

🧭 Project Structure

src/
 ├─ avl_trees/
 │   ├─ AVLnode.java
 │   ├─ AVLtree.java
 │   └─ AVLtreeTest.java
 └─ red_black_trees/
     ├─ RBTnode.java
     ├─ RedBlackTree.java
     └─ RBTtest.java

🧮 Complexity Overview

Operation	AVL Tree	Red-Black Tree
Search	O(log n)	O(log n)
Insert	O(log n)	O(log n)
Delete	O(log n)	O(log n)
Height (worst case)	~1.44·log₂(n)	≤ 2·log₂(n)

AVL is more strictly balanced, resulting in faster lookups.
Red-Black has fewer rotations on insertions/deletions, making updates more efficient.

🔁 Rotations (Cheat Sheet)

• AVL: LL, RR, LR, RL (single/double rotations after insert/delete)
• Red-Black: recoloring + left/right rotations (fix-ups for red-uncle / black-uncle cases)

🚀 Future Improvements

• Add unit tests for edge cases and visualization for in-order, pre-order, and post-order traversals.
• Add fully documented Red-Black Tree delete cases.
• Benchmark performance comparison: AVL vs Red-Black on large data sets.

📄 License

MIT — see LICENSE.

👩‍💻 Author

CellaIoana