標籤
紅黑樹：平衡二叉樹的一種，簡單理解它的規則
2025-12-20 107 閱讀 數據結構 紅黑樹 平衡二叉樹 數據結構 自平衡樹 Java TreeMap

紅黑樹是自平衡二叉搜索樹，通過顏色標記和5條規則保證平衡，使插入、刪除、查找複雜度穩定在O(log n)。核心規則包括：節點非紅即黑；根爲黑色；空葉子（NIL）爲黑色；紅節點子節點必爲黑色（避免連續紅節點）；任一節點到後代NIL路徑的黑節點數（黑高）一致。規則4阻止連續紅節點，規則5確保黑高相等，共同限制樹高在O(log n)。插入新節點爲紅色，若父紅需調整（變色或旋轉）。廣泛應用於Java TreeMap、Redis有序集合等，以平衡結構實現高效有序操作。

閱讀全文
平衡二叉樹：爲什麼需要平衡？旋轉操作簡單講
2025-12-20 111 閱讀 數據結構 平衡二叉樹 AVL樹 旋轉操作 平衡因子 數據結構

二叉搜索樹（BST）因極端插入可能退化爲鏈表，操作複雜度升至O(n)。平衡二叉樹通過**平衡因子**（節點左右子樹高度差）控制平衡，要求平衡因子爲-1、0或1。當不平衡時，通過**旋轉操作**（LL右旋、RR左旋、LR先左旋後右旋、RL先右旋後左旋）調整結構，使樹高保持log n級別，確保查找、插入、刪除等操作複雜度穩定在O(log n)。旋轉本質是調整支點，恢復樹的平衡結構。

閱讀全文