配列の要素の差が、最大値になる値を探す問題です。 ただし、配列の値が、「後から先」へは計算できるが「先から後」へは計算できない。 x = array[i] y = array[j] x - y が最大になる値を求める。だたし、「i > j」でなければならない 実際のコード例
アルゴリズムとデータ構造1の質問 - Qiita
配列の要素の差が、最大値になる値を探す問題です。 ただし、配列の値が、「後から先」へは計算できるが「先から後」へは計算できない。 x = array[i] y = array[j] x - y が最大になる値を求める。だたし、「i > j」でなければならない 実際のコード例
AVL Tree by Java -- これで分かったAVL木
AVL木(AVL Tree)は、 マップ(連想配列)と呼ばれるデータ構造の実装に使われる平衡木の１つです。 平衡木では木のバランスが適度にとれており、 キーの検索・要素の挿入・削除などの処理が、いかなる場合でも \(O(\log n)\) の計算量で行えます(\(n\) は要素数)。 AVL木の他にも 赤黒木 という平衡木がありますが、 AVL木は赤黒木に比べてより厳密に平衡性を維持しようとします。つまり、 よりバランスがとれているということです。 そのため赤黒木より検索の性能が良いとされています。 ただし、挿入や削除ではより手間がかかります。 本ページは、AVL木の実装に関して詳しく解説しています。 他のサイトでは省略されてしまっているような回転の場合分けについてもやさしく解説してあります。 その他にも、何故そうするの？という疑問に対して、 なるたけ答えるように書いたつもりですので、是非
AVL木の回転(要素の挿入や削除のしかた) - Qiita
回転 回転の対象とその高い方の子で子の高さの差の符号が異なる場合(0は含まない)は、まず子を木の外側(左の子なら左回転、右の子なら右回転)に回転する。その後、回転の対象の回転を行って子の高さの差の絶対値を減らす。 挿入後回転が発生した場合は、木の高さは変わらない。 削除後回転が発生した場合は、高い方の子の子の高さの差が0のときは木の高さは変わらず、そうでないときは木の高さが減る。 実装の工夫 子の高さの差の更新を回転処理に含めることで、挿入や削除では子の高さの差の更新を意識せず、現在の子の高さの差を見て回転操作を行うだけでよくなった。 「要素の追加や削除による高さの更新」と「木の回転によるバランスの調整」を分けて考えることで、回転操作の制御を挿入と削除で共通にすることができた。 実装例 要素の重複を許さないAVL木の、C言語による実装例である。 rotate()関数は、is_rightが真
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
半永続B木 (和訳) - Qiita
Amazon.co.jp: プログラミングコンテスト攻略のためのアルゴリズムとデータ構造: 渡部有隆 (著), Ozy（協力） (その他), 秋葉拓哉（協力） (その他): Digital Ebook Purchas
アルゴリズムとデータ構造
