二分探索木（BST）

Pythonで学ぶデータ構造とアルゴリズム

Miriam Antona

Software engineer

定義

ノードの左部分木:
- ノード自身より小さい値
ノードの右部分木:
- ノード自身より大きい値
左右の部分木も二分探索木であること

二分探索木の模式図。

実装

class TreeNode:  
  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

class BinarySearchTree:
  def __init__(self):
    self.root = None

探索

72 を探索

二分探索木の模式図。

探索

72 を探索

根ノードが黄色の二分探索木の模式図。

探索

72 を探索

根ノードとその左部分木が灰色、右部分木の最初のノードが黄色の二分探索木の模式図。

探索

72 を探索

二分探索木の模式図。直前の根ノードとその左部分木が灰色、新しい根ノードが黄色。

探索

72 を探索

新しい根ノードが黄色、他は灰色の二分探索木の模式図。

探索

72 を探索

新しい根ノードが黄色、他は灰色の二分探索木の模式図。色付きノードは 72 で強調表示。

探索

def search(self, search_value):

    current_node = self.root

    while current_node:

      if search_value == current_node.data:

        return True

      elif search_value < current_node.data:

        current_node = current_node.left_child

      else:

        current_node = current_node.right_child

    return False

挿入

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

新しいノードの図示。

挿入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return

新しいノードが根になった図。

挿入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:

新しいノードと、右子を持つ根ノードの図。

挿入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root

    while True:

      if data < current_node.data:

        if current_node.left_child == None:

新しいノードと右子を持つ根ノードの図。current_node は根。

挿入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return

右子と左子を持つ根ノードの図。current_node は根。new_node は左子。

挿入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:

新しいノードといくつかの要素を持つ二分探索木の図。current_node は根。

挿入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child

新しいノードといくつかの要素を持つ二分探索木の図。current_node は根の左子。

挿入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:

        if current_node.right_child == None:

左部分木を持つ二分探索木の図。

挿入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return

左部分木を持つ二分探索木の図。new_node は根の右子になった。

挿入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:

新しいノードと、いくつかの要素を持つ二分探索木の図。

挿入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

新しいノードといくつかの要素を持つ二分探索木の図。current_node は根の右子。

挿入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return 
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

新しいノードといくつかの要素を持つ二分探索木の図。current_node は根の右子。new_node は current_node の左子。

削除

子なし

いくつかの要素を持つ二分探索木の図。削除予定のノードが赤色で表示。子はない。

削除

子なし
- 削除

いくつかの要素を持つ二分探索木の図。削除されたノードが木から消えている。

削除

子が1つ

いくつかの要素を持つ二分探索木の図。削除予定のノードが赤色。右子を持つ。

削除

子が1つ
- 削除
- 子をノードの親に接続

いくつかの要素を持つ二分探索木の図。削除ノードが消え、根がその右子を指す。

削除

子が1つ
- 削除
- 子をノードの親に接続

二分探索木の図。

削除

子が2つ

根ノードを削除予定で赤色の二分探索木の図。

削除

子が2つ
- 後継で置換
  - ノード値より大きい中で最小のノード
- 後継の見つけ方:

根ノードを削除予定で赤色の二分探索木の図。

削除

子が2つ
- 後継で置換
  - ノード値より大きい中で最小のノード
- 後継の見つけ方:
  - 右子へ進む

根ノードが赤、根の右子が黄色の二分探索木の図。

削除

子が2つ
- 後継で置換
  - ノード値より大きい中で最小のノード
- 後継の見つけ方:
  - 右子へ進む
  - 左へ末端まで辿る

根ノードが赤、後継探索用の別ノードが黄色の二分探索木の図。

削除

子が2つ
- 後継で置換
  - ノード値より大きい中で最小のノード
- 後継の見つけ方:
  - 右子へ進む
  - 左へ末端まで辿る

根ノードが赤、後継探索用の別ノードが黄色の二分探索木の図。

削除

子が2つ
- 後継で置換
  - ノード値より大きい中で最小のノード
- 後継の見つけ方:
  - 右子へ進む
  - 左へ末端まで辿る

根ノードが赤、後継探索用の別ノードが黄色の二分探索木の図。後継は 13。

削除

子が2つ
- 後継で置換
  - ノード値より大きい中で最小のノード
- 後継の見つけ方:
  - 右子へ進む
  - 左へ末端まで辿る

根ノードが後継に置き換わった二分探索木の図。

削除

子が2つ
- 後継で置換
  - ノード値より大きい中で最小のノード
- 後継の見つけ方:
  - 右子へ進む
  - 左へ末端まで辿る
  - 後継に右子がある場合:

後継ノードに右子がある二分探索木の図。

削除

子が2つ
- 後継で置換
  - ノード値より大きい中で最小のノード
- 後継の見つけ方:
  - 右子へ進む
  - 左へ末端まで辿る
  - 後継に右子がある場合:
    - その子を後継の親の左子にする

後継に右子があった二分探索木の図。後継の子が後継の親の左子となり、根が後継に置換。

用途

リストを効率よく整列
配列や連結リストより探索が高速
挿入・削除が配列より高速
高度なデータ構造の実装に利用:
- 動的集合
- ルックアップテーブル
- 優先度付きキュー

Let's practice!

Pythonで学ぶデータ構造とアルゴリズム