arrays - 配列を使用した二分木表現

Question

古いノードベースの実装ではなく、バイナリツリーの配列ベースの実装を使用すると、速度/スペース/一般的なパフォーマンスが向上しますか? 配列ベースのツリーのローテーションやその他の複雑な変更は恐ろしいことだと理解していますが、単純なバイナリ ツリーの実装の場合、配列を介して行う方がよいと思いますか?

Answer 1

Binary Heapを探していると思います。

Answer 2

配列ベースのバージョンはヒープ割り当てを使用しないため、すべてがキャッシュに収まる可能性が高く、トラバースに必要な読み取り量を高速化するためのより単純なポインター計算が必要になります。コンパイル時にサイズが制限され、制限されている場合は、より高速なソリューションです。