比較次數：0
節點數：0
紅色（current）= 當前正在比較的節點；綠色（visited）= 本次 insert/search 操作已走過的比較路徑。
搜尋結果
—
二元搜尋樹的規則很簡單：每個節點左邊放比它小的、右邊放比它大的，找一個數就像猜數字遊戲，每往下一層 就砍掉一半範圍，平均只要 log n 步。但它有個陷阱：如果你照大小順序一個個插入（1、2、3…），樹會整個 往一邊倒、變成一條鏈，查詢就退回從頭找到尾的 n 步。AVL 樹就是來補這個洞的：每插一個就檢查有沒有長歪， 一歪就靠「旋轉」把樹轉正，保證永遠矮胖、查詢穩定 log n。這頁讓你並排看：同一組數字，BST 怎麼歪掉、AVL 怎麼 每次把它轉回平衡。
兩者都是「左小右大」的二元搜尋樹，插入與搜尋都靠逐層比較決定往左或往右子樹——但 BST 本身不做任何平衡調整， 插入遞增或遞減序列會退化成一條鏈，比較次數從 O(log n) 惡化到 O(n)；AVL 樹在每次插入後檢查每個祖先節點的平衡因子 （左右子樹高度差），一旦 |balance| > 1 就透過 LL/RR/LR/RL 四種旋轉重新調整樹形，換來插入與搜尋皆保證 O(log n) 的代價。
insert(value) 從 root 開始逐層比較：value < node.value 往左子樹、value > node.value 往右子樹， 走到 node == null 就在該處建立新節點；search(value) 走法完全相同，比較相等即命中，走到 null 則未找到（miss）。 本頁固定腳本刻意選了平衡形狀的插入序（root=50，左右子樹各 3 個節點），比較路徑深度均勻； 但這只是巧合——BST 完全不檢查也不維護平衡，換一組遞增序列（如 10,20,30,40...）就會退化成單邊鏈狀， 對照下方 AVL 靠旋轉維持的 O(log n) 保證。
標準 BST 插入之後，從新節點沿路徑回溯，逐一更新每個祖先的高度 height = 1 + max(height(left), height(right))； 再計算平衡因子 balance = height(left) - height(right)。只要某節點 |balance| > 1 就代表失衡， 依失衡型態旋轉：LL（左左）→右旋、RR（右右）→左旋、LR（左右）→先左旋子節點再右旋、RL（右左）→先右旋子節點再左旋。 本頁固定插入序（30,20,10,40,50,45,5,15,12,22）為實測選定，涵蓋 LL/RR/LR/RL 四種旋轉各至少一次。 每個節點上方標示 h=高度、bf=平衡因子，|bf| > 1 即觸發旋轉。