1

CLRSで赤黒木を研究しています。赤黒木の性質が論じられている部分について2つ質問があります。CLRS からの一節は次のとおりです。

赤黒木は、次の赤黒特性を満たす二分木です。

  1. すべてのノードは赤または黒のいずれかです

  2. 根元が黒い

  3. すべての葉(NIL)は黒い

  4. ノードが赤の場合、その子は両方とも黒です

  5. ノードごとに、ノードから子孫の葉へのすべての単純なパスには、同じ数の黒いノードが含まれます

まず、赤黒木は二分木と書いてあります。なぜ彼らは赤黒木が二分探索木だと言わなかったのか. 赤黒ツリーの全体的な目的は、検索ツリーのバランスを維持してlogN操作を保証することだと思いました。次に、なぜ赤黒木の葉がNILなのですか?

通常の二分木では、これに慣れています。

               4
         5            7
    3        2     Nil Nil
 Nil Nil  Nil Nil

この場合、3、2、および 7 がリーフです。CLRS で葉が Nil として描かれているのはなぜですか?

4

1 に答える 1

1

この本では、彼らは赤黒木を二分探索木と呼んでいます。それは章の冒頭にあります。

また、この章では、 とラベル付けされたノードnilが実際のノード (センチネルと呼ばれる) であり、通常のノードと同じフィールドを持つが、color固定値「黒」のフィールドを持つことを示します (他のフィールドは任意の値に設定できます)。これらのノードは、常にツリー内のリーフとして表示されます。そのため、リーフが左側のサブツリーと右側のサブツリーが両方とも であるノードである通常の BST とは異なりますnil。

于 2015-11-08T00:38:10.810 に答える