AVLツリーで次の表記/操作を想定します。空のAVLツリーはEで示されます。空でないAVLツリーTには、次の3つの属性があります。
•キーT.keyは、ルートノードのキーです。
•左の子T.leftは、AVLツリー（おそらくE）であるTの左サブツリーです。
•右の子T.rightは、AVLツリー（おそらくE）であるTの右サブツリーです。
キー値がlo≤key≤hiの範囲にあるルートTのAVLツリー内のノードの数をカウントして返すアルゴリズム（擬似コードで実行）Count（T、lo、hi）を作成しようとしています。 。時間計算量O（n）を持たせたいのですが、nはAVLツリーTのノード数です。私が持っていたアイデアの1つは再帰でしたが、これには必要な複雑さがなかったようです。何か案は？
カウンターのようなグローバル変数を追加し、事前注文でツリーを反復することができます。これには（n + e）のコストがかかり、ノードごとに1を追加します。
カウンターを追加することもできます。データ構造内に新しいノードを追加する場合は1を追加でき、ノードを削除すると1を減算できます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加