JavaScript二元搜尋樹構建操作詳解

2022-07-13 18:01:24

前言

前面我們介紹了二元樹這個資料結構以及二元樹的遍歷演演算法，這篇文章我們來學習一下一個特殊的二元樹——二元搜尋樹（BST Binary Search Tree），也叫二叉排序樹、二叉查詢樹。

什麼是二元搜尋樹

二元搜尋樹首先它是一棵二元樹，而且還滿足下面這些特質：

對於任何一個非空節點來說，它左子樹上的值必須小於當前值；
對於任何一個非空節點來說，它右子樹上的值必須大於當前值；
任何一顆子樹滿足上面的條件；

如下圖所示：

上圖就是一顆二元搜尋樹，我們就拿根節點來說，根節點的值71，它的左子樹的值分別是22、35、46、53和66，這幾個都是滿足左子樹小於當前值；它的右子樹的值分別是78、87和98，這幾個值是滿足右子樹大於當前值的；以此類推，所以上圖就是一棵二元搜尋樹。

根據二元搜尋樹的特質，我們還能得到以下結論：

二元搜尋樹的任何一個節點的左子樹、右子樹都是一顆二元搜尋樹；
二元搜尋樹的最小的節點是整顆樹的最左下角的葉子節點；
二元搜尋樹的最大的節點是整棵樹的最右下角的葉子節點；

構建一顆二元搜尋樹

我們現在使用JavaScript來構建一顆二元搜尋樹，要知道一顆二元搜尋樹也是由一個一個節點組成，這裡我們通過class建立一個節點類，

範例程式碼如下：

class BinarySearchTree {
  constructor() {
    // 初始化根節點
    this.root = null
  }

  // 建立一個節點
  Node(val) {
    return {
      left: null, // 左子樹
      right: null, // 右子樹
      parent: null, // 父節點
      val,
    }
  }
}

這裡一個節點由四部分組成，分別是指向左子樹的指標、指向右子樹的指標、指向父節點的指標以及當前值。

二元搜尋樹的操作

關於二元樹的遍歷操作我們在上一篇文章中已經介紹了，這裡不在重複，這裡主要介紹如下操作：

插入操作
查詢操作
刪除操作

向二元搜尋樹中插入資料

向一個二元搜尋樹插入資料實現思路如下：

判斷root是否為空，如果為空則建立root；
如果root非空，則需要判斷插入節點的val比根節點的val是大還是小；
如果比根節點小，說明是左子樹的節點；
如果比根節點大，說明是右子樹的節點；
上面兩步重複執行，直到找到一個點，如果這個點小於我們要插入的值，且不存在右子樹，將這個點作為其右葉子節點；如果這個點大於我們要插入的值，且不存在右子樹，將這個點作為其左葉子節點。

範例程式碼如下：

// 建立要給插入節點的方法
insertNode(val) {
  const that = this
  // 允許接受一個陣列，批次插入
  if (Object.prototype.toString.call(val) === '[object Array]') {
    val.forEach(function (v) {
      that.insertNode(v)
    })
    return
  }
  if (typeof val !== 'number') throw Error('插入的值不是一個數位')
  const newNode = this.Node(val)
  if (this.root) {
    // 根節點非空
    this.#insertNode(this.root, newNode)
  } else {
    // 根節點是空的，直接建立
    this.root = newNode
  }
}
// 私有方法，插入節點
#insertNode(root, newNode) {
  if (newNode.val < root.val) {
    // 新節點比根節點小，左子樹
    if (root.left === null) {
      // 如果左子樹上沒有內容，則直接插入，如果有，尋找下一個插入位置
      root.left = newNode
      root.left.parent = root
    } else {
      this.#insertNode(root.left, newNode)
    }
  } else {
    // 新節點比根節點大，右子樹
    if (root.right === null) {
      // 如果右子樹上沒有內容，則直接插入，如果有，尋找下一個插入位置
      root.right = newNode
      root.right.parent = root
    } else {
      this.#insertNode(root.right, newNode)
    }
  }
}

在類中定義了insertNode方法，這個方法接受數值或者數值型別的陣列，將其插入這個二元搜尋樹中；插入方法我們定義了一個私有的#insertNode方法，用於節點的插入。

