問題タブ [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.
c++ - 正しい反復子のヒントを提供した場合、マップ/セット :: 挿入の複雑さは何ですか?
それはO(1)またはO(logN)ですが、係数は小さいですか?
これが指定されていない場合は、マップ/セットが赤黒または AVL ツリーを使用して実装されているという合理的な仮定に基づいて、少なくとも答えを知りたいと思います。要素を挿入する一般的なアルゴリズムは、次のようなものだと思います。
- 適切な場所を見つける - O(logN)
- 実際の挿入を行います - ?
- 必要に応じてツリーのバランスを取り直します - ?
正しい反復子ヒントを提供すると、最初のステップはO(1)になります。他のステップもO(1)またはO(logN)ですか?
java - BST Java へのソートされた単一リンクリスト
現在、並べ替えられたリンク リストがあり、void リターン メソッドを使用して、リスト (2 番目のパラメーターと呼ばれます) からバランスのとれた二分探索木を再帰的に構築する必要があります。パラメータとして、LL ヘッド、作成されるルート、およびリストの長さのみを指定できます。
このメソッドは LL に対して破壊的であってはならず、後でツリーをテストするために、printTree と treeDepth があります。
avl-tree - AVL ツリーの完全なバランスの問題
AVL ツリーの再調整に根本的な問題があるかどうか疑問に思っています。いくつかのチュートリアルによると、AVL 挿入の場合、最大 2 回転でバランスを取ることができます。ただし、バランスと呼ばれるものに依存する場合があります。ツリーを見るにはリンクをたどってください。
もともとは6つの要素を持っています。最後の値を 3 または 4.5 または 5.5 または 6.5 として挿入したとします。とにかく、下の左側に挿入されます。合計 7 要素ツリーなので、バランスをとるために 3 行のみと見なします。
これにより、新しいルートが強制的に 6 または 6.5 になります (6.5 を挿入した場合)。2回転以内にバランスを取り戻す方法が本当にわかりません。「バランス」の定義のみに依存する場合、4 行は依然としてバランスが取れていると呼ばれますが、検索時間が長くなります。
何か不足していますか?
写真が削除された場合に備えて、以下はテキスト バージョンです。
algorithm - 赤黒木は、バランスを取り直すときに葉の左から右への順序を変更しますか?
つまり、挿入直後に赤黒の木の葉の値を左から右に読み取った場合、その順序は木でバランシング操作を実行した後も同じままでしょうか?
java - 部分木の平衡度から木が平衡であることを証明する
「Cracking the Coding Interview」から次の問題を解決しています: 二分木のバランスが取れているかどうかをチェックする関数を実装します。バランスの取れたツリーとは、ノードの 2 つのサブツリーの高さの差が 1 を超えないようなツリーです。
本のサンプル ソリューション (以下にコピー) では、(a) ノードの左と右のサブツリーのバランスが取れている場合、ノードから発するツリーのバランスが取れていると想定しています。(b) ノード自体のバランスがとれている。なぜこれが事実なのか理解しようとしていますか?上記の 2 つの条件が満たされていることは、ノードから発するツリー全体のバランスが取れていることをどのように証明しますか?
ありがとう