18888628835/Blog

二叉搜索树

18888628835 opened this issue · 0 comments

18888628835 commented

二叉搜索树

树是一种分层数据的抽象结构。在现实中的比较类似树这种数据结构的是组织架构图。

image-20210628212825443

从上面的图可以看出，树是一系列包含父子关系的节点，最高层是根节点，根节点下的每个节点都有多个子节点。我们熟悉的 DOM 就是树结构，所以一般我们都称之为 DOM 树。

下图为典型的二叉搜索树
image
有子节点的节点叫做内部节点，而没有子节点的就叫外部节点，也可以叫叶节点。

一个节点有父节点、祖父节点之说，同样也有子节点、孙节点之说。例如节点5的父节点是7，祖父节点是11，子节点是3和6。

这其中还有一个概念叫子树，子树就是把一个节点视为根节点，并将其和它的子节点抽离出来组成子树。

节点中有一个重要的属性叫做深度。深度是由它的祖先节点的数量决定的，越多就越深。

那么深度由什么决定的呢，就是由树的高度决定的。上图中的树有三层（根节点为0）

二叉树和二叉搜索树

二叉树的意思就是每个节点最多只能有两个子节点。一个在左侧，一个在右侧，这种定义是前人帮我们总结好的，有助于我们高效完成插入、删除、查找等算法。

二叉搜索树是二叉树的一种，但是只允许在左侧放比父节点小的值（递减），在右侧放比父节点大的值（递增）。一开始的图就是一棵二叉搜索树，注意它的结构，是不是左边比父节点小，右侧比父节点大呢。

二叉树的数据结构组织方式是这样的：
image

下面我们根据上图来创建二叉树的节点

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

和链表一样，我们将通过指针（引用）来表示节点之间的关系。树有两根指针，分别指向左边和右边的子节点。每个节点本身我们称之为键。

下面我们需要在底层实现一个二叉搜索树的类。跟链表一样，我们需要实现一个根节点，不过链表中叫 head，这里我们叫做 root。

// 实现一个二叉搜索树
class BinarySearchTree {
  root;
  constructor() {
    this.root = null;
  }
}

插入一个键（节点）

  insert(key) {
    if (this.root === null) {
      this.root = new TreeNode(key);
    } else {
      this.insertNode(this.root, key);
    }
  }

跟链表一样，我们需要判断root 上是否有了键，如果没有就添加上，如果有，那就递归插入到对应的键上。

这里就用到一个递归插入的辅助函数insertNode，它是这样实现的的

  insertNode(root, key) {
    if (root.key > key) {
      if (root.left === null) {
        root.left = new TreeNode(key);
      } else {
        this.insertNode(root.left, key);
      }
    } else {
      if (root.right === null) {
        root.right = new TreeNode(key);
      } else {
        this.insertNode(root.right, key);
      }
    }
  }

我们来整理一下插入的全部过程：

  • 首先在insert函数中判断root 是否为空，如果为空就在 root 节点上插入，不为空则走 insertNode 辅助函数逻辑
  • 这个insertNode辅助函数接收当前的键和传入的 key，它将判断当前的键上的 key 是不是比传入的 key 小，这时候就需要根据结果判断到底进入到 left 还是 right。left 是比当前 key 小，right 是比当前 key 大。
  • 判断完方向后，就会顺着查看对应的边是否有值。如果没有就放上去。如果有值就进行递归。

从调用栈的角度分析就是

  • 首先 insert 函数的调用入栈
  • 根据当前键的 key 和传入的 key 判断，进入 insertNode 辅助函数时， insertNode 辅助函数入栈
  • 一直递归到键的边为 null 时，递归停止，入栈结束
  • 开始出栈，从最后一个insertNode 辅助函数依次到最开始的 insert 函数依次出栈。

二叉搜索树的遍历

遍历树是指访问树的每个节点并对他们进行某种操作。访问树的所有节点有三种方式：中序、先序和后序。

中序遍历

中序遍历会按照最小到最大的顺序访问所有节点。这种排序最大的作用是对树进行排序操作。

  //中序遍历
  inOrderTraverse(callback) {
    this.inOrderTraverseNode(this.root, callback);
  }

