red-black tree

/ˈrɛdˌblæk triː/ レッドブラックツリー

1. 自己平衡二分探索木の一種。ノードが赤か黒の色を持ち、特定のルールに従って平衡を保つデータ構造。

赤と黒のルールを用いて木の平衡を保ち、探索、挿入、削除といった操作が常に効率的に行えるように設計された二分探索木の一種です。これにより、最悪の場合でもO(log n)の時間計算量を保証します。

A red-black tree is a type of self-balancing binary search tree. (赤黒木は自己平衡二分探索木の一種です。)

• A red-black tree: 「赤黒木」という、データ構造の一種を指します。
• is: 「～である」という存在や状態を表します。
• a type of: 「～の一種」という意味です。
• self-balancing: 「自己平衡型」という意味で、木が自動的にバランスを保つことを指します。
• binary search tree.: 「二分探索木」というデータ構造を指します。

Red-black trees guarantee O(log n) time complexity for operations. (赤黒木は操作に対してO(log n)の時間計算量を保証します。)

• Red-black trees: 「赤黒木」を指します。
• guarantee: 「～を保証する」という意味です。
• O(log n) time complexity: 「O(log n)の時間計算量」という意味で、アルゴリズムの効率性を表す指標です。
• for operations.: 「操作に対して」という意味です。

They are commonly used in implementing associative arrays. (これらは連想配列の実装によく使われます。)

• They: 「それら」、ここでは赤黒木を指します。
• are commonly used: 「一般的に使用される」という意味です。
• in implementing: 「～を実装する際に」という意味です。
• associative arrays.: 「連想配列」というデータ構造を指します。

2. コンピュータ科学におけるデータ構造の一種で、ノードの色と位置に関する厳格なルールによって平衡性を維持する二分探索木。

赤黒木は、根が黒であること、赤ノードの子は必ず黒であること、任意のノードからその子孫の葉までの全てのパスは同じ数の黒ノードを含むこと、といった特定のルールに従うことで平衡を維持します。これにより、効率的な検索、挿入、削除が可能になります。

Every node in a red-black tree is either red or black. (赤黒木のすべてのノードは、赤か黒のいずれかです。)

• Every node: 「すべてのノード」を指します。
• in a red-black tree: 「赤黒木において」という意味です。
• is either red or black.: 「赤か黒のいずれかである」という意味です。

The root of a red-black tree is always black. (赤黒木の根は常に黒です。)

• The root: 「根（ルート）」を指します。
• of a red-black tree: 「赤黒木の」という意味です。
• is always black.: 「常に黒である」という意味です。

No two adjacent red nodes are allowed in a red-black tree. (赤黒木では、隣接する2つの赤ノードは許されません。)

• No two adjacent red nodes: 「隣接する2つの赤ノードは存在しない」という意味です。
• are allowed: 「許される」の否定形です。
• in a red-black tree.: 「赤黒木において」という意味です。

関連

• Binary search tree
• AVL tree
• Data structure
• Algorithm
• Self-balancing tree