為了看到效果，我們這裡定義了一個靜態方法，用於中序遍歷（因為中序遍歷的順序是左根右，在二元搜尋樹中使用中序排序，最終結果是從小到大依次排序的）這個樹，並返回一個陣列，

範例程式碼如下：

// 中序遍歷這個樹
static inorder(root) {
  if (!root) return
  const result = []
  const stack = []
  // 定義一個指標
  let p = root
  // 如果棧中有資料或者p不是null，則繼續遍歷
  while (stack.length || p) {
    // 如果p存在則一致將p入棧並移動指標
    while (p) {
      // 將 p 入棧，並以移動指標
      stack.push(p)
      p = p.left
    }
    const node = stack.pop()
    result.push(node.val)
    p = node.right
  }
  return result
}

測試程式碼如下：

const tree = new BinarySearchTree()
tree.insertNode([71, 35, 87, 22, 53, 46, 66, 78, 98])
const arr = BinarySearchTree.inorder(tree.root)
console.log(arr) // [ 22, 35, 46, 53, 66,71, 78, 87, 98 ]

最終的樹結構如下：

查詢二元搜尋樹中的資料

現在我們封裝一個find方法，用於查詢二元搜尋樹中的某個資料，假如我們查詢66這個資料，利用上面那個樹，

其查詢思路如下圖所示：

遞迴方式實現如下：

/**
 * 根據 val 查詢節點
 * @param {number} val 需要查詢的數值
 * @returns 如果找到返回當前節點的參照，如果未找到返回 undefined
 */
find(val) {
  if (typeof val !== 'number') throw Error('插入的值不是一個數位')
  function r(node, val) {
    // console.log(node)
    if (!node) return
    if (node.val < val) {
      return r(node.right, val)
    } else if (node.val > val) {
      return r(node.left, val)
    } else {
      return node
    }
  }
  return r(this.root, val)
}

迭代方式實現如下：

/**
 * 根據 val 查詢節點
 * @param {number} val 需要查詢的數值
 * @returns 如果找到返回當前節點的參照，如果未找到返回 undefined
 */
find(val) {
  if (typeof val !== 'number') throw Error('插入的值不是一個數位')
  let node = this.root
  while (node) {
    if (node.val < val) {
      // 進入右子樹
      node = node.right
    } else if (node.val > val) {
      // 進入左子樹
      node = node.left
    } else {
      return node
    }
  }
  return
}

兩者相對來說，使用迭代的方式更優一些。

刪除二元搜尋樹的某個節點

前驅後繼節點

在開始刪除二元搜尋樹中的某個節點之前，我們先來了解一下什麼是前驅和後繼節點；

前驅節點指的是使用中序遍歷當前二元搜尋樹時，當前節點的上一個節點就是前驅節點，換一種說法就是在二元搜尋樹中，當前節點的左子樹的最大值，就是該節點的前驅節點；
後繼節點指的是使用中序遍歷當前二元搜尋樹時，當前節點的下一個節點就是後繼節點，換一種說法就是在二元搜尋樹中，當前節點的右子樹的最小值，就是該節點的後繼節點；

如下圖所示：

瞭解了什麼是前驅和後繼節點之後，現在我們來開始刪除某個節點。

刪除一個節點的三種情況

當刪除的節點是葉子節點時，只需要將指向它的指標修改為null，即可，如下圖所示：

當需要刪除的節點存在一個子節點時，需要將要刪除節點的子節點的parent指標指向要刪除節點的父節點，然後將當前要刪除節點的父節點指向子節點即可，

如下圖所示：

當需要刪除的節點存在一個子節點時，刪除步驟如下：

找到當前節點的前驅或者後繼節點，這裡選擇後繼；
然後將後繼節點的值賦值給當前節點；
刪除後繼節點。

如下圖所示：

現在我們將這些情況已經分析完成了，現在通過程式碼實現一下。

實現程式碼

實現程式碼如下：

