2014-04-06から1日間の記事一覧

破壊操作型 AVL 木

制約条件「すべてのノードについて、左右の部分木の高さの差を 1 に収めた」木が AVL 木です。1962 年に発表された AVL 木は、挿入・削除・探索のすべてで O(log n) を満たす最初に発見された 2 分探索木であり、それらを満たす最も制約が厳しい 2 分探索木…