René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"前端进阶算法11：二叉查找树（BST树）","articleBody":"### 一、二叉查找树（BST树）\r\n\r\n有的笔者也称它为二叉搜索树，都是一个意思。\r\n\r\n二叉树本身没有多大的意义，直到有位大佬提出一个 trick。\r\n\r\n如果我们规定一颗二叉树上的元素拥有顺序，所有比它小的元素在它的左子树，比它大的元素在它的右子树，那么我们不就可以很快地查找某个元素了吗？\r\n\r\n不得不说这是一个非常天才的想法，于是，二叉查找树诞生了。\r\n\r\n所以，二叉查找树与二叉树不同的是，它在二叉树的基础上，增加了对二叉树上节点存储位置的限制：二叉搜索树上的每个节点都需要满足：\r\n\r\n- 左子节点值小于该节点值\r\n- 右子节点值大于等于该节点值\r\n\r\n![img](https://cdn.nlark.com/yuque/0/2020/png/273506/1584237137899-5cb8a9d4-c2f7-4741-98c8-b29d24951300.png?x-oss-process=image/resize,w_1500)\r\n\r\n在二叉树中，所有子节点值都是没有固定规律的，所以使用二叉树存储结构存储数据时，查找数据的时间复杂度为 O(n)，因为它要查找每一个节点。\r\n\r\n而使用二叉查找树就不同了，例如上图，我们如果要查找 6 ，先从根节点 10 比较，6 比 10 小，则查找左子树，再与 8 比较，6 比 8 小，继续查找 8 的左子树，也就是 6，我们找到了元素，结束。\r\n\r\n### 二、代码实现\r\n\r\n```js\r\nfunction BinarySearchTree() {\r\n  let Node = function (key) {\r\n    this.key = key\r\n    this.left = null\r\n    this.right = null\r\n  }\r\n  let root = null\r\n  \r\n  // 插入\r\n  this.insert = function(key){}\r\n  \r\n  // 查找\r\n  this.search = function(key){}\r\n  \r\n  // 删除\r\n  this.remove = function(key){}\r\n  \r\n  // 最大值\r\n  this.max = function(){}\r\n  \r\n  // 最小值\r\n  this.min = function(){}\r\n  \r\n  // 中序遍历\r\n  this.inOrderTraverse = function(){}\r\n  \r\n  // 先序遍历\r\n  this.preOrderTraverse = function(){}\r\n  \r\n  // 后序遍历\r\n  this.postOrderTraverse = function(){}\r\n}\r\n```\r\n\r\n#### 插入：\r\n\r\n- 首先创建一个新节点\r\n- 判断树是否为空，为空则设置插入的节点为根节点，插入成功，返回\r\n- 如果不为空，则比较该节点与根结点，比根小，插入左子树，否则插入右子树\r\n\r\n```js\r\nfunction insert(key) {\r\n  // 创建新节点\r\n  let newNode = new Node(key)\r\n  // 判断是否为空树\r\n  if(root === null) {\r\n    root = newNode\r\n  } else {\r\n    insertNode(root, newNode)\r\n  }\r\n}\r\n\r\n// 将 insertNode 插入到 node 子树上\r\nfunction insertNode(node, newNode) {\r\n  if(newNode.key \u003c node.key) {\r\n    // 插入 node 左子树\r\n    if(node.left === null) {\r\n      node.left = newNode\r\n    } else {\r\n      insertNode(node.left, newNode)\r\n    }\r\n  } else {\r\n    // 插入 node 右子树\r\n    if(node.right === null) {\r\n      node.right = newNode\r\n    } else {\r\n      insertNode(node.right, newNode)\r\n    }\r\n  }\r\n}\r\n```\r\n\r\n#### 最值：\r\n\r\n最小值：树最左端的节点\r\n\r\n最大值：树最右端的节点\r\n\r\n```js\r\n// 最小值\r\nfunction min() {\r\n  let node = root\r\n  if(node) {\r\n    while(node \u0026\u0026 node.left !== null) {\r\n      node = node.left\r\n    }\r\n    return node.key\r\n  }\r\n  return null\r\n}\r\n\r\n// 最大值\r\nfunction max() {\r\n  let node = root\r\n  if(node) {\r\n    while(node \u0026\u0026 node.right !== null) {\r\n      node = node.right\r\n    }\r\n    return node.key\r\n  }\r\n  return null\r\n}\r\n```\r\n\r\n#### 查找：\r\n\r\n```js\r\nfunction search(key) {\r\n  return searchNode(root, key)\r\n}\r\n\r\nfunction searchNode(node, key) {\r\n  if(node === null) \r\n    return false\r\n  if(key \u003c node.key) {\r\n    return searchNode(node.left, key)\r\n  } else if(key \u003e node.key) {\r\n    return searchNode(node.right, key)\r\n  } else {\r\n    return true\r\n  }\r\n}\r\n```\r\n\r\n#### 删除：\r\n\r\n```js\r\nfunction remove(key) {\r\n  root = removeNode(root, key)\r\n}\r\n\r\nfunction removeNode(node, key) {\r\n  if(node === null) \r\n    return null\r\n  if(key \u003c node.key) {\r\n    return removeNode(node.left, key)\r\n  } else if(key \u003e node.key) {\r\n    return removeNode(node.right, key)\r\n  } else {\r\n    // key = node.key 删除\r\n    //叶子节点\r\n    if(node.left === null \u0026\u0026 node.right === null) {\r\n      node = null\r\n      return node\r\n    }\r\n    // 只有一个子节点\r\n    if(node.left === null) {\r\n      node = node.right\r\n      return node\r\n    }\r\n    if(node.right === null) {\r\n      node = node.left\r\n      return node\r\n    }\r\n    // 有两个子节点\r\n    // 获取右子树的最小值替换当前节点\r\n    let minRight = findMinNode(node.right)\r\n    node.key = minRight.key\r\n    node.right = removeNode(node.right, minRight.key)\r\n    return node\r\n  }\r\n}\r\n\r\n// 获取 node 树最小节点\r\nfunction findMinNode(node) {\r\n  if(node) {\r\n    while(node \u0026\u0026 node.right !== null) {\r\n      node = node.right\r\n    }\r\n    return node\r\n  }\r\n  return null\r\n}\r\n```\r\n\r\n#### 中序遍历：\r\n\r\n顾名思义，中序遍历就是把根放在中间的遍历，即按先左节点、然后根节点、最后右节点（左根右）的遍历方式。\r\n\r\n由于BST树任意节点都大于左子节点值小于等于右子节点值的特性，所以 **中序遍历其实是对🌲进行排序操作** ，并且是按从小到大的顺序排序。\r\n\r\n```js\r\nfunction inOrderTraverse(callback) {\r\n  inOrderTraverseNode(root, callback)\r\n}\r\n\r\nfunction inOrderTraverseNode(node, callback) {\r\n  if(node !== null) {\r\n    // 先遍历左子树\r\n    inOrderTraverseNode(node.left, callback)\r\n    // 然后根节点\r\n    callback(node.key)\r\n    // 再遍历右子树\r\n    inOrderTraverseNode(node.right, callback)\r\n  }\r\n}\r\n\r\n// callback 每次将遍历到的结果打印到控制台\r\nfunction callback(key) {\r\n  console.log(key)\r\n}\r\n```\r\n\r\n#### 先序遍历：\r\n\r\n已经实现的中序遍历，先序遍历就很简单了，它是按根左右的顺序遍历\r\n\r\n```js\r\nfunction preOrderTraverse() {\r\n  preOrderTraverseNode(root, callback)\r\n}\r\n\r\nfunction preOrderTraverseNode(node, callback) {\r\n  if(node !== null) {\r\n    // 先根节点\r\n    callback(node.key)\r\n    // 然后遍历左子树\r\n    preOrderTraverseNode(node.left, callback)\r\n    // 再遍历右子树\r\n    preOrderTraverseNode(node.right, callback)\r\n  }\r\n}\r\n\r\n// callback 每次将遍历到的结果打印到控制台\r\nfunction callback(key) {\r\n  console.log(key)\r\n}\r\n```\r\n\r\n#### 后序遍历：\r\n\r\n后序遍历按照左右根的顺序遍历，实现也很简单。\r\n\r\n```js\r\nfunction postOrderTraverse() {\r\n  postOrderTraverseNode(root, callback)\r\n}\r\n\r\nfunction postOrderTraverseNode(node, callback) {\r\n  if(node !== null) {\r\n    // 先遍历左子树\r\n    postOrderTraverseNode(node.left, callback)\r\n    // 然后遍历右子树\r\n    postOrderTraverseNode(node.right, callback)\r\n    // 最后根节点\r\n    callback(node.key)\r\n  }\r\n}\r\n\r\n// callback 每次将遍历到的结果打印到控制台\r\nfunction callback(key) {\r\n  console.log(key)\r\n}\r\n```\r\n\r\n### 三、BST树的局限\r\n\r\n在理想情况下，二叉树每多一层，可以存储的元素都增加一倍。也就是说 n 个元素的二叉搜索树，对应的树高为 O(logn)。所以我们查找元素、插入元素的时间也为 O(logn)。\r\n\r\n当然这是理想情况下，但在实际应用中，并不是那么理想，例如一直递增或递减的给一个二叉查找树插入数据，那么所有插入的元素就会一直出现在一个树的左节点上，数型结构就会退化为链表结构，时间复杂度就会趋于 O(n)，这是不好的。\r\n\r\n而我们上面的平衡树就可以很好的解决这个问题，所以平衡二叉查找树（AVL树）由此诞生。","author":{"url":"https://github.com/sisterAn","@type":"Person","name":"sisterAn"},"datePublished":"2020-07-21T12:34:39.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":2},"url":"https://github.com/87/JavaScript-Algorithms/issues/87"}