Algorithms with Python

はじめに

今回は赤黒木 (red-black tree) という平衡木 (balanced tree) を取り上げます。二分木は拙作のページ 二分木とヒープ で説明したように、左右の部分木のバランスが崩れると性能が劣化する欠点があります。極端な例ですが、昇順にソートされたデータを二分木に挿入していくと、データは右側の部分木にしか挿入されず、連結リストと同じ線形探索になってしまいます。

これを補うために、木のバランスを一定の範囲に収める平衡木が考案されています。有名なところでは、二分木をベースにした AVL 木、赤黒木、AA 木、多分木をベースにした 2-3 木、B 木、B* 木などがあります。今までに、AVL 木 ([1] [2]) と 2-3 木 ([1] [2]) は詳しく説明しました。そこで、今回は C++ の STL (Standard Template Library) などで用いられている赤黒木を紹介しましょう。

●赤黒木とは？

赤黒木は次の条件を満たす「二分木」です。

• 各節は赤または黒に区分される。
• ある節が赤ならばその子は必ず黒である。黒節の子に制限はない。
• ルートから葉までの黒節の個数を「黒高さ」という。赤黒木はどの経路でも黒高さが同じになる。
• ルートの節は黒である。

赤黒木は AVL 木と同様に二分木の一種ですが、節を赤と黒で色分けするところが特徴です。節を赤と黒の 2 色で塗り分けることから、2 色木と呼ばれる場合もあります。赤黒木のポイントは、ルートから葉までの全経路の黒高さを同じにすることです。簡単な例を示しましょう。次の図を見てください。

上図は黒高さが 2 の場合です。ルートから葉までのすべての経路で黒高さが 2 になっています。節が格納している値は整数値で、二分木の条件を満たしていることはすぐにわかると思います。図では root の節が黒で、その子は 12 が黒で 16 が赤になっています。赤黒木では、赤節の子は必ず黒になりますが、黒節の子は制限が無いので赤でも黒でもかまいません。

節 16 は赤なので、その子は 2 つとも黒になります。また、節 13, 18 のように子がない赤節もあります。赤節の子が一つだけ存在すると黒高さが同じにならないので、赤節は子が二つある場合と子が一つもない「葉」になる場合の 2 通りしかありません。

黒高さが 2 の場合、一番短い経路はすべての節が黒の場合（黒 - 黒）になります。逆に、一番長い経路は黒節の子が赤になる場合（黒 - 赤 - 黒 - 赤）になります。図では 14 - 12 の経路 (A) が最短で、14 - 16 - 17 - 18 の経路 (B) が最長になります。赤黒木の条件により、(A) より短い経路や (B) より長い経路はありえません。したがって、黒高さが N の赤黒木の場合、木の高さは N 以上 2 * N 以下になります。このように、赤黒木は黒高さを揃えることで平衡木を実現しているのです。

●補足

実をいうと、赤黒木は「2-3-4 木」という多分木の動作を二分木で実現したものです。2-3-4 木は最小で 2 つ、最大で 4 つの子を持ちます。2-3 木よりも一つ多くの子を持つことができるわけです。2-3-4 木の節を赤節と黒節で表したものが赤黒木です。対応関係を図で表すと、次のようになります。

子が 2 つの場合は簡単です。上図 (a) のように、黒節にデータ A と 2 つの子を格納します。子が 3 つの場合は、(b) のように 2 通りの方法があります。どちらの場合でも、赤節は黒節の子になります。赤節と黒節の 2 つで 3 つの子を保持しています。子が 4 つの場合は、(c) のように黒節の子は 2 つとも赤節になります。3 つの節で 4 つの子を保持するわけです。

このように、2-3-4 木は赤黒木で表すことができます。逆に、赤黒木を 2-3-4 木で表すこともできます。

●データの挿入

次は、データの挿入について詳しく説明します。新しいデータは赤節として赤黒木に挿入します。親が黒節の場合は簡単です。黒節の子が赤節ならば赤黒木の条件を満たしているので、そのまま挿入するだけです。問題は赤節の親にデータを挿入する場合です。大きく分けると次の 2 通りがあります。

節 D が新しく挿入するデータで、節 B が赤節で節 A が黒節になります。場合分けは節 B の兄弟である節 C で行います。(1) は節 C が赤の場合で、(2) は節 C が終端（空の木）の場合です。

(2) の場合、右回転で木のバランスを修正することができますね。あとは節の色を塗り替えることで赤黒木の条件を満たすことができます。ところが (1) の場合、木のバランスは回転操作では修正できません。この場合、節 B と C を黒に、節 A を赤に塗り替えます。すると、節 A 以下の部分木は赤黒木の条件を満たしますね。あとは、節 A とその親が赤黒木の条件を満たしているかチェックします。

