はじめての C

lang

「二分木 続き 5」

つりあいの とれた 二分木には、代表的なものが 3つ あります。

はじめの 2つは、この tutorial で 扱うことになる spray木と AVL木です。

もう 1つの red-black木ですが、この tutorial では、簡単な 説明だけに しておきます。 でも 多分 将来の tutorial では、より 完全なものが できるでしょうね。

red-black木とは、(二分木とは) 別の 木の タイプで 2-3-4木と 呼ばれるものの、二分形式での 表記のことです。

2-3-4木では、root が すでに リンクを 2つ もつときに 3つ目の リンクを 追加し、別の リンクを 追加して 合計 4つに するために 分割を 行うことで、その 最小の高さ - minimal height - が 保たれています。

M が 挿入されると、次のような (Knuth 3, 6.2.3) 分割が 実行されます ▽


       J
   /         |
   E        L,T
 /   |   /   |     |          
A,C  G  K  M,N,R  V,X


       J
   /        |
   E      L,N,T
 /   |  /  |  |   | 
A,C, G  K  M  R  V,X 


        J,N
   /     |      | 
   E     L      T 
 /   |  /  |  /   | 
A,C  G  K  M  R  V,X

二分木だと、リンクを 追加すると いうような ゼイタクは できませんから、red-black木では 2-3-4 という 構成を 表すために カラー表記を 使っています (red が 内部リンク、black は 外部リンクに)。

red-black の 構造体に おいては、ノードが 3つ あるのと 同じことを、次のように 表します ▽


3 Node  Red-black Node (R = red link color)
  *      R  R  
/ | |   / or |
       *      *

ノードが 4つの ときは、次のように なります ▽


4 Node  Red-black Node (R = red link color)
   *       R
/ | | |   / |
         *   *

red-black の 図式は 全体として とても エレガントで、AVL木との 違いは 通常 その入力データに よっています。

この tutorial で、red-black ではなくて AVL の方を 選んだのは、まったくの 独断に よるものです。