概要
概要
二分探索木は、各ノードで左部分木の値が小さく、右部分木の値が大きい構造です。探索・挿入の考え方を木として学べます。
データ構造 / Binary Search Tree（二分探索木）
二分探索木は、各ノードで左部分木の値が小さく、右部分木の値が大きい構造です。探索・挿入の考え方を木として学べます。
目次
このページでわかること
概要
二分探索木は、各ノードで左部分木の値が小さく、右部分木の値が大きい構造です。探索・挿入の考え方を木として学べます。
考え方
if x < node then go left
if x > node then go right
insert at null child要点
O(log n)
O(n)
順序性
偏ると遅い
補足
各ノードで片側だけ見ればよいからです。
偏った木になると線形に近づきます。
AVL や赤黒木へつなげられます。
動きで確認
ここでは「何が制約か」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。