平衡二叉排序樹-展示頁
2024-08-16 17:02本頁面
【正文】 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 +1 1 1 1 0 0 0 0 0 0 0 0 平衡樹 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 +1 1 1 1 0 0 0 0 0 0 0 0 2 +1 +1 +2 原平衡度為 0 危機結點 如何用最簡單、最有效的辦法保持平衡分類二叉樹的性質不變？ 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 +1 1 1 1 0 0 0 0 0 0 0 0 2 +1 +1 +2 原平衡度為 0 危機結點 如何用最簡單、最有效的辦法保持平衡分類二叉樹的性質不變？ 解決方案： 不涉及到危機結點的父親結點，即以危機結點為根的子樹的高度應保持不變（圖為 3 ）。 40 30 25 50 20 60 58 40 30 25 60 70 80 50 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 +1 1 1 1 0 0 0 0 0 0 0 0 是平衡樹不是豐滿樹 14 5 3 9 28 63 53 60 50 17 18 30 +1 +2 1 1 0 0 0 0 0 +1 不是平衡樹 1 ?以插入為例： 在左圖所示的平衡樹中插入數據場為 2 的結點。 平衡二叉排序樹的 平均查找長度為 O（ log2n） ?；蛘哒f每個結點的左右子樹的高度最多差一的二叉樹。 C F ? 平衡因子（平衡度）：結點的平衡度是結點的左子樹的高度－右子樹的高度。平衡二叉排序樹 D G E D A B C F E G B A ? 起因：提高查找速度，避免最壞情況出現。如右圖情況的出現。 ? 平衡二叉樹：每個結點的平衡因子都為 ＋ － 0 的二叉樹。 平衡二叉樹 平衡二叉排序樹 —— AV樹 定義： 一棵平衡二叉排序樹或者是空樹，或者是具有下列性質的二叉排序樹：
環(huán)評公示相關推薦
鄂ICP備17016276號-1