Javascript
 Computer >> コンピューター >  >> プログラミング >> Javascript

JavascriptのAVLツリー

AVLツリー（発明者のAdelson-VelskyとLandisにちなんで名付けられました）は、自己平衡二分探索木です。自己平衡ツリーは、サブツリー内で回転を実行するツリーであり、左側と右側の両方でバランスをとることができます。

これらの木は、挿入によって片側の木が重くなる場合に特に役立ちます。バランスの取れたツリーは、O（n）側に傾く完全にアンバランスなツリーとは対照的に、ルックアップ時間をO（log（n））に近づけます。


  1. JavaScriptでツリー化するオブジェクトのフラット配列

    このようなオブジェクトの配列があるとします- const arr = [    { id: '1', name: 'name 1', parentId: null },    { id: '2', name: 'name 2', parentId: null },    { id: '2_1', name: 'name 2_1', parentId: '2' },    { id: '2_2

  2. AVLツリーを実装するためのC++プログラム

    AVLツリーは自己平衡二分探索木であり、左右のサブツリーの高さの差がすべてのノードで複数になることはありません。 ツリーの回転は、AVLツリーの要素の順序を妨げることなく構造を変更する操作です。ツリー内で1つのノードを上に移動し、1つのノードを下に移動します。これは、ツリーの形状を変更したり、小さいサブツリーを下に移動したり、大きいサブツリーを上に移動したりして高さを低くしたりするために使用され、多くのツリー操作のパフォーマンスが向上します。回転の方向は、木のノードが移動する側に依存しますが、他の人は、どの子がルートの場所をとるかに依存すると言います。これは、AVLツリーを実装するためのC+