二叉搜索树 (BST) 示例

什么是二叉搜索树？

二叉搜索树是一种高级算法，用于分析节点及其左分支和右分支（这些分支以树结构建模并返回值）。BST 是基于基本二叉搜索算法的架构设计的；因此，它可以更快地查找、插入和删除节点。这使得程序非常快速和准确。

二叉搜索树的属性

BST 由多个节点组成，包含以下属性：

树的节点以父子关系表示
每个父节点可以有零个子节点，或者左侧和右侧最多有两个子节点或子树。
每个子树（也称为二叉搜索树）在其右侧和左侧都有子分支。
所有节点都通过键值对链接起来。
左子树上节点的键小于其父节点的键
类似地，左子树节点的键的值小于其父节点的键的值。

有主节点或父级 11。在它下面，有左、右节点/分支，它们有自己的键值
右子树的键值大于父节点
左子树的值大于父节点的值

为什么我们需要二叉搜索树？

使二叉搜索树成为任何实际问题的最佳解决方案的两个主要因素是速度和准确性。
由于二分查找是具有父子关系的分支格式，因此算法知道需要在树的哪个位置搜索元素。这减少了程序为找到所需元素而必须进行的键值比较次数。
此外，如果要搜索的元素大于或小于父节点，节点知道要搜索树的哪一侧。原因是，左子树始终小于父节点，而右子树的值始终等于或大于父节点。
BST 通常用于实现复杂的搜索、强大的游戏逻辑、自动完成活动和图形。
该算法有效地支持搜索，插入和删除等操作。

二叉树的类型

二叉树有三种类型：

完全二叉树：树中所有层级都充满最后一层可能出现的异常。同样，所有节点也都充满，指向最左边。
满二叉树：除叶子节点外，所有节点都有 2 个子节点。
平衡二叉树或完美二叉树：树中的所有节点都有两个子节点。此外，每个子节点的级别相同。

进一步了解数据结构中的二叉树我们期待你的加入！

二叉搜索树如何工作？

树总是有一个根节点和其他子节点，无论是在左侧还是右侧。算法通过将值与根及其在左子树或右子树中的其他子节点进行比较来执行所有操作。

根据要插入、搜索或删除的元素，比较之后，算法可以轻松地删除根节点的左子树或右子树。

BST 主要提供以下三种类型的操作供您使用：

搜索：从二叉树中搜索元素
插入：向二叉树中添加一个元素
删除：从二叉树中删除元素

每个操作都有自己的结构和执行/分析方法，但最复杂的是删除操作。

搜索 OperaTION

始终从根节点开始分析树，然后根据要定位的元素是小于还是大于根，进一步移动到根节点的右子树或左子树。

要搜索的元素是 10
将元素与根节点 12 进行比较，10 < 12，因此移动到左子树。无需分析右子树
现在将 10 与节点 7 进行比较，10 > 7，因此移动到右子树
然后将 10 与下一个节点（即 9）进行比较，10 > 9，在右子树子节点中查找
10 与节点中的值匹配，10 = 10，将该值返回给用户。

BST 中搜索的伪代码

search(element, root)
     if !root
    	return -1
     if root.value == element
    	return 1
     if root.value < element
    	search(element, root.right)
      else
    	search(element, root.left)

插页 OperaTION

这是一个非常直接的操作。首先，插入根节点，然后将下一个值与根节点进行比较。如果该值大于根，则将其添加到右子树，如果该值小于根，则将其添加到左子树。

有 6 个元素需要按从左到右的顺序插入到 BST 中
插入 12 作为根节点，并比较下一个值 7 和 9，以便相应地插入到右子树和左子树中
将剩余的值 19、5 和 10 与根节点 12 进行比较，并相应地放置它们。19 > 12 将其作为 12 的右子节点，5 < 12 且 5 < 7，因此将其作为 7 的左子节点。现在比较 10，10 < 12 且 10 > 7 且 10 > 9，将 10 作为 9 的右子树。

在 BST 中插入节点的伪代码

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
    	y = x
    if x.value < element.value
        x = x.right
    else
        x = x.left
    if y.value < element
    	y.right = element
    else
    	y.left = element

删除 Opera系统蒸发散

对于从 BST 中删除节点，有几种情况，例如删除根或删除叶节点。此外，删除根后，我们需要考虑根节点。

假设我们想删除一个叶子节点，我们可以直接删除它，但如果我们想删除一个根节点，我们需要用另一个节点替换根节点的值。让我们来看以下例子：

情况 1-具有零个子节点的节点：这是最简单的情况，您只需删除右侧或左侧没有其他子节点的节点。
情况 2 - 具有一个子节点：一旦删除该节点，只需将其子节点与已删除值的父节点连接起来。
情况 3 有两个子节点：这是最困难的情况，它遵循以下两个规则
3a – 按顺序前置节点：需要删除具有两个子节点的节点，并将其替换为已删除节点左子树上的最大值
3b – 按顺序后继：您需要删除具有两个子节点的节点，并将其替换为已删除节点右子树上的最大值

这是第一种删除没有子节点的删除情况。如图所示，19、10 和 5 没有子节点。但我们将删除 19。
删除值 19 并从节点中删除链接。
查看没有 19 的 BST 新结构

这是第二种删除情况，其中删除了一个具有 1 个子节点的节点，如您在图中所见，9 有一个子节点。
删除节点 9，用其子节点 10 替换，并添加从 7 到 10 的链接
查看没有 9 的 BST 新结构

这里你将删除具有两个子节点的节点 12
节点的删除将按照顺序前驱规则进行，这意味着左子树上最大的元素 12 将替换它。
删除节点 12 并将其替换为 10，因为它是左子树上的最大值
查看删除12之后BST的新结构

1 删除具有两个子节点的节点 12
2 节点的删除将根据顺序后继规则进行，这意味着右子树上的最大元素 12 将替换它
3 删除节点 12 并将其替换为 19，因为它是右子树上的最大值
4 查看删除12后BST的新结构

删除节点的伪代码

delete (value, root):
    Node x = root
    Node y = NULL
# searching the node
    while x:
    	y = x
    if x.value < value
        x = x.right
    else if x.value > value
        x = x.left
    else if value == x
        break
# if the node is not null, then replace it with successor
    if y.left or y.right:
    	newNode = GetInOrderSuccessor(y)
    	root.value = newNode.value
# After copying the value of successor to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

重要条款

插入：在树中插入元素/创建树。
搜索：在树中搜索元素。
前序遍历：以前序方式遍历树。
中序遍历：按顺序遍历树。
后序遍历：以后序方式遍历树。

结语

BST 是一种高级算法，它根据节点值与根节点的比较执行各种操作。
父子层次结构中的任何点都代表节点。至少一个父节点或根节点始终存在。
有左子树和右子树。左子树包含小于根节点的值。但是，右子树包含大于根节点的值。
每个节点可以有零个、一个或两个子节点。
二叉搜索树有助于执行搜索、插入和删除等主要操作。
删除是最复杂的，有多种情况，例如，没有子节点的节点、有一个子节点的节点和有两个子节点的节点。
该算法应用于游戏、自动完成数据和图形等现实世界的解决方案中。