赤黒木について

空の赤黒木に文字を挿入するときに完成する木は一意に決まりますか？

例）空の赤黒木に5,3,9,1,7,2,8,4,6をこの順に挿入するとき

No.1 ベストアンサー 回答者： stomachman 回答日時： 2023/11/12 10:19

「一意に決ま」るかどうかをお考えだということは、少なくとも同じデータを保持している赤黒木というだけでは一意的でない、ということはお分かりなのだろうと思います。

でも、何の断りもなく「文字を挿入」とおっしゃるところにいささか不安がある。というのは、その「文字」にどんな全順序関係を設定するかで結果が全く異なるからです。でもま、例に挙げてあるのが自然数なので、自然数の普通の大小関係をそのまま全順序関係として利用する、という話（だと自覚なさっているのかどうかは知らないが、おそらくそう）なのでしょう。
　さて、赤黒木の挿入操作を行うアルゴリズム（赤黒木に挿入して結果が赤黒木になるような、計算時間がO(n log(n))の手続き）は複数構成できる。けれども、ご質問は、そのうちひとつの特定のアルゴリズムを選んであって、いつもその同じアルゴリズムで挿入する、という話なんじゃなかろうか。

　仮に、ご質問がそういう意味なのだとすると、（そのアルゴリズムが決定的（サイコロを振らない）でありさえすれば）「この順に挿入するとき」の結果が何度やったって異なるものになりようがないのは、当たり前ですよね。
　ところで、「そのアルゴリズムにおいて、出来る赤黒木は挿入の順番によらず一意的か」という問いを立てたとすると、それは、空の赤黒木に1,2をこの順で挿入するのと、空の赤黒木に2,1をこの順で挿入するのとで同じ結果になるかどうかを考えれば、すぐわかるでしょう。

この回答へのお礼

ありがとうございます

お礼日時：2023/11/18 11:03