JS实现二叉搜索树及操作详解

下载万磁搜索绿色版

本文深入解析了使用JS实现二叉搜索树（BST）及其常见操作，并着重讲解了BST的核心特性：左子节点小于根节点，右子节点大于根节点。文章详细阐述了插入、删除、查找等关键操作的JS实现方法，并提供了清晰的代码示例。针对删除操作，文章剖析了无子节点、单子节点、双子节点三种情况，并分别给出了相应的解决方案。同时，还讨论了二叉搜索树的平衡问题以及平衡树的实现方法。掌握这些知识点，能帮助开发者更好地理解和应用二叉搜索树这种重要的数据结构。

二叉搜索树插入操作的时间复杂度在平衡情况下为O(log n)，最坏情况下为O(n)；删除节点的三种情况分别为：无子节点直接删除、单子节点用子节点替代、双子节点用中序后继或前驱值替换后删除该节点。

JS实现二叉搜索树，关键在于理解BST的特性：左子节点小于根节点，右子节点大于根节点。然后，围绕这个特性，实现插入、删除、查找等操作。

解决方案：

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

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(data) {
    const newNode = new Node(data);

    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  insertNode(node, newNode) {
    if (newNode.data < node.data) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }

  remove(data) {
    this.root = this.removeNode(this.root, data);
  }

  removeNode(node, data) {
    if (node === null) {
      return null;
    }

    if (data < node.data) {
      node.left = this.removeNode(node.left, data);
      return node;
    } else if (data > node.data) {
      node.right = this.removeNode(node.right, data);
      return node;
    } else {
      // data === node.data

      // case 1: no children
      if (node.left === null && node.right === null) {
        node = null;
        return node;
      }

      // case 2: one child
      if (node.left === null) {
        node = node.right;
        return node;
      }

      if (node.right === null) {
        node = node.left;
        return node;
      }

      // case 3: two children
      // find the minimum node in the right subtree
      const aux = this.findMinNode(node.right);
      node.data = aux.data;

      node.right = this.removeNode(node.right, aux.data);
      return node;
    }
  }

  findMinNode(node) {
    let current = node;
    while (current && current.left !== null) {
      current = current.left;
    }
    return current;
  }


  inorder(node = this.root, callback) {
    if (node) {
      this.inorder(node.left, callback);
      callback(node.data);
      this.inorder(node.right, callback);
    }
  }

  preorder(node = this.root, callback) {
    if (node) {
      callback(node.data);
      this.preorder(node.left, callback);
      this.preorder(node.right, callback);
    }
  }

  postorder(node = this.root, callback) {
    if (node) {
      this.postorder(node.left, callback);
      this.postorder(node.right, callback);
      callback(node.data);
    }
  }

  search(data) {
    return this.searchNode(this.root, data);
  }

  searchNode(node, data) {
    if (node === null) {
      return false;
    }

    if (data < node.data) {
      return this.searchNode(node.left, data);
    } else if (data > node.data) {
      return this.searchNode(node.right, data);
    } else {
      return true;
    }
  }
}


// Example Usage:
const bst = new BinarySearchTree();
bst.insert(11);
bst.insert(7);
bst.insert(15);
bst.insert(5);
bst.insert(9);
bst.insert(13);
bst.insert(20);

console.log("Inorder traversal:");
bst.inorder(bst.root, (data) => console.log(data)); // Output: 5 7 9 11 13 15 20

console.log("Search for 9:", bst.search(9)); // Output: true
console.log("Search for 2:", bst.search(2)); // Output: false

bst.remove(7);
console.log("Inorder traversal after removing 7:");
bst.inorder(bst.root, (data) => console.log(data)); // Output: 5 9 11 13 15 20

二叉搜索树的插入操作的时间复杂度是多少？

插入操作的时间复杂度取决于树的结构。在最佳情况下（树是平衡的），时间复杂度为O(log n)，其中n是树中节点的数量。在最坏情况下（树是不平衡的，类似于链表），时间复杂度为O(n)。 实际情况往往介于两者之间，但平衡树的插入操作通常性能更好。

如何在JS中实现二叉搜索树的平衡？

平衡二叉搜索树（例如AVL树、红黑树）是为了解决普通二叉搜索树在最坏情况下性能退化的问题。 实现平衡的关键在于维护树的平衡状态，并在插入和删除节点时进行必要的旋转操作。

• AVL树: AVL树通过跟踪每个节点的平衡因子（左子树高度 - 右子树高度）来维护平衡。平衡因子必须始终为 -1、0 或 1。如果插入或删除操作导致节点的平衡因子超出此范围，则执行旋转操作（左旋或右旋）来恢复平衡。 实现AVL树需要额外的代码来计算高度和执行旋转操作。

• 红黑树: 红黑树使用颜色（红色或黑色）来标记节点，并遵循一组规则来确保树的平衡。这些规则包括：根节点是黑色的，所有叶子节点（NIL节点）都是黑色的，红色节点的子节点必须是黑色的，从任何节点到其所有叶子节点的路径都包含相同数量的黑色节点。 红黑树的插入和删除操作比AVL树更复杂，但通常具有更好的性能。

虽然手动实现AVL树或红黑树可以更深入地理解平衡二叉搜索树的原理，但也可以考虑使用现有的库。

二叉搜索树删除节点的三种情况分别是什么？

删除操作稍微复杂一些，需要考虑三种情况：

1. 要删除的节点没有子节点（叶子节点）： 直接将该节点从树中移除即可。 将父节点的相应指针（left 或 right）设置为 null。

2. 要删除的节点只有一个子节点： 将该节点从树中移除，并将其子节点连接到其父节点。 用子节点替换要删除的节点，更新父节点的指针。

3. 要删除的节点有两个子节点： 这种情况比较复杂。 通常有两种策略：

   • 找到该节点的中序后继节点（右子树中的最小节点）： 将后继节点的值复制到要删除的节点，然后从右子树中删除后继节点。 由于后继节点是右子树中的最小节点，它要么是叶子节点，要么只有一个右子节点，因此删除后继节点会简化为前面两种情况之一。
   • 找到该节点的中序前驱节点（左子树中的最大节点）： 类似于后继节点方法，将前驱节点的值复制到要删除的节点，然后从左子树中删除前驱节点。

选择哪种策略通常取决于具体的实现和性能考虑。 使用后继节点方法更常见。

今天关于《JS实现二叉搜索树及操作详解》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！