二进制搜索树简介小小书 XXshu

创建二进制搜索树

本周，我们将首先看一下二叉搜索树。到本文结尾，我们将对如何创建二进制搜索树以及如何为其分配新值有更好的了解。

什么是二叉搜索树？

二进制搜索树（BST）或多或少是一种存储项目（或节点）集合的数据结构。节点通常由3个主要键/值对组成：值，左和右。通过将节点的value属性与其相邻节点的value属性进行比较来确定节点的位置。值小于当前节点值的所有节点都将放置在当前节点的左侧，而值大于当前节点值的所有节点都将放置在当前节点的右侧。如果目前尚不清楚，请继续阅读，我们将详细介绍如何订购它们，但现在请看一下上面的图片。请注意，8（在本例中是BST的根）在其左侧排列的所有小于8的值，而在其右侧放置的所有大于8的值。

通过以这种方式构造数据，我们能够：

保持导航，插入和删除速度到O（logN），其中N是树中的节点数
确保按键已订购
按范围搜索（限制搜索。例如，如果我们知道目标大于或等于25且小于或等于50，则从25 => 50进行搜索，而不是1 => 100）

创建一个BST

今天，我们将重点关注如何创建BST以及如何向其添加新节点（在BST中搜索和删除节点将在以后的文章中介绍）。还记得上面包含的BST图片吗？让我们尝试重新创建它。我们需要的只是创建节点的方法，创建BST的方法以及将这些节点添加到BST的方法。

节点数

如上所述，节点通常具有3个主要属性： left ， right和value 。 value将存储节点的value 。 left和right属性将存储在树上找到的其他节点，将较小的值分配给left ，将较大的值分配给right 。

让我们继续创建一个Node类，用它来实现我们的示例：

 类Node { 
 构造函数（val）{ 
  this.value = val 
  this.left = null 
  this.right = null 
  } 
  }

很简单吗？当我们调用Node的构造函数时，我们将为其传递一个值，并将该值分配给Node的value属性。 Node的left和right属性将初始化为null 。

二进制搜索树

现在，我们有了一种方法来创建要添加到BST中的节点。让我们定义新类并为其提供构造函数：

 类BinarySearchTree { 
  constructor（）{ 
  this.root = null; 
  } 
  }

现在，我们的BST具有root属性，但是它缺乏任何使用功能。让我们使其添加自己的Node：

 类BinarySearchTree { 
  constructor（）{ 
  this.root = null 
  } 

  addNode（val）{ 
  var root = this.root

  if（！root）{ 
  this.root =新Node（val） 
 返回 
  } 
  } 
  }

addNode()函数在这里做两件事。首先，它将BST的root属性存储为变量。接下来，它正在检查是否已为root分配了值。如果根目录具有false-y值，我们将实例化一个新的Node，并将传递给BNode的root属性的值传递给addNode（）调用。

因此，我们的BST可以为自己分配一个根节点 ，但是我们仍然需要树为节点添加正确的left或right属性的方法。这个过程稍微复杂一点，但是通过花一些时间阅读代码，它应该会变得清晰起来。

请务必记住，我们将要跟踪当前正在检查的Node（ currentNode ）以及通过addNode()实例化的新Node（ newNode addNode() 。从那里开始，我们将使用currentNode并将其与循环一起使用，通过将newNode的value属性与currentNode的left和/或right属性进行比较，为newNode查找正确的位置。

看起来怎么样？首先，使BST能够将其值小于根节点值的节点添加到其自身。如果newNode的值小于currentNode的值，则仅当currentNode没有为其左属性分配任何东西时，才将newNode分配为currentNode.left的值。如果currentNode的left属性已经有一个值，则将currentNode分配为与currentNode相等，然后重复此过程。

 类BinarySearchTree { 
  constructor（）{ 
  this.root = null 
  } 

  addNode（val）{ 
  var root = this.root

  if（！root）{ 
  this.root =新Node（val） 
 返回 
  }

  var currentNode =根 
  var newNode =新Node（val）

  while（currentNode）{ 
  if（val <currentNode.value）{ 
  if（！currentNode.left）{ 
  currentNode.left = newNode 
 打破 
  }其他{ 
  currentNode = currentNode.left 
  } 
  } 
  } 
  } 
  }

这是添加逻辑后树的示例：

因此，现在我们可以添加价值较小的节点。让我们添加一些功能以启用添加更大价值的节点。逻辑将与添加较小值的Node的逻辑非常相似-如果newNode 值不小于currentNode 值，我们现在将其放置在右侧而不是左侧：

 类BinarySearchTree { 
  constructor（）{ 
  this.root = null 
  }

  addNode（val）{ 
  var root = this.root

  if（！root）{ 
  this.root =新Node（val） 
 返回 
  }

  var currentNode = root; 
  var newNode =新Node（val）

  while（currentNode）{ 
  if（val <currentNode.value）{ 
  if（！currentNode.left）{ 
  currentNode.left = newNode; 
 打破; 
  }其他{ 
  currentNode = currentNode.left 
  } 
  }其他{ 
  if（！currentNode.right）{ 
  currentNode.right = newNode; 
 打破; 
  }其他{ 
  currentNode = currentNode.right 
  } 
  } 
  } 
  } 
  }

现在我们可以将Nodes添加到其他Node的left和right属性中，让我们看看如何将这些Node添加到树中：

还记得我曾说过我们将根据先前发布的图像创建树吗？

让我们继续前进。我将首先调用addNode(8)来分配BST的root属性。从那里我们可以跟随树的分支并相应地添加值：

结论

尽管确实需要一些实践和对代码的一到几次审查，但是BST并非超出我们的理解范围。通过比较currentNode和newNode ，我们可以相应地在树中分配每个Node的位置。

附加材料

下面包括一个指向此文章用作模型的存储库的链接。如有必要，请随时参考。

GitHub回购：https://github.com/christopher-hague/Binary-Search-Tree-Intro