二分探索木

二分探索木

二分探索木(BST)は、順序付きノードベースの二分木データ構造です。ノードは、値と 2つの子ノード(二分木は最大 2つの子ノードを持ちます)を左右に持ちます。ルートノードを除いて、すべてのノードは親ノードのみが参照できます。BST は以下のような性質を持っています。 左サブツリーのすべてのノードはルートノードよりも小さい。 右サブツリーのすべてのノードはルートノードよりも大きい。 左と右のサブツリーも二分探索木でなければなりません。 左側の木は BST の性質をすべて満たしています。一方、右側の木は、左のサブツリーのノードがすべて小さく、右のサブツリーのノードがすべて大きくなっており、BST のように見えます。しかし、左サブツリーのノード 1 は、ノード 4 よりは小さいが、ルートノード 3 よりは大きくないので、BST の性質を満たしていません。したがって、これは BST ではありません。

人気記事

最新記事