二进制搜索树(BST)

介绍

在一个正常的家庭中,我们有父母和孩子。 父母恰好是团长,孩子们也效仿。 另一方面,除非是双胞胎,否则孩子的年龄是男性还是女性。 这几乎类似于数据结构中二进制树的排列。

二进制搜索树(BST)是一棵树,其中的节点遵循符合以下两个规则的特定顺序:

1.节点的左子树的值小于或等于其父节点的值(≤)。

2.节点的右子树的值(>)大于其父节点的值。

从这两个规则,我们可以推断出二叉搜索树将子树分为左子树和右子树。

在上图中,根节点值为11。

  • 左侧子树中的数据为:[6,2,7]
  • 所有数据元素均小于11
  • 右侧子树中的数据为:[20,18]
  • 所有数据元素均大于11
  • 数据= 6个子节点的根节点也满足指定的顺序,并且节点= 20。

编程中的节点

二叉树运算

共有三种二进制操作: 元素插入元素删除元素查找

1. 元素插入

顾名思义,它涉及插入或添加元素。 为此,请先找到其正确位置。 从根节点开始搜索,然后如果数据小于键值,则在左侧子树中搜索空位置并插入数据。 否则,请在右侧子树中搜索空白位置并插入数据。

2. 元素搜索/查找

可以通过深度优先宽度优先进行搜索广度优先是指水平移动; 我们从根开始,然后是左孩子,然后是右孩子。 然后移动到下一个级别,我们先遍历左孩子,然后遍历右孩子。 深度优先搜索涉及以指定的方式向下移动BST,即Pre-order,In-order或Post-order。 我们将很快讨论差异。

如上所述,我们现在来看一下三种深度优先遍历方法之间的区别:

预购–先遍历父级,然后遍历左子级,最后遍历右子级。

按顺序遍历左孩子,然后遍历父对象,最后遍历右孩子。

后置订单遍历左侧的孩子,然后遍历右侧的孩子,再遍历父对象。

3. 元素删除

这涉及从二叉树中删除节点或元素。 删除节点后,必须重新排列其余节点,以确保它们遵循二进制搜索树的必需规则。 当一个节点有两个孩子而不是一个孩子一个孩子时,这会更容易。

  • 如果有两个孩子的节点,请记住 无法将较大的节点向下移动,我们将其替换为下一个国王元素。 我们必须在右侧找到比左侧孩子大的最小右侧孩子。
  • 如果该节点有一个子节点,则必须取一个节点并替换已删除的节点。

结论

BST结构是一种有趣的抽象数据结构,具有许多用途,例如以一种有组织的方式存储数据,以便我们可以更快地找到数据(因为数据是在树中组织的)。 这对于查询非常有用,因为查询中存储了大量数据,并且您希望尽快访问它。 总体而言,BST是计算机科学家学习的非常有用的数据结构。 感谢您的阅读!