remove(val) {
  // 1. 刪除節點
  const cur = this.find(val)
  if (!val) return false // 未找到需要刪除的節點
  if (!cur.left && !cur.right) {
    // 1. 當前節點是葉子節點的情況
    this.#removeLeaf(cur)
  } else if (cur.left && cur.right) {
    // 2. 當前節點存在兩個子節點
    // 2.1 找到當前節點的後繼節點
    const successorNode = this.#minNode(cur.right)
    // 2.2 將後繼節點的值賦值給當前值
    cur.val = successorNode.val
    if (!successorNode.left && !successorNode.right) {
      // 2.3 後繼節點是葉子節點，直接刪除
      this.#removeLeaf(successorNode)
    } else {
      // 2.4 後繼節點不是葉子節點
      // 2.4.1記錄該節點的子節點，
      let child =
        successorNode.left !== null ? successorNode.left : successorNode.right
      // 2.4.2 記錄該節點的父節點
      let parent = successorNode.parent
      // 2.4.3 如果當前父節點的left是後繼結點，則把後繼結點的父節點的left指向後繼結點的子節點
      if (parent.left === successorNode) {
        parent.left = child
      } else {
        // 2.4.4 如果不是，則讓父節點的right指向後繼結點的子節點
        parent.right = child
      }
      // 2.4.5 修改子節點的parent指標
      child.parent = parent
    }

    // 2.3 刪除後繼節點
  } else {
    // 記錄當前節點的是否是父節點的左子樹
    const isLeft = cur.val < cur.parent.val
    // 3. 僅存在一個子節點
    if (cur.left) {
      // 3.1 當前節點存在左子樹
      cur.parent[isLeft ? 'left' : 'right'] = cur.left
      cur.left.parent = cur.parent
    } else if (cur.right) {
      // 3.2 當前節點存在右子樹
      cur.parent[isLeft ? 'left' : 'right'] = cur.right
      cur.right.parent = cur.parent
    }
  }
}
// 刪除葉子節點
#removeLeaf(node) {
  if (!node) return
  const parent = node.parent
  if (node.val < parent.val) {
    // 當前要刪除的葉子節點是左節點
    parent.left = null
  } else {
    // 當前要刪除的葉子節點是右節點
    parent.right = null
  }
}
// 查詢最小值
#minNode(node) {
  if (!node) return
  if (!node.left) return node
  let p = node.left
  while (p.left) {
    p = p.left
  }
  return p
}

完整程式碼

本篇文章中的完整程式碼如下：

class BinarySearchTree {
  constructor() {
    // 初始化根節點
    this.root = null
  }

  // 建立一個節點
  Node(val) {
    return {
      left: null, // 左子樹
      right: null, // 右子樹
      parent: null, // 父節點
      val,
    }
  }
  /**
   * 建立要給插入節點的方法
   * @param {number | array[number]} val
   * @returns
   */
  insertNode(val) {
    const that = this
    // 允許接受一個陣列，批次插入
    if (Object.prototype.toString.call(val) === '[object Array]') {
      val.forEach(function (v) {
        that.insertNode(v)
      })
      return
    }

    if (typeof val !== 'number') throw Error('插入的值不是一個數位')

    const newNode = this.Node(val)
    if (this.root) {
      // 根節點非空
      this.#insertNode(this.root, newNode)
    } else {
      // 根節點是空的，直接建立
      this.root = newNode
    }
  }

