木構造

概要

リストを使って表現できる

子ノードは親ノードを1つしか持たない

探索効率は木の高さに大きく影響を受ける

二分探索木

順序木

子コードは2つ以下

左部分木にあるすべてのノードのキー(key)は、それの親ノードのキーよりも小さい(または大きい)

右部分木にあるすべてのノードのキー(key)は、それの親ノードのキーよりも大きい(または小さい)

探索，挿入，削除の計算量

最良でO(log2n)

最悪でO(n)

木みたいになってないとき（全部右 or 全部左で要素探索したとき）

平衡木

挿入や削除等で木の形が変わったときに、高さがlon2n程度に収まるように木を変形させる

2-3木

内部ノードは2 - 3個の子ノードをもつ

左部分木、中部分木、右部分木となる

右部分木がない場合もある

内部ノードは、key1 と key2を持つ

中部分木の中で最小のキーをkey1にいれる

右部分木の中で最小のキーをkey2にいれる。右部分木がなかったらNULLを入れる

key1 と key2を使って、要素との大小関係を比較して、どの木にあるのかをたどっていく

葉ノードだけバリューをもつ

ヒープ

二分探索木よりもゆるい規則の順序木

親ノード≧子ノード(または親ノード≦子ノード)

最大値(または最小値)をもつノードが根(ルート)にある

ノードの挿入

葉ノードの一番右側に挿入

親ノードと比較して必要に応じて入れ替え

入れ替えた結果に対して、更に入れ替えが必要かも見ていく

ノードの取り出し（削除）

ルートノードを取り出す

葉ノードの一番右側を空席になったルートに持ってくる

親ノードと子ノードを比較して、必要に応じて入れ替え

配列でヒープを簡単に表現できる

親ノードの添え字をkとすると

左の子の添え字は2k

右の子の添え字は2k+1

詳しくは以下

素集合データ構造