紅黑樹和平衡二叉樹的區別

一、基本概念

平衡二叉樹：

平衡二叉樹是一種二叉搜索樹，它的每個結點的左子樹和右子樹的高度之差不超過1。有AVL樹、紅黑樹等類型的平衡二叉樹。平衡二叉樹的插入和刪除操作會引起局部的旋轉操作，以保證樹的平衡。

紅黑樹：

紅黑樹也是一種自平衡二叉搜索樹，除了滿足二叉搜索樹的性質之外，紅黑樹還滿足以下5個性質，這些性質是用來保證紅黑樹在動態添加/刪除節點時能自我平衡：

1. 每個節點非紅即黑。

2. 根節點必須是黑色的。

3. 每個葉子節點（NIL節點，即空節點）都是黑色的。

4. 如果一個節點是紅色的，則它的兩個子節點都是黑色的。

5. 從任一節點到其每個葉子節點的所有路徑都包含相同數量的黑色節點。

二、插入刪除操作

平衡二叉樹的插入和刪除操作會引起局部的旋轉操作，以保證樹的平衡。具體來說：

1. 插入操作：如果插入一個節點後打破了樹的平衡，那麼進行比較少的旋轉操作就可以調整回平衡。

2. 刪除操作：如果刪除一個節點後打破了樹的平衡，那麼進行比較少的旋轉操作就可以調整回平衡。

平衡二叉樹對於插入和刪除的操作都需要保證在平衡二叉樹中遵守平衡約束，因此相對比較複雜。

而紅黑樹在插入和刪除節點時的平衡策略相對簡單一些，具體如下：

1. 插入操作：按照二叉搜索樹的規則進行插入，並將插入的新節點標記為紅色。然後對紅黑樹進行必要的調整，以保持紅黑樹的5個性質。調整過程中使用了旋轉和顏色變化的策略，來保證紅黑樹的5個特性。

2. 刪除操作：同樣按照二叉搜索樹的規則進行刪除，如果被刪除的節點是紅色的，就直接刪除；如果是黑色的，則reb-black性質就被打破了，這時需要通過旋轉、移動、染色等方式重新調整樹的結構，以保證紅黑樹的5個特性。

三、代碼實現

以下是紅黑樹和平衡二叉樹的Python代碼實現，其中涉及了節點的定義、旋轉和顏色調整等操作：

# 平衡二叉樹節點定義
class AVLNode:
    def __init__(self, val):
        self.val = val
        self.height = 0
        self.left = None
        self.right = None

# 紅黑樹節點定義
class RBNode:
    def __init__(self, val, color=0):
        self.val = val
        self.color = color  # 0表示黑色，1表示紅色
        self.left = None
        self.right = None
        self.parent = None

# AVL樹中的旋轉操作
def rotate_right(node: AVLNode) -> AVLNode:
    pivot = node.left
    node.left = pivot.right
    pivot.right = node
    node.height = max(get_height(node.left), get_height(node.right)) + 1
    pivot.height = max(get_height(pivot.left), get_height(pivot.right)) + 1
    return pivot

def rotate_left(node: AVLNode) -> AVLNode:
    pivot = node.right
    node.right = pivot.left
    pivot.left = node
    node.height = max(get_height(node.left), get_height(node.right)) + 1
    pivot.height = max(get_height(pivot.left), get_height(pivot.right)) + 1
    return pivot

# 紅黑樹中的旋轉和顏色調整操作
def left_rotate(rb_node: RBNode):
    r_node = rb_node.right
    rb_node.right = r_node.left
    if r_node.left:
        r_node.left.parent = rb_node
    r_node.parent = rb_node.parent
    if rb_node.parent is None:
        root_node = r_node
    elif rb_node == rb_node.parent.left:
        rb_node.parent.left = r_node
    else:
        rb_node.parent.right = r_node
    r_node.left = rb_node
    rb_node.parent = r_node
    return root_node

def right_rotate(rb_node: RBNode):
    l_node = rb_node.left
    rb_node.left = l_node.right
    if l_node.right:
        l_node.right.parent = rb_node
    l_node.parent = rb_node.parent
    if rb_node.parent == None:
        root_node = l_node
    elif rb_node == rb_node.parent.right:
        rb_node.parent.right = l_node
    else:
        rb_node.parent.left = l_node
    l_node.right = rb_node
    rb_node.parent = l_node
    return root_node

def insert_fixup(rb_node: RBNode, root_node: RBNode):
    # 插入節點時，如果父節點為紅色，則需要進行平衡調整
    while rb_node.parent and rb_node.parent.color == 1:
        if rb_node.parent == rb_node.parent.parent.left:
            # 父節點為祖父節點的左孩子
            uncle = rb_node.parent.parent.right
            if uncle and uncle.color == 1:
                # Case 1：叔叔節點為紅色，則父節點和叔叔節點都改為黑色，祖父節點改為紅色
                rb_node.parent.color = 0
                uncle.color = 0
                rb_node.parent.parent.color = 1
                rb_node = rb_node.parent.parent
            else:
                if rb_node == rb_node.parent.right:
                    # Case 2：叔叔節點為黑色，且當前節點是父節點的右孩子，則需要左旋父節點
                    rb_node = rb_node.parent
                    root_node = left_rotate(rb_node)
                # Case 3：叔叔節點為黑色，且當前節點是父節點的左孩子，則父節點變成黑色，祖父節點變成紅色，然後右旋祖父節點
                rb_node.parent.color = 0
                rb_node.parent.parent.color = 1
                root_node = right_rotate(rb_node.parent.parent)
        else:
            # 父節點為祖父節點的右孩子
            uncle = rb_node.parent.parent.left
            if uncle and uncle.color == 1:
                # Case 1
                rb_node.parent.color = 0
                uncle.color = 0
                rb_node.parent.parent.color = 1
                rb_node = rb_node.parent.parent
            else:
                if rb_node == rb_node.parent.left:
                    # Case 2
                    rb_node = rb_node.parent
                    root_node = right_rotate(rb_node)
                # Case 3
                rb_node.parent.color = 0
                rb_node.parent.parent.color = 1
                root_node = left_rotate(rb_node.parent.parent)
    root_node.color = 0
    return root_node

def insert_rbt(root_node: RBNode, val):
    rb_node = RBNode(val, 1)
    node = root_node
    while node:
        if val < node.val:
            if node.left:
                node = node.left
            else:
                node.left = rb_node
                rb_node.parent = node
                break
        else:
            if node.right:
                node = node.right
            else:
                node.right = rb_node
                rb_node.parent = node
                break
    root_node = insert_fixup(rb_node, root_node)
    return root_node

四、總結

紅黑樹和平衡二叉樹都是一種在動態添加/刪除節點時能自我平衡的二叉搜索樹，但是它們之間還是有不少差異的。其中，平衡二叉樹對於插入和刪除的操作都需要保證在平衡二叉樹中遵守平衡約束，因此相對比較複雜；而紅黑樹在插入和刪除節點時的平衡策略相對簡單一些，易於實現以及調試。因此，對於動態操作較為頻繁、對性能要求較高的場景，紅黑樹可能是更好的選擇。