2分探索木とはなにか？図で理解する

2分探索木は、各々の節点ごとにキーを持ち、2分探索木条件を常に満たすように構築された木です。

2分探索木条件とは、ある節点の左の木が兄弟の右の木やその節点よりも必ず低い値をもつなどの
一定の条件を満たす木のことです。
では、例を見ていきましょう

            30

  12           88

1  20
 
    7  25

この木の条件を例に見ると
キーが30の根の左部分木に該当するキーは全て30以下になっています。
右部分木に属する節点のキーは左部分木よりも大きいという条件が成り立っていることがわかります。
これが2分探索木になります。