二分探索木

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。新しいノードは左の子です。

挿入

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

二分探索木の左部分木を示す図。新しいノードは、現在ルートの右の子。

挿入

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

新しいノードといくつかの要素がついた二分探索木の図示。 currentnodeはルートの右の子。新しいノードはcurrentnodeの左の子。

削除

子なし

いくつかの要素が入った二分探索木。ノードの1つは、削除されるため赤色で表示されている。このノードには子ノードがない。

削除

子なし
- 削除する

いくつかの要素が入った二分探索木。削除される予定だったノードはツリーから消える。

削除

子1つ

いくつかの要素が入った二分探索木。ノードの1つは、削除されるため赤色で表示されている。このノードには右の子がある。

削除

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

いくつかの要素が入った二分探索木。削除される予定だったノードは木から消え、ルートノードは削除されたノードの右の子を指している。

削除

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

二分探索木の図示。

削除

子2つ

削除される予定のルートノードが赤色で示された二分探索木の図。

削除

子2つ
- 別のノードに置き換える
  - そのノードの値より大きい値の中で、最も小さい値のノード
- 置き換え先を見つける：

削除される予定のルートノードが赤で示された二分探索木の図。

削除

子2つ
- 別のノードに置き換える
  - そのノードの値より大きい値の中で、最も小さい値のノード
- 置き換え先を見つける：
  - 右の子を訪問する

二分探索木の図。ルートノードが削除されようとしており、赤で示されている。ルートの右の子は黄色で色付けされている。

削除

子2つ
- 別のノードに置き換える
  - そのノードの値より大きい値の中で、最も小さい値のノード
- 置き換え先を見つける：
  - 右の子を訪問する
  - 左のノードを最後までたどり続ける

二分探索木の図。ルートノードが削除されようとしており、赤で示されている。後続ノードを見つけるために、別のノードが黄色で色付けされている。

削除

子2つ
- 別のノードに置き換える
  - そのノードの値より大きい値の中で、最も小さい値のノード
- 置き換え先を見つける：
  - 右の子を訪問する
  - 左のノードを最後までたどり続ける

削除

子2つ
- 別のノードに置き換える
  - そのノードの値より大きい値の中で、最も小さい値のノード
- 置き換え先を見つける：
  - 右の子を訪問する
  - 左のノードを最後までたどり続ける

二分探索木の図。ルートノードが削除されようとしており、赤で示されている。別のノードは、後続ノードを見つけるために黄色で色付けされている。後継ノードの13が見つかる。

削除

子2つ
- 別のノードに置き換える
  - そのノードの値より大きい値の中で、最も小さい値のノード
- 置き換え先を見つける：
  - 右の子を訪問する
  - 左のノードを最後までたどり続ける

二分探索木の図解。ルートノードは後続ノードに置き換えられる。

削除

子2つ
- 別のノードに置き換える
  - そのノードの値より大きい値の中で、最も小さい値のノード
- 置き換え先を見つける：
  - 右の子を訪問する
  - 左のノードを最後までたどり続ける
  - 置き換えたノードに右の子ノードがある場合：

右の子を持つ後続ノードがある二分探索木の図示。

削除

子2つ
- 別のノードに置き換える
  - そのノードの値より大きい値の中で、最も小さい値のノード
- 置き換え先を見つける：
  - 右の子を訪問する
  - 左のノードを最後までたどり続ける
  - 置き換えたノードに右の子ノードがある場合：
    - 子は置き換えたノードの親の左の子ノードになる

二分探索木の図。後続ノードに右の子がある。後継ノードの子は後継ノードの親の左の子となり、ルートノードは後継ノードに置き換えられる。

用途

リストを効率良く並べ替える
配列や連結リストよりも検索がはるかに高速
配列よりも挿入・削除もはるかに高速
より高度なデータ構造を実装するために使用：
- 動的なデータセット
- ルックアップテーブル
- 優先度付きキュー

練習しましょう！

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

二分探索木

**定義**

コード

探索

探索

探索

探索

探索

探索

探索

挿入

挿入

挿入

挿入

挿入

挿入

挿入

挿入

挿入

挿入

挿入

挿入

削除

削除

削除

削除

削除

削除

削除

削除

削除

削除

削除

削除

削除

削除

用途

練習しましょう！

定義