🌳 धडा 09 — Trees आणि heaps: कॅटलॉगचा खण आणि व्यासपीठ

📍 तुम्ही इथे आहात: 12 पैकी धडा 09 · पुढे: lesson-10-graphs

📦 या ब्रँचमध्ये काय आहे

धडे 01–09. structure रूपातला binary search, त्याला balance का लागतो, tree मधून चालण्याच्या तीन पद्धती, आणि वर कोण आहे हे नेहमी माहीत असणारा structure.

dsa/structures.py — BST (insert, step count सह search, in-order, height), MinHeap (sift up/down)
dsa/demo.py — trees

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

ग्रंथालयाचा कॅटलॉगचा खण: प्रत्येक कार्ड सांगते "लहान कार्डे माझ्या डावीकडे, मोठी उजवीकडे". कार्ड शोधणे हा पुन्हा binary search च — प्रत्येक कार्डाजवळ खणाचा अर्धा भाग सोडा. डावे-मी-उजवे असे चाललात तर कार्डे आपोआप sorted बाहेर येतात. पण कार्डे sorted क्रमाने लावली तर प्रत्येक कार्ड आधीच्याच्या उजवीकडे जाते: खण एक लांबलचक साखळी बनतो — वेषांतर केलेली list, O(n). Balanced trees खण छोटा ठेवायला कार्डे फिरवतात (rotate).

क्रीडा दिनाचे व्यासपीठ: सर्वात जलद धावपटू नेहमी वर असते. नवी वेळ आली? ती तळाशी ठेवा आणि हळू वेळांना ओलांडून वर चढू द्या. वरची काढायची? शेवटची वर आणा आणि तिला खाली बुडू द्या. प्रत्येक दुरुस्ती म्हणजे काही अदलाबदली — O(log n) — आणि तुम्ही कधीच पूर्ण list sort करत नाही.

🗺️ आकृती

flowchart TD
  R["50"] --> A["25"] & B["75"]
  A --> A1["12"] & A2["37"]
  B --> B1["62"] & B2["87"]
  A1 --> A11["6"] & A12["18"]

❓ काय

BST: left < node < right. Insert/search O(height): balanced असेल तर O(log n), degenerate असेल तर O(n). In-order चाल = sorted; pre-order = copy; post-order = delete; level-order = queue सह BFS.
Balanced trees (AVL, red-black) height O(log n) ठेवायला insert वेळी rotate करतात; B-trees म्हणजे प्रत्येक database index मागची रुंद, disk ला सोयीची आवृत्ती; कामावर Python चे sortedcontainers किंवा list वर bisect.
Heap: array मधले complete binary tree (children of i म्हणजे 2i+1, 2i+2); parent ≤ children (min-heap). Push: append + sift up; pop: शेवटचा वर swap + sift down; दोन्ही O(log n); peek O(1). Python मध्ये heapq. उपयोग: priority queues, Dijkstra (धडा 10), top-k, schedulers.

🤔 का

बदलत असतानाही sorted data sorted राहतो तो trees मुळे; पुन्हा sort न करता वारंवार minimum मिळतो तो heaps मुळे. दोघे मिळून database indexes, schedulers, आणि अंतर मोजणाऱ्या प्रत्येक graph algorithm मधली priority queue समजावतात.

🔧 कसे (या repo मध्ये)

BST.search किती कार्डे पाहिली ती संख्या परत करतो; demo.py trees त्याच 11 keys balanced क्रमाने (height 4) आणि sorted क्रमाने (height 11) insert करतो. MinHeap हा array आहे, ज्यात push/pop index गणिताने sifts करतात.

🧪 करून पाहा

python3 dsa/demo.py trees
python3 - <<'EOF'
import sys, heapq, random; sys.path.insert(0, "dsa"); from structures import BST, MinHeap
t = BST(); [t.insert(k) for k in random.Random(4).sample(range(1000), 500)]
print("500 random keys → height", t.height(), "(log2 500 ≈ 9; a random tree runs about twice that)")
print("in-order first 5:", t.inorder()[:5])
times = [12.9, 11.4, 13.7, 10.8, 12.1]
print("top 3 with heapq.nsmallest:", heapq.nsmallest(3, times))     # O(n log k) — no full sort
EOF

✅ तपासा — तुम्हाला काय दिसायला हवे

Balanced क्रम: height 4, search(43) 4 कार्डे पाहतो; sorted क्रम: height 11, 11 कार्डे; heap 10.8, 11.4, 12.1 pop करतो. तुमच्या random tree ची height 18 आहे आणि त्याची in-order चाल sorted आहे; nsmallest त्याच तीन वेळा देतो.

🏁 तुम्ही आत्ताच काय सिद्ध केले

BST म्हणजे ज्यात insert करता येतो असा binary search, balance मुळेच तो O(log n) राहतो, आणि heap sorting शिवाय O(log n) मध्ये minimum देतो.

