[解決済み] 二分探索木におけるk番目の最小要素を最適な方法で探す

質問

二分探索木のk番目の最小要素をスタティック/グローバル変数を使用せずに見つけたい。どのように効率的にそれを達成するのですか？ 私の頭の中にある解決策は、私が木全体の無秩序な横断を行うことを計画しているので、最悪の場合、O（n）で操作を行うことです。しかし、心の底では、私はここでBSTの特性を使っていないと感じています。私の仮定的な解決策は正しいですか、または利用可能なより良いものがありますか？

どのように解決するのですか？

ここでは、アイデアの概要を説明します。

BSTにおいて、左サブツリーのノード T に格納されている値よりも小さい要素のみが格納されています。 T . もし k が左のサブツリーの要素数より小さい場合は k が左の部分木の要素数より小さい場合、最小の要素は左の部分木に属さなければならない。そうでなければ、もし k が大きい場合は k が大きい場合、最小の要素は右のサブツリーにある。

BSTを拡張して、その中の各ノードにその左サブツリーの要素数を格納させることができます（与えられたノードの左サブツリーはそのノードを含むと仮定します）。この情報により、左サブツリーまたは右サブツリーのどちらに再帰するかを決定するために、左サブツリーの要素数を繰り返し尋ねることによって、ツリーを簡単にたどることができるようになります。

さて、私たちがノードTにいるとします。

1. もし k == num_elements(Tの左サブツリー) であれば、探している答えは、ノード T .
2. もし k > num_elements(Tの左サブツリー) の場合、明らかに左のサブツリーを無視できます。なぜなら、それらの要素も k よりも小さいからです。そこで、この問題を k - num_elements(left subtree of T) 右のサブツリーの最小の要素を見つけることです。
3. もし k < num_elements(Tの左サブツリー) であれば k の最小値は左部分木のどこかにあるので、問題は k の最小の要素を見つけることに問題を軽減します。

複雑さの解析。

これには O(depth of node) の時間であり、これは O(log n) であり、バランスのとれた BST では最悪の場合 O(log n) となります。

BSTには O(n) ストレージを必要とし、さらに O(n) を利用して要素数に関する情報を格納する。すべてのBST操作は O(depth of node) の時間を要し、また O(depth of node) の時間がかかり、ノードの挿入、削除、回転のために "要素数"の情報を維持するために余分な時間がかかる。したがって、左のサブツリーの要素数に関する情報を保存することで、BSTの空間と時間の複雑さを維持することができます。