重軽分解

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /heavy-light-decomposition#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /heavy-light-decomposition#noredirect を利用してください。
name
重軽分解
short description
重軽分解とは、根付き木をパスの集合へ分解するテクニックのひとつである。根から始まる最も長いパスをひとつ選んで削除することを再帰的に行う。元々の根付き木上の親子関係によって分解されたパスの集合に木構造を入れたとき、元々の木の高さを $h$ とすると分解されてできた木の高さが $O(\log h)$ になることを特徴とする。