⚠️ नेहमीच्या चुका

sorted input वर साधा BST (वेषांतर केलेली list). balanced tree किंवा list वर bisect वापरा.
sorted क्रम मिळवायला heap वापरणे (तो वारंवार min देतो; तेच heap sort आहे, O(n log n)).
"binary tree" (कोणतीही दोन children) आणि "binary search tree" (क्रमबद्ध) यांत गोंधळ.

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: प्रत्येक CREATE INDEX म्हणजे B-tree; प्रत्येक scheduler आणि प्रत्येक "पुढचा event" loop म्हणजे heap; प्रत्येक JSON document म्हणजे तुम्ही recursively चालता असे tree.

⏭️ पुढे

धडा 10 — graphs: कॉरिडॉरचा नकाशा, आणि त्यातून चालण्याच्या तीन पद्धती.

🌳 Lesson 09 — Trees & heaps: the catalogue drawer and the podium

📍 You are here: Lesson 09 of 12 · Next: lesson-10-graphs

📦 What's in this branch

Lessons 01–09. Binary search as a structure, why it needs balance, three ways to walk a tree, and the structure that always knows who is on top.

dsa/structures.py — BST (insert, search with a step count, in-order, height), MinHeap (sift up/down)
dsa/demo.py — trees

🧒 Explain like I'm 5

The library's catalogue drawer: every card says "smaller cards are on my left, bigger on my right". Finding a card is binary search again — halve the drawer at each card. Walk it left-me-right and the cards come out sorted for free. But file cards in sorted order and every card is to the right of the last: the drawer becomes one long chain — a list in disguise, O(n). Balanced trees rotate cards to keep the drawer short.

The podium at sports day: the fastest runner is always on top. A new time arrives? Put it at the bottom and let it climb past slower times. Take the top? Move the last one up and let it sink. Each fix is a few swaps — O(log n) — and you never sort the whole list.

🗺️ Diagram

flowchart TD
  R["50"] --> A["25"] & B["75"]
  A --> A1["12"] & A2["37"]
  B --> B1["62"] & B2["87"]
  A1 --> A11["6"] & A12["18"]

❓ What

BST: left < node < right. Insert/search O(height): O(log n) balanced, O(n) degenerate. In-order walk = sorted; pre-order = copy; post-order = delete; level-order = BFS with a queue.
Balanced trees (AVL, red-black) rotate on insert to keep height O(log n); B-trees are the wide, disk-friendly version behind every database index; Python's sortedcontainers or bisect on a list at work.
Heap: a complete binary tree in an array (children of i are 2i+1, 2i+2); parent ≤ children (min-heap). Push: append + sift up; pop: swap last to top + sift down; both O(log n); peek O(1). heapq in Python. Uses: priority queues, Dijkstra (lesson 10), top-k, schedulers.

🤔 Why

Trees are how sorted data stays sorted while changing; heaps are how you get the minimum repeatedly without re-sorting. Between them they explain database indexes, schedulers, and the priority queue in every graph algorithm that measures distance.

🔧 How (in this repo)

BST.search returns the number of cards looked at; demo.py trees inserts the same 11 keys in a balanced order (height 4) and in sorted order (height 11). MinHeap is an array with push/pop doing the sifts by index arithmetic.

🧪 Try it

python3 dsa/demo.py trees
python3 - <<'EOF'
import sys, heapq, random; sys.path.insert(0, "dsa"); from structures import BST, MinHeap
t = BST(); [t.insert(k) for k in random.Random(4).sample(range(1000), 500)]
print("500 random keys → height", t.height(), "(log2 500 ≈ 9; a random tree runs about twice that)")
print("in-order first 5:", t.inorder()[:5])
times = [12.9, 11.4, 13.7, 10.8, 12.1]
print("top 3 with heapq.nsmallest:", heapq.nsmallest(3, times))     # O(n log k) — no full sort
EOF

✅ Verify — what you should see

Balanced order: height 4, search(43) looks at 4 cards; sorted order: height 11, 11 cards; the heap pops 10.8, 11.4, 12.1. Your random tree is height 18 and its in-order walk is sorted; nsmallest gives the same three times.

🏁 What you just proved

A BST is binary search you can insert into, balance is what keeps it O(log n), and a heap gives you the minimum in O(log n) without sorting.

⚠️ Common mistakes

A plain BST on sorted input (a list in disguise). Use a balanced tree or bisect on a list.
Using a heap to get sorted order (it gives the min, repeatedly; that is heap sort, O(n log n)).
Confusing "binary tree" (any two children) with "binary search tree" (ordered).

🏭 Why this matters in production: every CREATE INDEX is a B-tree; every scheduler and every "next event" loop is a heap; every JSON document is a tree you walk recursively.

⏭️ Next

Lesson 10 — graphs: the corridor map, and three ways to walk it.

← Previousbinary search Next →graphs

This page is the lesson's README from the lesson-09-trees-heaps branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.