中序遍历接收一个回调函数，这个回调函数用来定义我们对遍历到的每个节点进行的操作。由于我们还是在树中大量使用递归，所以这里使用一个辅助函数来帮助我们操作。

  //中序遍历的辅助函数
  inOrderTraverseNode(node, callback) {
    if (node !== null) {
      this.inOrderTraverseNode(node.left, callback);
      callback(node.key);
      this.inOrderTraverseNode(node.right, callback);
    }
  }

要通过中序遍历的方法来遍历一棵树，首先需要检查传入的节点是否为 null，如果为 null，则停止递归——这是递归的基线条件。

然后，递归调用相同的函数来访问左侧子节点。接着对当前的节点进行一些操作，然后访问右侧子节点。

测试一下：

let tree = new BinarySearchTree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
tree.insert(6);
tree.inOrderTraverse(key => {
  console.log(key);
});//3 5 6 7 8 9 10 11 12 13 14 15 18 20 25

整个过程可以这样表示

image-20210628141814035

采用递归的方式不但代码简洁，还非常好理解。

先序遍历

先序遍历非常简单，只是把中序遍历的顺序换一下

  private preOrderTraverseNode(node, callback) {
    if (node !== null) {
      callback(node.key);
      this.preOrderTraverseNode(node.left, callback);
      this.preOrderTraverseNode(node.right, callback);
    }
  }
  preOrderTraverse(callback) {
    this.preOrderTraverseNode(this.root, callback);
  }

在先序遍历下，会首先访问节点本身，然后再访问它的左侧节点，最后是右侧节点。先序遍历的访问路径是这样的：

image-20210628143012137

先序遍历的一种应用是将树结构打印出来。

后序遍历