このとき、節 A の親が黒節ならば簡単です。節 A を赤に塗り替えても赤黒木の条件を満たしているので、修正はこれで終わりです。問題は節 A の親が赤の場合です。この場合も木の修正が必要になります。つまり (1) の場合、バランスの修正は節 A よりも上の木で行うのです。この場合、大きく分けると 3 通りのパターンがあります。次の図を見てください。

ここでも場合分けは節 A の親 Y の兄弟である節 Z の色で行います。(1) は節 Z が赤の場合、(2) と (3) は節 Z が黒の場合です。(1) の場合、回転操作で木のバランスを修正できないので、節 Y と Z の色を黒に、節 X の色を赤に塗り替えて、節 X よりも上の木でチェックを行います。

このように、ルート方向に向かって赤黒木の条件をチェックしていきます。(1) の場合が続くと、最後にはルートにたどりつきます。(1) で節 X がルートの場合を考えてください。赤黒木の条件からルートの節は黒でなければいけません。したがって、節 X を赤に塗り替えても黒に戻すことになります。つまり、ここで黒高さが一つ増えるわけです。

(2) と (3) は回転操作で木のバランスを修正することができます。まず、(2) から説明しましょう。次の図を見てください。

この場合、節 X と Z は黒と黒のつながりなので、回転操作によってその間に赤節を挿入すると考えてください。回転したあとで、節 X と Y の色を塗り替えます。

赤黒木の場合、どの経路でも黒高さは同じなので、回転前の部分木 A, W, Z に含まれている黒節の個数は同じになります。そして、回転した後でも黒高さは変化しないことに注意してください。回転操作によって右部分木の高さは一つ増えますが、そこに赤節を挿入するので黒高さは同じままなのです。

(3) の場合はちょっと複雑です。次の図を見てください。

まず、節 Y 以下の部分木に対して左回転を行います。すると、赤節 A の左の子が赤節 Y になります。この形は (2) の場合と同じなので、節 X 以下の部分木に対して右回転を行えば、木のバランスを修正することができます。このあと、節 A と X の色を塗り替えます。このように回転操作を 2 回行いますが、この操作でも黒高さは変化しないことに注意してください。

それから、今までの説明では左部分木にデータを挿入しましたが、当然ですが右部分木にデータが挿入されることもあります。この場合も同じように回転操作で木のバランスを修正することができます。実際にプログラムを作るときは、回転操作の場合分けに注意してください。

●プログラムの作成

それでは、赤黒木にデータを挿入するプログラムを Python で作ってみましょう。最初に、節を表すクラスを定義します。

リスト : 節と終端の定義

# 終端
null = None

# 色
BLACK = 0
RED = 1

# 節
class Node:
    def __init__(self, x, color = RED):
        self.data = x
        self.color = color
        self.left = null
        self.right = null

# 終端の設定
def make_null():
    global null
    if null is None:
        null = Node(None, BLACK)
        null.left = None
        null.right = None
    return null

クラス名は Node としました。インスタンス変数 color には節の色をセットします。赤を RED (1) で、黒を BLACK (0) で表します。それから、二分木のプログラムでは終端を None で表しましたが、今回のプログラムでは終端を節 Node のオブジェクトで表すことにします。そして、終端オブジェクトの色を黒に設定します。このようにしても、赤黒木の条件に違反しません。また、終端と黒節の場合分けが不用になるのでプログラムも簡単になります。

関数 make_null() は終端オブジェクトを生成して返します。終端オブジェクトはグローバル変数 null に格納します。null が None の場合は終端オブジェクトがまだないので、Node() で終端オブジェクトを生成します。節の色は黒で、left と right には None をセットしておきます。

●木の回転操作と色の塗り替え

ところで、Robert Sedgewick 氏の "Left-Leaning Red Black Trees" (参考 URL 1) では、木を回転するときに節の色を塗り替えています。この方法を使うと、通常の赤黒木でもプログラムを簡略化することができます。次の図を見てください。

右回転すると節 A が右の子に、節 B が親節になります。このとき、B の色を A の色に塗り替え、A の色を無条件に赤に塗り替えます。すると、右回転することで、左の赤節を右へ移動させることができます。もし、節 D が赤節ならば、この操作で木のバランスを修正することができます。

