二叉查找树

[jinzhepro]

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

二叉查找树的查找

先取根节点，如果值比节点小就在左树递归，如果值比节点大就在右树递归。

代码

const searchOrder = (node, val)=>{
  if(!node.value) return
  let n = node // 存储节点
  while (n){
    if(val < n.value){ // 小于节点值
      n = n.children[0] // 循环
    }else if(val > n.value){ // 大于节点值
      n = n.children[1] // 循环
    }else{
      console.log(n.value) // 找到！
      return n
    }
  }
  return null
}

二叉查找树插入

如果数据比节点小，并且左子树为空，就插入到左子树位置；如果不为空，那就递归查找左子树。
如果数据比节点大，并且右子树为空，就插入到右子树位置；如果不为空，那就递归查找右子树。

代码

const insertOrder = (node, val)=>{
  if(!node){
    return val
  }
  let n = node // 存储节点
  while (n){
     if(val.value < n.value){ // 小于节点值
      if(!n.children || !n.children[0]){ // 判断是叶子节点或没有左树
        n.children = [val].concat(n.children || ['']) // 添加节点到左树
        return node // 返回树
      }
      n = n.children[0] // 递归左树
    }else if(val.value > n.value){ // 大于节点值
      if(!n.children || !n.children[1]){ // 判断是叶子节点或没有右树
        n.children = (n.children || ['']).concat(val) // 添加节点到右树
        return node // 返回树
      }
      n = n.children[1] // 递归右树
    }else{
      console.log('相同数据！！')
      return node
    }
  }
}

二叉查找树删除

被删除的节点分三种情况：

1. 为叶子结点的情况下，只需要在父级节点删除该节点。（55）
2. 只有一个节点的情况下，只需要改变子节点的父级指针。（13）
3. 左右节点都有的情况下需要查找右子树的最小节点替换当前节点。（18）

也可用标记法，在不改变结构的情况下使用删除标记记录

代码

const removeOrder = (node, val)=>{
  let n = node // 存储树
  let p = null // 存储父节点
  while (n){
    if(n.value === val.value && !n.children){ // 叶子结点
      p.children = p.children.filter(m=>m.value !== val.value) // 父节点直接过滤掉该值
      return node
    }
    if(n.value === val.value && n.children.filter(o=>o).length === 1){ // 只有一个叶子节点
      p.children = p.children.map(m=>{ // 父节点遍历
        if(m.value === n.value){ // 找到要删除的节点
          return m.children.filter(o=>o)[0] // 替换子节点数据
        }else{ // 否则不变
          return m
        }
      })
      return node // 返回树
    }
    if(n.value === val.value && n.children.filter(o=>o).length === 2){ // 两个节点都有
      p.children = p.children.map(m=>{ // 父节点遍历
        if(n.value === m.value){ // 找到要删除的节点
          const min = minOrder(m.children[1]) // 找到右树最小节点
          removeOrder(p,{value: min}) // 删除右树最小节点
          return { // 将本节点替换为右树最小节点
            ...m,
            value: min,
          }
        }else{ // 否则不变
          return m
        }
      })
      return node // 返回树
    }
    p = n // 存储父节点
    if(val.value < n.value){ // 小于节点值
      n = n.children[0] // 循环左树
    }else if(val.value > n.value){ // 大于节点值
      n = n.children[1] // // 循环右树
    }else{
      console.log('未找到')
      return
    }
  }
}

二叉查找树最大最小值

• 循环左树到最后的值就是最小值。
• 循环右树到最后的值就是最大值。

代码

const minOrder = (tree) => {
  if(!tree) return false
  let min = tree.value // 最小值初始化
  let n = tree.children ? tree.children[0] : null // 存储循环条件
  while (n) {
    min = n.value // 赋值最小值
    n = n.children ? n.children[0] : null // 循环左树
  }
  return min // 返回最小值
}

const maxOrder = (tree) => {
  if(!tree) return false
  let max = tree.value // 最大值初始化
  let n = tree.children ? tree.children[1] : null // 存储循环条件
  while (n) {
    max = n.value // 赋值最大值
    n = n.children ? n.children[1] : null // 循环右树
  }
  return max // 返回最大值
}

二叉查找树的前驱和后继节点

中序排列二叉查找树后节点的前后节点

支持重复数据的二叉查找树

• 将重复数据放在同一节点
• 将重复数据放在右子树

二叉查找树的时间复杂度

二叉查找树类似于二分查找法，时间复杂度 $O(log_n)$