AVL 树检查左子树和右子树的高度，并确保两者之差不大于 1。这个差值称为平衡因子。例如，在下面的树中，第一棵树是平衡的，而接下来的两棵树是不平衡的：在第二棵树中，C 的左子树高度为 2，右子树高度为 0，所以差值为 2。在第三棵树中，A 的右子树高度为 2，而左子树不存在，所以高度为 0，差值再次为 2。AVL 树……阅读更多

AVL 树（以发明者 Adelson-Velsky 和 Landis 命名）是一种自平衡二叉搜索树。自平衡树是一种在子树内执行某些旋转以使其左右两侧都保持平衡的树。这些树在插入操作导致树的一侧变得很重的情况下特别有用。平衡树使查找时间保持接近 O(log(n))，而不是完全不平衡的树，后者更接近 O(n)。

以下是 BinarySearchTree 类的完整实现：示例class BinarySearchTree {    constructor() {       // 将根元素初始化为 null。       this.root = null;    }    insertIter(data) {       let node = new this.Node(data);    // 检查树是否为空    if (this.root === null) {       // 作为第一个元素插入       this.root = node;       return;    }    let currNode = this.root;    while (true) {    if (data < currNode.data) {       // 设置……阅读更多

树是一种非线性数据结构，它具有节点和边；其中边充当两个节点之间的链接，节点在其内保存值。遍历是一种过程，它将检索树中每个节点的数据并按指定的顺序打印它们。下面提到了三种类型的树遍历：中序遍历 - 中序技术将遵循路径（左→根→右）。前序遍历 - 前序技术将遵循路径（根→左→右）。后序遍历 - 后序技术将遵循路径（左……阅读更多

树是一种分层数据结构，它包含节点和边。树中的边充当连接两个节点的链接。前序树遍历是一种技术，其中根节点将首先被遍历，然后遍历左子树，然后是右子树。它将表示为根→左→右算法以下是执行前序树遍历的步骤：遍历根节点。然后，遍历左子树。然后，遍历右子树。为了更好地理解前序遍历，请考虑以下二叉搜索树……阅读更多

树是由节点和边组成的复杂数据结构。这些实体相互连接以形成树状结构。遍历数据结构意味着访问该结构中的每个节点并从中提取一系列值。共有三种类型的遍历，即中序遍历（左→根→右）、前序遍历（根→左→右）和后序遍历（左→右→根）。中序遍历在中序遍历中，首先访问左子树，然后访问根节点，最后访问右子树。如果二叉树是……阅读更多

树是一种非线性分层数据结构，它是节点和边的组合。树中的节点存储值，这些节点通过边相互连接。树的最顶层节点没有任何父节点，称为根节点。下面的二叉搜索树用重要的术语进行了标记。基本术语节点 - 具有指向另一个节点的指针和存储任何数据类型值的能力。根 - 此节点位于树的最顶部，并且是……阅读更多

在二叉搜索树中，如果我们查看左子节点总是小于父节点的属性，我们会发现，如果我们一直迭代到左子节点，直到到达没有左子节点的节点，我们基本上就会找到 BST 中最小的元素。让我们在代码中实现此函数。从现在起，我们将只实现函数的单一版本，即迭代版本或递归版本。在这种情况下，我们将创建一个迭代函数：示例getMinVal() {    if (this.root === null) {       throw "空树！";    }    let……阅读更多

我们将使用 BST 的属性在其中查找元素。让我们首先看一下搜索的迭代实现：示例searchIter(data) {    let currNode = this.root;    while (currNode !== null) {       if (currNode.data === data) {          // 找到元素！          return true;       } else if (data < currNode.data) {          // 向左移动，因为数据小于父节点          currNode = currNode.left;       } else {        ……阅读更多

在新建的二叉树中，第一次插入会在根节点创建一个节点。进一步的插入将根据二叉搜索树的属性进行插入，左子节点小于父节点，右子节点大于父节点。让我们看看如何在代码中实现这个算法：示例insertIter(data) {    let node = new this.Node(data);    // 检查树是否为空    if (this.root === null) {       // 作为第一个元素插入       this.root = node; return;    }    let currNode = this.root;  ……阅读更多