JS中的算法与数据结构之二叉查找树（Binary Sort Tree）实例详解

JS中的算法与数据结构：二叉查找树（Binary Sort Tree）

什么是二叉查找树

二叉查找树（Binary Sort Tree），又称二叉搜索树或二叉排序树，是一种特殊的二叉树结构。它具有以下性质：

• 每个结点最多只有两个子结点。
• 左子树中的所有结点的值均小于它的根结点的值。
• 右子树中的所有结点的值均大于它的根结点的值。
• 没有相同节点值出现

因为具备以上性质，所以可以对其进行查找、插入、删除等操作，时间复杂度为 O(log n)。

实现过程

插入节点

向二叉查找树中插入一个节点，需要从二叉树的根节点开始查找。此时，有以下两种情况：

1. 如果树为空，直接将该节点作为根节点。
2. 如果该节点的值大于当前节点的值，则向右子树查找。如果右子树为空，则将该节点作为当前节点的右子节点。如果右子树不为空，继续查找。
3. 如果该节点的值小于当前节点的值，则向左子树查找。如果左子树为空，则将该节点作为当前节点的左子节点。如果左子树不为空，继续查找。

class BinarySortTree {
  constructor() {
    this.root = null; // 初始化根节点为空
  }

  // 插入节点
  insert(key) {
    const newNode = new Node(key); // 创建一个新节点
    if (this.root === null) { // 树为空时，直接将该节点作为根节点
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  // 插入节点-辅助方法
  insertNode(root, newNode) {
    if (newNode.key > root.key) { // 如果节点值大于当前节点的值
      if (root.right === null) { // 如果右子树为空，则将该节点作为当前节点的右子节点
        root.right = newNode;
      } else { // 如果右子树不为空，继续查找
        this.insertNode(root.right, newNode);
      }
    } else { // 如果节点值小于当前节点的值
      if (root.left === null) { // 如果左子树为空，则将该节点作为当前节点的左子节点
        root.left = newNode;
      } else { // 如果左子树不为空，继续查找
        this.insertNode(root.left, newNode);
      }
    }
  }
}

class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

查找节点

从根节点开始查找，依次比较节点值和要查找的值。如果相等，则返回该节点。如果当前节点的值大于要查找的值，则向左子树查找。如果当前节点的值小于要查找的值，则向右子树查找。如果找不到，则返回 null。

// 查找节点
search(key) {
  return this.searchNode(this.root, key);
}

// 查找节点-辅助方法
searchNode(root, key) {
  if (root === null) { // 如果树为空或者已经遍历过整个树，则返回null
    return null;
  } else if (root.key === key) { // 如果当前节点的值等于查找的值，则返回该节点
    return root;
  } else if (root.key > key) { // 如果当前节点的值大于查找的值，则向左子树查找
    return this.searchNode(root.left, key);
  } else { // 如果当前节点的值小于查找的值，则向右子树查找
    return this.searchNode(root.right, key);
  }
}

删除节点

删除节点需要注意以下三种情况：

1. 节点为叶子节点，即没有子节点。此时，直接删除该节点即可。
2. 节点只有一个子节点。此时，将该节点的子节点替换该节点即可。
3. 节点有两个子节点。此时，将该节点的后继节点（即右子树的最小值）替换该节点。

// 删除节点
remove(key) {
  this.root = this.removeNode(this.root, key);
}

// 删除节点-辅助方法
removeNode(root, key) {
  if (root === null) { // 如果树为空
    return null;
  } else if (key < root.key) { // 如果当前节点的值大于要删除的值，则向左子树查找
    root.left = this.removeNode(root.left, key);
    return root;
  } else if (key > root.key) { // 如果当前节点的值小于要删除的值，则向右子树查找
    root.right = this.removeNode(root.right, key);
    return root;
  } else { // 如果当前节点的值等于要删除的值

    // 第一种情况：节点为叶子节点
    if (root.left === null && root.right === null) {
      root = null;
      return root;
    }

    // 第二种情况：节点只有一个子节点
    if (root.left === null) {
      root = root.right;
      return root;
    } else if (root.right === null) {
      root = root.left;
      return root;
    }

    // 第三种情况：节点有两个子节点
    const aux = this.findMinNode(root.right); // 获取右子树的最小节点
    root.key = aux.key; // 将当前节点的值替换为后继节点的值
    root.right = this.removeNode(root.right, aux.key); // 删除后继节点
    return root;
  }
}

// 查找最小节点
findMinNode(node) {
  while (node.left !== null) {
    node = node.left;
  }
  return node;
}

示例

const bst = new BinarySortTree();

bst.insert(11);
bst.insert(7);
bst.insert(15);
bst.insert(5);
bst.insert(3);
bst.insert(9);
bst.insert(8);
bst.insert(10);
bst.insert(13);
bst.insert(12);
bst.insert(14);
bst.insert(20);
bst.insert(18);
bst.insert(25);

console.log(bst.search(9)); // 返回： Node { key: 9, left: Node {...}, right: Node {...} }
console.log(bst.search(19)); // 返回： null

bst.remove(5);
console.log(bst.root.left.left); // 返回： Node { key: 3, left: null, right: null }

以上代码演示了一个二叉查找树，其中包括节点的插入、查找和删除操作。其中，演示了一个查找成功的情况和一个查找失败的情况，以及一个删除节点的操作。