同様に、左回転すると節 B が左の子に、節 A が親節になります。このとき、A の色を B の色に塗り替え、B の色を無条件に赤に塗り替えます。すると、左回転することで、右の赤節を左へ移動させることができます。もし、節 C が赤節ならば、この操作で木のバランスを修正することができます。

このように、木を回転するときに色を塗り替えることで、木のバランスを簡単に修正することができます。プログラムは次のようになります。

リスト : 二分木の回転操作

# 右回転
def rotate_right(node):
    lnode = node.left
    node.left = lnode.right
    lnode.right = node
    lnode.color = node.color
    node.color = RED
    return lnode

# 左回転
def rotate_left(node):
    rnode = node.right
    node.right = rnode.left
    rnode.left = node
    rnode.color = node.color
    node.color = RED
    return rnode

node を右回転すると、左の子 lnode が親になります。lnode.color を node.color に書き換え、node.color を赤に書き換えます。逆に、node を左回転すると、右の子 rnode が親になります。rnode.color を node.color に書き換え、node.color を赤に書き換えます。

●データの挿入処理

次はデータを挿入する関数 insert() を作成します。赤黒木の場合、新しい節を挿入したらルートの方に向かって木のバランスをチェックします。プログラムは次のようになります。

リスト : データの挿入

def insert(node, x):
    if node is null: return Node(x), False
    if x < node.data:
        node.left, flag = insert(node.left, x)
        return balance_insert_left(node, flag)
    elif x > node.data:
        node.right, flag = insert(node.right, x)
        return balance_insert_right(node, flag)
    return node, True

insert() は赤黒木のルートと挿入するデータを受け取り、挿入したあとの木と修正が終了したか否かを表すフラグを返します。フラグが True の場合は木のバランスがとれていることを表します。False の場合はバランスの修正が必要であることを表します。

node が null ならば新しい節を Node(x) で生成して、そこに節を挿入します。このとき、木のバランスを修正する必要があるので、フラグの値は False に設定します。次に、insert() を再帰呼び出して木をたどり、データを挿入する場所を探します。もしも、x と等しいデータがあれば、データを挿入せずに node と True を返します。この場合、木のバランスを修正する必要はありません。

そして、x が node.data よりも小さい場合は左部分木をたどり、大きい場合は右部分木をたどります。データが左部分木に挿入された場合は、関数 balance_insert_left() で木のバランスを修正ます。逆に、データが右部分木に挿入された場合は関数 balance_insert_right() で修正を行います。

なお、赤黒木のルートは必ず黒になるので、insert() を呼び出したあとはルートの color を BLACK にセットしてください。

●バランスの修正処理

次は関数 balance_insert_left() を説明します。次のリストを見てください。

リスト : バランスの修正

# 4node の分割
def split(node):
    node.color = RED
    node.left.color = BLACK
    node.right.color = BLACK

# 左部分木の修正
def balance_insert_left(node, flag):
    if flag: return node, flag
    if node.color == BLACK:
        flag = True
        # 左(赤)の子に赤があるか
        if node.left.right.color == RED:
            node.left = rotate_left(node.left)
        if node.left.left.color == RED:
            # 赤が 2 つ続く
            if node.right.color == RED:
                split(node)
                flag = False
            else:
                node = rotate_right(node)
    return node, flag

flag が False の場合に修正処理を行います。node が赤節の場合は、その親節で修正処理を行います。node が黒節の場合は、node.left に赤節の子がないかチェックします。

node.left の右の子が赤の場合は、node.left を左回転して左側に赤節をそろえます。次に、node.left の左の子が赤節かチェックします。このとき、node の右の子が赤節ならば、node は子を 4 つ持つ節 (4 node) なので木のバランスを修正することはできません。関数 split で 4 node を分割して、node の親節で木のバランスを修正します。

そうでなければ、node を右回転して木のバランスを修正することができます。また、node.left に赤節の子がない場合はバランスを修正する必要はありません。

右部分木のバランスを修正する関数 balance_insert_right() は、子のチェックと回転操作が左右対称になるだけなので説明は割愛いたします。詳細は プログラムリスト をお読みください。

●データ挿入のテスト

それでは、ここでデータ挿入のテストを行ってみましょう。テストプログラムは次のようになります。

リスト : データ挿入の簡単なテスト

# 木の表示
def print_node(node, n):
    color = ('B', 'R')
    if node is not null:
        print_node(node.left, n + 1)
        print('    ' * n, color[node.color], node.data)
        print_node(node.right, n + 1)

# 赤黒木の条件を満たしているか
def check_rbtree(node):
    if node is not null:
        if node.color == RED:
            if node.left.color == RED or node.right.color == RED:
                raise 'rbtree error1'
        a = check_rbtree(node.left)
        b = check_rbtree(node.right)
        if a != b: raise 'rbtree error2'
        if node.color == BLACK: a += 1
        return a
    return 0

