重複の可能性:
最大ヒープを二分探索木に変換する
追加のスペースを使用せずに、可能な限り効率的に最小ヒープを二分探索木に変換します。(再帰が許可されます)。
この質問は私を夢中にさせてきました。min-heap プロパティを使用して、力ずくよりも効率的にこれを行う方法が必要です。たとえば、次の最小ヒープが与えられた場合:
[1, 7, 6, 9, 8, 21, 15] =
1
/ \
7 6
/ \ / \
9 8 21 15
定義により、ルートは二分探索ツリーの一番左のノードになることがすぐにわかります。また、最小ヒープ内の任意のノードの右の子が BST プロパティ (parent.right > parent) に違反しないこともわかっています。
これらの事実を利用して、BST をインプレースで効率的に作成するにはどうすればよいでしょうか?