K-fix Learning & Playing

アルゴリズムとプログラミング


2分探索木

2分探索木

2分木の構造をデータ構造として利用したものです。

各点にキー(=自然数)を1つ格納
  左の子を根とする部分木に、より小さなキーを格納
  右の子を根とする部分木に、より大きなキーを格納

2分探索木
問題)

キー が与えられたとき、2分探索木上でkを探したい

2分探索木

節の挿入

2分探索木への節の挿入

2分探索木へ点を1つ追加する(※2分探索木の性質が失われないように!)

2分探索木
2分探索木へのデータ挿入

2分探索木へ点を1つ追加する(※2分探索木の性質が失われないように!)

2分探索木

節の削除

2分探索木からデータ削除

2分探索木から点を1つ削除する(※2分探索木の性質が失われないように!)

2分探索木
2分探索木からデータ削除

2分探索木から点を1つ削除する(※2分探索木の性質が失われないように!)

2分探索木