二叉搜索树的特点、插入、查询和删除操作

terry 2年前 (2023-09-27) 阅读数 65 #数据结构与算法

二叉搜索树

二叉搜索树（BST），也称为二叉排序树，是树的一种。二叉树组织数据。每个树节点包含一个键值、一个数据值、一个指向左子节点的指针和一个指向右子节点的指针。其中，关键值是中心部分。它的值决定了树的组织形式；数据值data是该节点对应的数据。有些场景可以忽略。例如，键是身份证号，数据是人名。通过搜索人名的身份证号码；左子节点指针指向左子节点；右子节点指针指向右子节点。

二叉搜索树的特点

左右子树也是二叉搜索树。
左子树节点的所有键值均小于其根节点的键值。
右子树中所有节点的键值均大于其根节点的键值。
二叉搜索树可以是空树。
一般情况下，树中每个节点的键值都不相同，但如果需要，可以将相同的键值插入到树中。

插入操作

如果树为空，则插入的节点将是根节点。
如果树不为空，则从根节点开始，比较插入节点和根节点的键值。如果值相同则直接返回，不做任何处理。如果比较大，就继续比较右子节点R。如果比较小，就继续比较儒家节点L。。
将R的右子节点与插入的节点进行比较。如果插入节点的key值较大，则继续比较到节点R的右子节点，如果较小，则继续比较到节点R的左子节点。
这样继续往下查找直到找到左子节点指针或右子节点指针为空的节点，将插入的节点放入其中。

对于较低的树，插入D和H，

创建一个节点D并将其与根节点进行比较 D 是小于 E ，因此继续比较左子节点。

D 大于 C，必须转到右子节点。目前节点C的右子节点指针为空，可以将节点D放入其中。

节点H同理，先创建节点H并与根节点进行比较。

H大于E，所以继续与右子节点比较。

H比G大，所以应该是右子节点方向，而目前G的右子节点指针为空，可以将节点H放入其中。

插入顺序

二叉搜索树的形状可能会根据节点插入的顺序而变化。例如，对于这些节点集，Ab c d e f gh，如果将节点集插入以ec a b d g fh的顺序插入，则如果您交换前两个节点，并将它们插入了。 C E A B D G F H，形状差异相当大，如下图。

极端情况下，请按照A B C D E F G H的顺序插入。然后

查询操作

从根节点开始，比较查询节点和根节点的key值；如果值相等，则找到该节点并直接返回。如果大于，则继续查找R的右子节点，如果小于，则继续查找L的左子节点。
将R的右子节点与查询节点进行比较。如果查询节点的键值较大，则继续搜索节点 R 的右子节点。如果较小，则继续搜索节点 R 的左子节点。
如此继续搜索，直到找到的键值节点等于查询节点的值，则表示查找成功。如果最后没有找到，则说明该节点不存在。

对于下图中的树，找到键值为“B”和“G”的节点，

将“B”与根节点的键值进行比较，

“B”小于“E”，转到左子节点继续搜索，

“B”小于“C”，继续搜索到左子节点，

“B”大于“A”，继续查找右边的子节点，发现是相同的。

继续查询键值为“G”的节点，与根节点比较，

“G”大于“E”，转到右子节点，两者相同，找到它。

删除操作

删除操作分三种情况进行。

如果删除的节点是叶子节点，即其左子节点指针和右子节点指针为空时，可以直接删除该节点，不会影响整棵树的结构。
如果被删除的节点只有一个子节点（左子节点或右子节点），则该子节点直接提升到被删除节点的位置。
如果被删除的节点有两个子节点，则必须按照被删除节点的顺序找到后继或前驱来填充被删除的节点。按顺序的后继实际上是所有节点中大于被删除节点的最小的，而按顺序的前驱小于被删除节点中最大的，因为二叉搜索树是按顺序的-transition的升序序列，所以后继节点在被删除节点之后大于且最小的，如5中的1 2 3 4 4是后继3。前驱应删除该节点之前的节点。例如，1 2 3 4 5中的2是3的前身。？ ”，从根节点开始查找，找到节点“C”，直接将原本指向节点“C”的右子节点指针指向子节点“C”，最后，示例3 如果要删除下面树中的节点“E”，节点“E”有两个子节点，所以我们开始在其要替换的节点的顺序，前驱在左子节点“C以下最大值的节点”，要找到节点“C”以下最大值的节点，一直走到对，，直到不能再往下走，即节点“D”的前身，用节点“D”替换节点“E”，最后删除节点“E”。作者：超人王小健链接：https://juejin.im/post/5b60fd59f265da0f8d3675c5 来源：掘金版权归作者所有。商业转载请联系作者获得许可。非商业转载请注明来源。