  /**
   * 私有方法，插入節點
   * @param {Object{Node}} root
   * @param {Object{Node}} newNode
   */
  #insertNode(root, newNode) {
    if (newNode.val < root.val) {
      // 新節點比根節點小，左子樹
      if (root.left === null) {
        // 如果左子樹上沒有內容，則直接插入，如果有，尋找下一個插入位置
        root.left = newNode
        root.left.parent = root
      } else {
        this.#insertNode(root.left, newNode)
      }
    } else {
      // 新節點比根節點大，右子樹
      if (root.right === null) {
        root.right = newNode
        root.right.parent = root
      } else {
        this.#insertNode(root.right, newNode)
      }
    }
  }
  /**
   * 根據 val 查詢節點
   * @param {number} val 需要查詢的數值
   * @returns 如果找到返回當前節點的參照，如果未找到返回 undefined
   */
  find(val) {
    if (typeof val !== 'number') throw Error('插入的值不是一個數位')
    let node = this.root
    while (node) {
      if (node.val < val) {
        // 進入右子樹
        node = node.right
      } else if (node.val > val) {
        // 進入左子樹
        node = node.left
      } else {
        return node
      }
    }
    return
  }
  // /**
  //  * 根據 val 查詢節點 遞迴版
  //  * @param {number} val 需要查詢的數值
  //  * @returns 如果找到返回當前節點的參照，如果未找到返回 undefined
  //  */
  // find(val) {
  //   if (typeof val !== 'number') throw Error('插入的值不是一個數位')
  //   function r(node, val) {
  //     // console.log(node)
  //     if (!node) return
  //     if (node.val < val) {
  //       return r(node.right, val)
  //     } else if (node.val > val) {
  //       return r(node.left, val)
  //     } else {
  //       return node
  //     }
  //   }
  //   return r(this.root, val)
  // }
  remove(val) {
    // 1. 刪除節點
    const cur = this.find(val)
    if (!val) return false // 未找到需要刪除的節點

    if (!cur.left && !cur.right) {
      // 1. 當前節點是葉子節點的情況
      this.#removeLeaf(cur)
    } else if (cur.left && cur.right) {
      // 2. 當前節點存在兩個子節點
      // 2.1 找到當前節點的後繼節點
      const successorNode = this.#minNode(cur.right)
      // 2.2 將後繼節點的值賦值給當前值
      cur.val = successorNode.val
      if (!successorNode.left && !successorNode.right) {
        // 2.3 後繼節點是葉子節點，直接刪除
        this.#removeLeaf(successorNode)
      } else {
        // 2.4 後繼節點不是葉子節點
        // 2.4.1記錄該節點的子節點，
        let child =
          successorNode.left !== null ? successorNode.left : successorNode.right
        // 2.4.2 記錄該節點的父節點
        let parent = successorNode.parent
        // 2.4.3 如果當前父節點的left是後繼結點，則把後繼結點的父節點的left指向後繼結點的子節點
        if (parent.left === successorNode) {
          parent.left = child
        } else {
          // 2.4.4 如果不是，則讓父節點的right指向後繼結點的子節點
          parent.right = child
        }
        // 2.4.5 修改子節點的parent指標
        child.parent = parent
      }

      // 2.3 刪除後繼節點
    } else {
      // 記錄當前節點的是否是父節點的左子樹
      const isLeft = cur.val < cur.parent.val
      // 3. 僅存在一個子節點
      if (cur.left) {
        // 3.1 當前節點存在左子樹
        cur.parent[isLeft ? 'left' : 'right'] = cur.left
        cur.left.parent = cur.parent
      } else if (cur.right) {
        // 3.2 當前節點存在右子樹
        cur.parent[isLeft ? 'left' : 'right'] = cur.right
        cur.right.parent = cur.parent
      }
    }
  }
  // 刪除葉子節點
  #removeLeaf(node) {
    if (!node) return
    const parent = node.parent
    if (node.val < parent.val) {
      // 當前要刪除的葉子節點是左節點
      parent.left = null
    } else {
      // 當前要刪除的葉子節點是右節點
      parent.right = null
    }
  }
  // 查詢最小值
  #minNode(node) {
    if (!node) return
    if (!node.left) return node
    let p = node.left
    while (p.left) {
      p = p.left
    }
    return p
  }
  // 中序遍歷這個樹
  static inorder(root) {
    if (!root) return
    const result = []
    const stack = []
    // 定義一個指標
    let p = root
    // 如果棧中有資料或者p不是null，則繼續遍歷
    while (stack.length || p) {
      // 如果p存在則一致將p入棧並移動指標
      while (p) {
        // 將 p 入棧，並以移動指標
        stack.push(p)
        p = p.left
      }

      const node = stack.pop()
      result.push(node.val)
      p = node.right
    }
    return result
  }
}
const tree = new BinarySearchTree()
tree.insertNode([71, 35, 84, 22, 53, 46, 66, 81, 83, 82, 88, 98])
console.log(BinarySearchTree.inorder(tree.root)) // [ 22, 35, 46, 53, 66, 71, 81, 82, 83, 84, 88, 98 ]
tree.remove(71
console.log(BinarySearchTree.inorder(tree.root)) // [ 22, 35, 46, 53, 66, 81, 82, 83, 84, 88, 98 ]