codes/ruby/chapter_tree/binary_search_tree.rb - main - githubmirror/hello-algo

codes/ruby/chapter_tree/binary_search_tree.rb
161 строка4 KB
khoaxuantu
feat: add ruby codes - chapter tree (#1288)
19 апр 2024, 10:50
19 апр 2024, 10:5019488b1
=begin
File: binary_search_tree.rb
Created Time: 2024-04-18
Author: Xuan Khoa Tu Nguyen (ngxktuzkai2000@gmail.com)
=end

require_relative '../utils/tree_node'
require_relative '../utils/print_util'

### 二叉搜索树 ###
class BinarySearchTree
  ### 构造方法 ###
  def initialize
    # 初始化空树
    @root = nil
  end

  ### 获取二叉树根节点 ###
  def get_root
    @root
  end

  ### 查找节点 ###
  def search(num)
    cur = @root

    # 循环查找，越过叶节点后跳出
    while !cur.nil?
      # 目标节点在 cur 的右子树中
      if cur.val < num
        cur = cur.right
      # 目标节点在 cur 的左子树中
      elsif cur.val > num
        cur = cur.left
      # 找到目标节点，跳出循环
      else
        break
      end
    end

    cur
  end

  ### 插入节点 ###
  def insert(num)
    # 若树为空，则初始化根节点
    if @root.nil?
      @root = TreeNode.new(num)
      return
    end

    # 循环查找，越过叶节点后跳出
    cur, pre = @root, nil
    while !cur.nil?
      # 找到重复节点，直接返回
      return if cur.val == num

      pre = cur
      # 插入位置在 cur 的右子树中
      if cur.val < num
        cur = cur.right
      # 插入位置在 cur 的左子树中
      else
        cur = cur.left
      end
    end

    # 插入节点
    node = TreeNode.new(num)
    if pre.val < num
      pre.right = node
    else
      pre.left = node
    end
  end

  ### 删除节点 ###
  def remove(num)
    # 若树为空，直接提前返回
    return if @root.nil?

    # 循环查找，越过叶节点后跳出
    cur, pre = @root, nil
    while !cur.nil?
      # 找到待删除节点，跳出循环
      break if cur.val == num

      pre = cur
      # 待删除节点在 cur 的右子树中
      if cur.val < num
        cur = cur.right
      # 待删除节点在 cur 的左子树中
      else
        cur = cur.left
      end
    end
    # 若无待删除节点，则直接返回
    return if cur.nil?

    # 子节点数量 = 0 or 1
    if cur.left.nil? || cur.right.nil?
      # 当子节点数量 = 0 / 1 时， child = null / 该子节点
      child = cur.left || cur.right
      # 删除节点 cur
      if cur != @root
        if pre.left == cur
          pre.left = child
        else
          pre.right = child
        end
      else
        # 若删除节点为根节点，则重新指定根节点
        @root = child
      end
    # 子节点数量 = 2
    else
      # 获取中序遍历中 cur 的下一个节点
      tmp = cur.right
      while !tmp.left.nil?
        tmp = tmp.left
      end
      # 递归删除节点 tmp
      remove(tmp.val)
      # 用 tmp 覆盖 cur
      cur.val = tmp.val
    end
  end
end

### Driver Code ###
if __FILE__ == $0
  # 初始化二叉搜索树
  bst = BinarySearchTree.new
  nums = [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]
  # 请注意，不同的插入顺序会生成不同的二叉树，该序列可以生成一个完美二叉树
  nums.each { |num| bst.insert(num) }
  puts "\n初始化的二叉树为\n"
  print_tree(bst.get_root)

  # 查找节点
  node = bst.search(7)
  puts "\n查找到的节点对象为: #{node}，节点值 = #{node.val}"

  # 插入节点
  bst.insert(16)
  puts "\n插入节点 16 后，二叉树为\n"
  print_tree(bst.get_root)

  # 删除节点
  bst.remove(1)
  puts "\n删除节点 1 后，二叉树为\n"
  print_tree(bst.get_root)

  bst.remove(2)
  puts "\n删除节点 2 后，二叉树为\n"
  print_tree(bst.get_root)

  bst.remove(4)
  puts "\n删除节点 4 后，二叉树为\n"
  print_tree(bst.get_root)
end