AVL Tree
এভিএল ট্রি
প্রতিটা node-এ বাম-ডান subtree-র height difference সর্বোচ্চ ১ রাখা self-balancing BST — rotation দিয়ে balance ফেরত আনে, search guaranteed O(log n)।
also: avl, avl tree
Balance factor = height(right) − height(left); প্রতি node-এ এটা −১, ০ বা +১ থাকতে বাধ্য। Insert/delete-এ নষ্ট হলে rotation-এ ঠিক করতে হয়।
| Case | চেনা যায় | সমাধান |
|---|---|---|
| LL | বাম সন্তানের বামে ভারী | এক rotation ডানে |
| RR | ডান সন্তানের ডানে ভারী | এক rotation বামে |
| LR | বাম সন্তানের ডানে ভারী | আগে বামে, পরে ডানে |
| RL | ডান সন্তানের বামে ভারী | আগে ডানে, পরে বামে |
Height সর্বোচ্চ প্রায় 1.44·log₂(n) — Red-Black tree-র চেয়ে বেশি টানটান balance, তাই lookup-heavy workload-এ AVL ভালো; বিনিময়ে insert/delete-এ rotation একটু বেশি লাগে।