[xyzzy:00125] Re: バージョンアップのお知らせ

[Tetsuya Kamei <kamei@xxxxxxxxxxxx>]

    Mon, 10 Aug 1998 13:41:33 +0900 の
   “[xyzzy:00124] Re: バージョンアップのお知らせ”
    への返事です.

| 赤黒木みたいな物？

赤黒木は名前しか知りません(^^;

AVLは、例えば 1, 2, 3... を追加するとき、単純にくっ付けていくと、

    1             1                 1
          →        ＼      →        ＼
                       2                 2
                                           ＼
                                              3

てなことになって、「どこがツリーやねん」と突っ込まれてしまうので、

    1            1               2              2                 2
          →       ＼     →   ／ ＼    →    ／ ＼      →     ／ ＼
                      2       1     3        1     3           1     4
                                                     ＼            ／  ＼
                                                       4          3       5

このように木を変形しながら追加していくことで、「リストちゃうんか」と突っ
込まれるのを防ぐためのアルゴリズムです(^^;

--
亀井哲弥(Tetsuya Kamei)
kamei@xxxxxxxxxxxx/JCA00343@xxxxxxxxxxx