前面两个遍历只是顺序转换一下，后序遍历也是如此。只需要把对节点本身操作的放到最下面就行了。

  //后序遍历的辅助函数
  private postOrderTraverseNode(node, callback) {
    if (node !== null) {
      this.postOrderTraverseNode(node.left, callback);
      this.postOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  }
  //后序遍历
  postOrderTraverse(callback) {
    this.postOrderTraverseNode(this.root, callback);
  }

下面是后序遍历的程序处理过程

image-20210628212441914

后序遍历的一种用处是计算一个目录及其子目录的内存占用大小。

二叉搜索树的搜索

搜索最小值

下面我们需要搜索以下树的最小值和最大值

image-20210628213128349

我们说二叉搜索树的左边放的是比父节点小的值，而右边则放的是比父节点大的值。那么正如图中所见，最小的值不就在最左边，最大的值不就在最右边吗？

所以我们可以用递归来打印出最小的节点，很好写出来的可能是这样的

  minNode(node) {
    if (node.left !== null) {
      return this.minNode(node.left.left);
    } else {
      return node;
    }
  }
  min() {
    if (this.root.left !== null) {
      return this.minNode(this.root.left);
    } else {
      return this.root;
    }
  }

这种方式是我一开始想得到的，不过还有更加优雅的写法——使用指针来迭代查找。

  minNode(node) {
    let current = node;
    while (current !== null && current.left !== null) {
      current = current.left;
    }
    return current;
  }
  min() {
    return this.minNode(this.root);
  }

指针的方式来查找树的最小值跟查找链表的最后一个节点非常相似，只是这里变成了一直查找 left。

搜索最大值

既然最小值已经实现了，那么最大值就呼之欲出了。

  maxNode(node) {
    let current = node;
    while (current && current.right) {
      current = current.right;
    }
    return current;
  }
  max() {
    return this.maxNode(this.root);
  }

二叉树树搜索最小值和搜索最大值就是不断查找left 和 right。

搜索指定的值

在树的搜索中，大量使用递归可以减少复杂度，以下是实现搜索指定值的递归实现：

  searchNode(node, key) {
    if (node === null) {
      return false;
    }
    if (node.key === key) {
      return true;
    }
    if (key < node.key) {
      return this.searchNode(node.left, key);
    } else if (key > node.key) {
      return this.searchNode(node.right, key);
    }
  }
  search(key) {
    return this.searchNode(this.root, key);
  }

我们将二叉树的 root 节点传递进searchNode这个函数中，然后通过判断大小，来递归进入不同的边，代码非常简洁易懂。

删除指定的键

现在我们要删除指定的键，也就是删除指定的节点。

下面我们画一个最简单的二叉树

image-20210629143154766

现在我要删除右边节点的 key 为4的键。它既没有 left 又没有 right，所以只需要把 root 的 left 变成 null，那我们可以这样写：

删除叶子结点

  removeNode(node, key) {
    //{2}
    if (node === null) {
      return null;
    }
    // 判断方向{3}
    if (node.key > key) {
      //当前节点大于 key，要往左边走
      node.left = this.removeNode(node.left, key); //{4}
      return node; //{5}
    } else if (node.key < key) {
      //当前节点小于 key，要往右边走
      node.right = this.removeNode(node.right, key); //{6}
      return node; //{7}
    } else {
      //当前节点等于 key
      if (node.left === null && node.right === null) {
        node = null; //{8}
        return node; //{9}
      }
    }
  }
  remove(key) {
    this.removeNode(this.root, key); //{1}
  }

跟之前的递归逻辑一样，我们还是利用一个辅助函数 removeNode进行递归{1}。接着进入递归函数运行逻辑：

  • 1.在递归时，如果判断当前节点是 null，则返回 null。{2}

  • 2.接下来判断key 跟当前节点的 key 的大小，这样可以判断应该走 left 还是 right。{3}

  • 3.我们传入的key 为4，此时当前 node 不为 null，它是根节点5，那程序会走左边进入递归。{4}

  • 4.当判断相等时，那么我们应该把当前节点变成 null。{8}

  • 5.由于node 是指针，让 node=null 只是改变 node 的指向，需要让父节点来接收这个 null 才行。{9}=>{4}

  • 6.由于父节点总是要拿到子节点的返回值，所以就有了{5}、{7}。否则就会变成函数默认返回值 undefined

**上面的代码我们处理的是删除叶节点的情况。**它的过程是这样的：

image-20210629160250472

删除有一边子节点的节点

下面处理找到对应的 key有 left 或者 right 其中一个的逻辑。我们只需要让它的指针等于 node.left 或者 node.right 就行了

      //第二种情况
      if (node.left === null) {
        node = node.right;
        return node;
      } else if (node.right === null) {
        node = node.left;
        return node;
      }

它的过程是这样的：

image-20210629160323202

删除的有双边的节点

这种要怎么处理呢？由于我们的是二叉搜索树，所以被删除的节点会比 left 大，比 right 小，如果随便删除掉这个节点，肯定会引起整棵树的顺序错乱。所以我们需要想一个办法替换掉这个节点。下图给了明确的解决方法：

image-20210629161105444

需要走以下步骤：

  • 从当前要删除的节点的右边找出最小的节点
  • 把最小节点的值替换掉当前节点的 key 值
  • 删除最小节点

这是因为节点的右边总是比当前节点大，所以从右边找最小的，也能让子树始终保持 left 小，right 大的顺序

        //第三种情况:删除双边节点
        let rightMin = this.minNode(node.right);
        node.key = rightMin.key;
        node.right = this.removeNode(node.right, node.key);
        return node;

删除节点完整代码

  removeNode(node, key) {
    //{2}
    if (node === null) {
      return null;
    }
    // 判断方向{3}
    if (node.key > key) {
      //当前节点大于 key，要往左边走
      node.left = this.removeNode(node.left, key); //{4}
      return node; //{5}
    } else if (node.key < key) {
      //当前节点小于 key，要往右边走
      node.right = this.removeNode(node.right, key); //{6}
      return node; //{7}
    } else {
      //当前节点等于 key
      //第一种情况：删除叶节点
      if (node.left === null && node.right === null) {
        node = null; //{8}
        return node; //{9}
      }
      //第二种情况：删除单边节点
      if (node.left === null) {
        node = node.right;
        return node;
      } else if (node.right === null) {
        node = node.left;
        return node;
      } else {
        //第三种情况:删除双边节点
        let rightMin = this.minNode(node.right);
        node.key = rightMin.key;
        node.right = this.removeNode(node.right, node.key);
        return node;
      }
    }
  }
  remove(key) {
    this.removeNode(this.root, key); //{1}
  }

源码地址：二叉搜索树