二叉搜索树 - wangshengliang

有序序列查找：二分查找、插值查找
乱序序列查找：顺序查找，但是时间复杂度为 O(n)

示例：10000 个乱序的数，查找指定的元素

const arr = [] // 存放乱序的数
// 生成1万个乱序的数
for (let i = 0; i < 10000; i++) {
  arr[i] = Math.floor(Math.random() * 10000)
}

let count = 0 // 计数器，用于对查找的次数进行计数

// 查找指定的元素
function search(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    count++
    if (arr[i] === target) return true
  }
  return false
}
console.log(search(arr, 7))
console.log(`用了${count}次查找`)

这种方式，实际上是比较低效的。如何优化呢？

算法
数据结构：数据结构上面有很大的优化空间，可以将其优化为一颗二叉搜索树。

二叉搜索树

二叉搜索树，英语是 Binary Search Tree，简称 BST，这是一种特殊的二叉树，其每个节点都包含一个键值，并且满足以下性质：

节点关系：对于任意一个节点，左子树中所有节点的键值都比该节点的键值小，右子树中所有节点的键值都比该节点的键值大。
中序遍历：由于上述性质，对 BST 进行 中序遍历 可以得到一个有序的序列。

示例：对下面的数字构建二叉搜索树

;[3, 5, 1, 6, 7, 2, 9, 8]

取3作为根节点，然后取第二个元素5，因为5比 3 大，所以放在右边
取 1，比 3 小，所以将其放在左侧
接下来是 6，比 3 大，往右侧走，然后比 5 也大，因此放在 5 的右侧
接下来是 7，一层一层比下来，应该放在 6 的右侧
接下来是 2，比 3 小，所以走左边，比 1 大，成为 1 的右节点
接下来是 9，一路比下来，比 7 也大，成为 7 的右节点；

最后是 8，一路比下来，比 9 小，因此成为 9 的左节点

代码实现

class TreeNode {
  constructor(value) {
    this.value = value
    this.left = null
    this.right = null
  }
}

/**
 * arr - 要构建的二叉搜索树的序列
 */
function buildSearchTree(arr) {
  if (arr === null || arr.length === 0) return null

  /**
   * root - 父节点
   * num - 当前节点
   */
  function addNode(root, num) {
    if (root === null || root.value === num) return

    if (root.value < num) {
      // 当前节点比父节点大，应该放在右边
      if (root.right === null) {
        // 当前父节点没有右子树，那么当前节点直接成为新的右子树即可
        root.right = new TreeNode(num)
      } else {
        addNode(root.right, num)
      }
    } else {
      // 当前节点比父节点小，应该放在左边
      if (root.left === null) root.left = new TreeNode(num)
      else addNode(root.left, num)
    }
  }

  const root = new TreeNode(arr[0]) // 最上层的根节点

  // 注意这里 i 是从 1 开始的，因为第一个元素已经根节点了
  for (let i = 1; i < arr.length; i++) {
    addNode(root, arr[i])
  }

  return root
}

const arr = [3, 5, 1, 6, 7, 2, 9, 8]
const bst = buildSearchTree(arr)
console.log(bst)

function inOrder(root) {
  if (root === null) return

  inOrder(root.left)

  console.log(root.value)

  inOrder(root.right)
}
inOrder(bst)

接下来，我们想要使用二叉搜索树进行一个搜索。

const arr = [3, 5, 1, 6, 7, 2, 9, 8]
const bst = buildSearchTree(arr)

function searchByBST(root, target) {
  if (root === null) return false
  // 下面的逻辑有一点类似于二分查找
  if (root.value === target) return true
  if (root.value > target) return searchByBST(root.left, target)
  else return searchByBST(root.right, target)
}
console.log(searchByBST(bst, 5))

-EOF-