binary-search-tree - 高さプロパティを二分探索木に追加する

Question

Set を実装するために使用される Binary Search Tree クラスが与えられました。すべての基本機能、挿入、削除、および特定の値が存在するかどうかのチェックを備えています。ツリーに使用される Node クラスも提供されています。ノードには未使用のクラス変数がありますheight。

class TreeNode{
    .......
    public int height;
    .......
}

これはノード クラスの単純化されたバージョンです。heightここで、各ノードの高さを追跡するために、これを使用してこのクラスの機能を拡張する新しいクラスを作成することになっています。高さは次のとおりです。

• 0、ノードにサブツリーがない場合、
• 空の場合は -1
• 1+ 最大サブツリーの高さ。

ここでの問題は、与えられたコードを変更できないことです。既存のコードの大部分を単純にコピーして、ニーズに合わせて変更することもできません。つまり、スーパー クラス関数を呼び出してからadd()、更新するコードを追加する必要があります。高さ、およびこのコードは、関数全体のランタイムに定数のみを追加する必要があります。super.add()高さを更新するために、呼び出してから、新しく追加された要素の検索パスに沿って移動するソリューションを思いつきました。これは機能しますが、非常に厄介なソリューションです。

私の現在のソリューションは次のように機能します。

• super.add()それ自体が再帰関数であるCall (BST の標準 add 関数)
• 要素が追加されたので、追加された値を受け取り、それを再帰的に検索し、その検索パスに沿って高さ情報を更新するプライベート ヘルパー関数を呼び出します。

何かが欠けているように感じ、精神的な障害に直面しているように感じるので、ここでヒントが欲しいだけです. ソースコードの投稿は控えてください。考えさせられる逆質問の回答もありがたいです。