平衡二叉排序樹ppt課件-展示頁(yè)
2025-05-08 00:24本頁(yè)面
【正文】 入的結(jié)點(diǎn)和第一個(gè)平衡度不為 0 的結(jié)點(diǎn)（也可能是危機(jī)結(jié)點(diǎn)）之間的結(jié)點(diǎn)，其平衡度皆為 0。1412539 286353605017187 30+1+11110000000 0平衡樹1412539 286353605017187 30+1+11110000000 02+1+1+2原平衡度為 0危機(jī)結(jié)點(diǎn)如何用最簡(jiǎn)單、最有效的辦法保持平衡分類二叉樹的性質(zhì)不變？1412539 286353605017187 30+1+11110000000 02+1+1+2原平衡度為 0危機(jī)結(jié)點(diǎn)如何用最簡(jiǎn)單、最有效的辦法保持平衡分類二叉樹的性質(zhì)不變？解決方案：不涉及到危機(jī)結(jié)點(diǎn)的父親結(jié)點(diǎn)，即以危機(jī)結(jié)點(diǎn)為根的子樹的高度應(yīng)保持不變（圖為 3 ）。403025 5020 6058403025 607080501412539 286353605017187 30+1+11110000000 0是平衡樹不是豐滿樹14539 2863536050171830+1+21100000+1不是平衡樹1?以插入為例： 在左圖所示的平衡樹中插入數(shù)據(jù)場(chǎng)為 2 的結(jié)點(diǎn)。平衡二叉排序樹的 平均查找長(zhǎng)度為 O（ log2n） ?；蛘哒f每個(gè)結(jié)點(diǎn)的左右子樹的高度最多差一的二叉樹。C F? 平衡因子（平衡度）：結(jié)點(diǎn)的平衡度是結(jié)點(diǎn)的左子樹的高度－右子樹的高度。平衡二叉排序樹DGEDABCFEGBA? 起因：提高查找速度，避免最壞情況出現(xiàn)。如右圖情況的出現(xiàn)。? 平衡二叉樹：每個(gè)結(jié)點(diǎn)的平衡因子都為 ＋ － 0 的二叉樹。平衡二叉樹平衡二叉排序樹 ——AV 樹定義： 一棵平衡二叉排序樹或者是空樹，或者是具有下列性質(zhì)的二叉排序樹：左子樹與右子樹的高度之差的
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1