二叉搜索树（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 为根节点，新节点为其左子节点。

插入

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

新节点与包含若干元素的二叉搜索树图示。current_node 为根的右子节点，新节点为 current_node 的左子节点。

删除

无子节点

含若干元素的二叉搜索树图示。将被删除的节点为红色，无子节点。

删除

无子节点
- 直接删除

含若干元素的二叉搜索树图示。要删除的节点已从树中消失。

删除

有一个子节点

含若干元素的二叉搜索树图示。将被删除的节点为红色，且有右子节点。

删除

有一个子节点
- 删除该节点
- 将其子节点与其父节点相连

含若干元素的二叉搜索树图示。被删除的节点已消失，根节点指向其右子节点。

删除

有一个子节点
- 删除该节点
- 将其子节点与其父节点相连

二叉搜索树示意图。

删除

有两个子节点

二叉搜索树图示，根节点将被删除并标为红色。

删除

有两个子节点
- 用其后继替换
  - 比该节点值更大且最小的节点
- 寻找后继：

二叉搜索树图示，根节点将被删除并标为红色。

删除

有两个子节点
- 用其后继替换
  - 比该节点值更大且最小的节点
- 寻找后继：
  - 访问右子节点

二叉搜索树图示，根节点将被删除并标为红色。根的右子节点为黄色。

删除

有两个子节点
- 用其后继替换
  - 比该节点值更大且最小的节点
- 寻找后继：
  - 访问右子节点
  - 不断向左直到末端

二叉搜索树图示，根节点将被删除并标为红色。另一个节点为黄色以寻找后继。

删除

有两个子节点
- 用其后继替换
  - 比该节点值更大且最小的节点
- 寻找后继：
  - 访问右子节点
  - 不断向左直到末端

二叉搜索树图示，根节点将被删除并标为红色。另一个节点为黄色以寻找后继。

删除

有两个子节点
- 用其后继替换
  - 比该节点值更大且最小的节点
- 寻找后继：
  - 访问右子节点
  - 不断向左直到末端

二叉搜索树图示，根节点将被删除并标为红色。另一个节点为黄色以寻找后继。已找到后继，为数字 13。

删除

有两个子节点
- 用其后继替换
  - 比该节点值更大且最小的节点
- 寻找后继：
  - 访问右子节点
  - 不断向左直到末端

二叉搜索树图示。根节点已被后继替换。

删除

有两个子节点
- 用其后继替换
  - 比该节点值更大且最小的节点
- 寻找后继：
  - 访问右子节点
  - 不断向左直到末端
  - 若后继有右子节点：

二叉搜索树图示，后继节点有右子节点。

删除

有两个子节点
- 用其后继替换
  - 比该节点值更大且最小的节点
- 寻找后继：
  - 访问右子节点
  - 不断向左直到末端
  - 若后继有右子节点：
    - 该子节点成为后继父节点的左子节点。

二叉搜索树图示，后继节点曾有右子节点。该子节点已成为后继父节点的左子节点，根已替换为后继。

用途

高效有序地存储列表
查找比数组和链表快得多
插入和删除比数组快得多
用于实现更高级的数据结构：
- 动态集合
- 查找表
- 优先队列

开始练习吧！

Python 中的数据结构与算法