問題タブ [tree-balancing]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - バランシング ツリーを使用したバッチ操作
私は自己均衡二分探索木を使用しています (現在は AVL 木ですが、別のものに置き換えることができます)。特定の操作のみが実行される明確な期間があることに気付きました。大規模な削除または挿入バッチが実行されることはめったにありませんが、ほとんどの場合、検索ツリーは不変です。リバランスをバッチの最後まで延期すると、パフォーマンスが向上しますか?
data-structures - 自己均衡ツリーまたは高さの低いツリー構造が効率的なリストと抽象的なデータ構造にどのように役立つか
私はAVLツリーについて読んでいて、そこにあるセルフバランシングツリーにリダイレクトしました
コンピューター サイエンスでは、自己均衡型 (または高さのバランスがとれた) 二分探索木は、任意の項目の挿入と削除に直面して、その高さ (ルートの下のレベルの最大数) を自動的に小さく保つノードベースの二分探索木です。1
これらの構造は、変更可能な順序付きリストの効率的な実装を提供し、連想配列、優先キュー、およびセットなどの他の抽象データ構造に使用できます。
よくわかりません
- 高さとリストの関係は？配列？
- 変更可能な順序付きリストの効率的な実装を提供する高さの小さいツリーはどのように提供されますか? 配列？待ち行列？
- リストのノードまたは配列のインデックスがリストまたは配列の高さであると仮定すると、どのように小さいのでしょうか?
java - 二分探索木を再帰的にバランスさせる
私がBinarySearchTree作成したクラスである Instance bankaccount の with オブジェクトがあるので、基本的には単なる binarysearchtree であり、ツリーを取得してバランスをとるメソッドを作成しました。何らかの理由で、バランスの前にツリーを正確に出力します。
さて、最初にcreateListリストと a を取り、それを順番に調べてツリーデータのtree(one node)を作成するメソッドがあるarrayList(DynamicArray)ので、それはソートされた配列です。次に、他の方法を使用して、配列の中央の要素をルートにし、左中央を左サブツリーのルートにし、右中央を右サブツリーのルートにすることで、バランスの取れた方法でツリーを作成します。
何らかの理由で私がこれを行うと：
最初にコンパレータを使用して配列を番号でソートするため、配列は {1,2,3,4,5,6,7,8} になるはずです (これがこのコンパレータの動作です)。ツリーはバランスが取れていますが、同じままです。コードの何が問題なのか分かりますか?
編集:これは私がこれまでに変更したもので、buildBalancedTree は NullpointerException を与えています