# test
if __name__ == '__main__':
    import random
    root = make_null()
    buff = list(range(8))
    print('insert test')
    for x in buff:
        print('----- insert', x)
        root, _ = insert(root, x)
        root.color = BLACK
        print_node(root, 0)
        check_rbtree(root)

print_node() は赤黒木を表示する関数です。黒節は B を、赤節は R をつけて表しています。終端は None ではなく null なので、node と null を比較していることに注意してください。

check_rbtree() は赤黒木の条件をチェックする関数です。node が赤節の場合、その子が赤節であればエラーを送出します。check_rbtree() の返り値は黒高さです。左右の部分木の黒高さを求め、それが等しくない場合はエラーを送出します。

テストは 0 から 7 までの整数値を順番に赤黒木に挿入します。実行結果は次のようになります。

insert test
----- insert 0
 B 0
----- insert 1
 B 0
     R 1
----- insert 2
     R 0
 B 1
     R 2
----- insert 3
     B 0
 B 1
     B 2
         R 3
----- insert 4
     B 0
 B 1
         R 2
     B 3
         R 4
----- insert 5
     B 0
 B 1
         B 2
     R 3
         B 4
             R 5
----- insert 6
     B 0
 B 1
         B 2
     R 3
             R 4
         B 5
             R 6
----- insert 7
         B 0
     R 1
         B 2
 B 3
         B 4
     R 5
         B 6
             R 7

どの経路でも黒高さが同じになっていることがすぐにわかると思います。このように、赤黒木ではどのようなデータでも木のバランスが大きく崩れることはありません。

今度は木の高さを比較してみましょう。次のリストを見てください。

リスト : データ挿入の簡単なテスト (2)

import node
import avlnode
import rbnode
import random

# 木の高さを求める
def get_height(node, term = None):
    if node is not term:
        a = get_height(node.left, term)
        b = get_height(node.right, term)
        return max(a, b) + 1
    return 0

for x in [1000, 2000, 4000, 8000, 16000]:
    buff = list(range(x))
    random.shuffle(buff)
    a = None                # AVL tree
    b = None                # Binary tree
    c = rbnode.make_null()  # 赤黒木
    for n in buff:
        a = avlnode.insert(a, n)
        b = node.insert(b, n)
        c, _ = rbnode.insert(c, n)
        c.color = rbnode.BLACK
    print(x, get_height(a), get_height(b), get_height(c, rbnode.null))

関数 get_height() は木の高さを求めます。赤黒木の場合、rbnode.null で終端をチェックすることに注意してください。

それでは、実行結果を示します。

赤黒木の高さは AVL 木とほとんど同じになりました。赤黒木の場合、データの探索は二分木や AVL 木と同じなので、AVL 木と同様にデータを高速に探索できると思われます。

次はソート済みデータで試してみましょう。結果は次のようになりました。

• ソート済みデータの場合

AVL 木の場合、木の高さはソート済みデータの方が低くなりましたが、赤黒木は逆に高くなりました。赤黒木はソート済みデータを苦手としているようです。データの探索も遅くなるかもしれません。これはプログラムを完成したあとで、実際に試してみましょう。

次回はデータの削除について説明します。

●参考文献, URL

1. Robert Sedgewick, Left-Leaning Red Black Trees (PDF)

●プログラムリスト

#
# rbnode.py : 赤黒木用操作関数 (2-3-4 木をベース)
#
#             Copyright (C) 2008-2022 Makoto Hiroi
#

# 終端
null = None

# 色
BLACK = 0
RED = 1

# 節
class Node:
    def __init__(self, x, color = RED):
        self.data = x
        self.color = color
        self.left = null
        self.right = null

# 終端の設定
def make_null():
    global null
    if null is None:
        null = Node(None, BLACK)
        null.left = None
        null.right = None
    return null

# 右回転
def rotate_right(node):
    lnode = node.left
    node.left = lnode.right
    lnode.right = node
    lnode.color = node.color
    node.color = RED
    return lnode

# 左回転
def rotate_left(node):
    rnode = node.right
    node.right = rnode.left
    rnode.left = node
    rnode.color = node.color
    node.color = RED
    return rnode

#
# データの探索
#
def search(node, x):
    while node is not null:
        if x == node.data: return True
        elif x < node.data:
            node = node.left
        else:
            node = node.right
    return False

#
# データの挿入
#

