avl-tree - AVL ツリーへの追加

Question

AVL ツリーに値を追加する場合、どこに挿入すればよいですか? 私はコーディングの側面について話しているのではなく、より絵的な表現について話しているのです。挿入は最初に利用可能な外部ノードで行われると想定していますが、私の教科書に示されている例ではランダムな外部ノードに挿入されているため、確信が持てません。

Answer 1

AVL ツリーは自己均衡バイナリ サーチ ツリーであり、バイナリ サーチ ツリーには次のプロパティがあります。すべてのノードの左側のサブツリーには、ノードのキーよりも小さいキーを持つノードのみが含まれ、すべてのノードの右側のサブツリーには、ノードのキーよりも大きいキーを持つノードのみが含まれます。キー。そのため、挿入後に指定されたプロパティが残るように新しいノードを挿入する必要があります。ルート ノードから開始し、新しいノード キーと現在のノード キーを比較して、新しいノード キーの方が大きい場合は右の子にアクセスし、それ以外の場合は左にアクセスします。その場所に訪問する子がいない場合は、新しいノードを挿入します。