バイナリ検索ツリーの検索操作

Question

バイナリ検索ツリーを効率的に検索するにはどうすればよいか知りたいと思います。

Answer 1

バイナリ検索ツリーを効率的に検索するためには、ツリーはの平衡でなければなりません。つまり、各ノードの左右のサブツリーには、ほぼ同じ数の子ノードがあります。バイナリ探索木が完全に平衡している場合、探索はO（log n）演算である。一方、縮退ツリーは、右側（または左側）のサブツリーにすべてのノードを持っています。検索は、リンクされたリストを検索するようなものです.O（n）。

詳細については、ウィキペディアの記事Binary search treeを参照してください。