# 4node の分割
def split(node):
    node.color = RED
    node.left.color = BLACK
    node.right.color = BLACK

# 左部分木の修正
def balance_insert_left(node, flag):
    if flag: return node, flag
    if node.color == BLACK:
        flag = True
        # 左(赤)の子に赤があるか
        if node.left.right.color == RED:
            node.left = rotate_left(node.left)
        if node.left.left.color == RED:
            # 赤が 2 つ続く
            if node.right.color == RED:
                split(node)
                flag = False
            else:
                node = rotate_right(node)
    return node, flag

# 右部分木の修正
def balance_insert_right(node, flag):
    if flag: return node, flag
    if node.color == BLACK:
        flag = True
        # 右(赤)の子に赤があるか
        if node.right.left.color == RED:
            node.right = rotate_right(node.right)
        if node.right.right.color == RED:
            # 赤が 2 つ続く
            if node.left.color == RED:
                split(node)
                flag = False
            else:
                node = rotate_left(node)
    return node, flag

# 挿入
def insert(node, x):
    if node is null: return Node(x), False
    if x < node.data:
        node.left, flag = insert(node.left, x)
        return balance_insert_left(node, flag)
    elif x > node.data:
        node.right, flag = insert(node.right, x)
        return balance_insert_right(node, flag)
    return node, True

#
# データの削除
#

# 右部分木の修正
def balance_right(node, flag):
    if flag: return node, flag
    if node.left.left.color == BLACK and node.left.right.color == BLACK:
        if node.left.color == BLACK:
            # left is 2node
            node.left.color = RED
            if node.color == BLACK: return node, False
            node.color = BLACK
        else:
            # node is 3node
            node = rotate_right(node)
            node.right, _ = balance_right(node.right, False)
    else:
        # left is 3,4node
        if node.left.right.color == RED:
            node.left = rotate_left(node.left)
        node = rotate_right(node)
        node.right.color = BLACK
        node.left.color = BLACK
    return node, True

# 左部分木の修正
def balance_left(node, flag):
    if flag: return node, flag
    if node.right.left.color == BLACK and node.right.right.color == BLACK:
        # right is 2node
        if node.right.color == BLACK:
            # node is 2node
            node.right.color = RED
            if node.color == BLACK: return node, False
            node.color = BLACK
        else:
            # node is 3node
            node = rotate_left(node)
            node.left, _ = balance_left(node.left, False)
    else:
        # right is 3,4node
        if node.right.left.color == RED:
            node.right = rotate_right(node.right)
        node = rotate_left(node)
        node.left.color = BLACK
        node.right.color = BLACK
    return node, True

# 最小値を探す
def search_min(node):
    while node.left is not null: node = node.left
    return node.data

# 削除
def delete(node, x):
    if node is null: return node, True
    if x == node.data:
        if node.left is null and node.right is null:
            return null, node.color == RED
        elif node.right is null:
            node.left.color = BLACK
            return node.left, True
        elif node.left is null:
            node.right.color = BLACK
            return node.right, True
        else:
            node.data = search_min(node.right)
            node.right, flag = delete(node.right, node.data)
            return balance_right(node, flag)
    elif x < node.data:
        node.left, flag = delete(node.left, x)
        return balance_left(node, flag)
    else:
        node.right, flag = delete(node.right, x)
        return balance_right(node, flag)

#
# 巡回
#
def traverse(node):
    if node is not null:
        for x in traverse(node.left):
            yield x
        yield node.data
        for x in traverse(node.right):
            yield x

# 木の表示
def print_node(node, n):
    color = ('B', 'R')
    if node is not null:
        print_node(node.left, n + 1)
        print('    ' * n, color[node.color], node.data)
        print_node(node.right, n + 1)

# 赤黒木の条件を満たしているか
def check_rbtree(node):
    if node is not null:
        if node.color == RED:
            if node.left.color == RED or node.right.color == RED:
                raise 'rbtree error1'
        a = check_rbtree(node.left)
        b = check_rbtree(node.right)
        if a != b: raise 'rbtree error2'
        if node.color == BLACK: a += 1
        return a
    return 0

# test
if __name__ == '__main__':
    import random
    root = make_null()
    buff = list(range(1000))
    random.shuffle(buff)
    print('insert test')
    for x in buff:
        root, _ = insert(root, x)
        root.color = BLACK
        check_rbtree(root)
    print('search test')
    random.shuffle(buff)
    for x in buff:
        if not search(root, x):
            raise 'search error'
    print('delete test')
    for x in buff:
        root, _ = delete(root, x)
        root.color = BLACK
        check_rbtree(root)