数据结构与算法

数据结构与算法知识详解
帅旋
关注
充电
IT宅站长,技术博主,架构师,全网id:arthinking。

二叉树数据结构

发布于 2020-04-28 | 更新于 2024-05-16

9、二叉树与二叉搜索树BST

**二叉树(Binary Tree)**是每个节点最多具有两个子节点的树;

**二叉搜索树(Binary Search Tree)**是满足以下条件二叉树:左子树的元素较小,右子树的元素较大。

image-20200416073440886

9.1、使用场景

  • 某些map和set的ADT的实现;
  • 红黑树;
  • AVL树;
  • 伸展树(Splay Tree 分裂树);
  • 用于二叉堆的实现;
  • 语法树;
  • Treap-概率DS(使用随机BST)

9.2、实现思路

9.2.1、插入元素

  • 二叉搜索树(BST)元素必须具有可比性,以便我们可以在树中对其进行排序;
  • 插入元素时,我们将其值与当前节点中存储的值进行比较:
    • 小于节点值:向下递归左子树;
    • 大于节点值:向下递归右子树;
    • 等于节点值:处理重复值;
    • 不存在节点:创建新节点。

极端场景:

image-20200415231429075

这种情况就变为了线性结构,比较糟糕,这就是平衡二叉搜索树出现的原因。

9.2.2、移除元素

移除元素可以分为两步:

  • 找到我们想要移除的元素;
  • 如果存在后续节点,那么我们用后续节点替换掉要删除的节点;

移除会有以下三种情况:

9.2.2.1、移除的元素是一个叶子节点

找到对应待移除的节点,直接删除掉即可:

remove(16):

image-20200416074239465

9.2.2.2、移除的元素下面有左子树或者右子树

如果移除的元素下面带有左子树或者右子树,那么:找到对应待移除的节点,用子树的根节点作为移除元素的后继者,替换掉需要移除的元素即可:

image-20200416075026232

9.2.2.3、移除的元素下面有左子树和右子树

如果移除的元素下面带有左子树和右子树,那么应该用左子树还是右子树中的节点作为删除元素的后继者呢?

答案是两者都可以! 后继者可以是左侧子树中的最大值,也可以是右侧子树中的最小值。

下面我们执行remove(8),统一选择使用右子树中的最小值。

具体步骤:

  1. 查找到需要删除的元素;

  2. 在其右子树中寻找到最小值的节点;

    image-20200416081647552

  3. 最小值的节点和待删除元素的值互换;

  4. 使用9.2.2.2的步骤删除掉原来最小值节点位置的节点;

image-20200416082027262

9.2.3、查找元素

BST搜索元素会出现以下四种情况之一:

  • 我们命中了一个空节点,这时我们知道该值在我们的BST中不存在;
  • 比较器值等于0,说明找到了元素;
  • 比较器值小于0,说明元素在左子树中;
  • 比较器值大于0,说明元素在右子树中。

以下是find(6)操作:

image-20200416073145881

9.3、树的遍历

可以分为深度优先遍历和广度优先遍历。而深度优先遍历又分为:前序遍历、中序遍历、后序遍历、层序遍历。

9.3.1、深度优先遍历

深度优先遍历都是通过递归来实现的,对应的数据结构为栈。

9.3.1.1、前序遍历

在递归方法最开始处理节点信息,代码逻辑:

1
2
3
4
5
6
void preOrder(node) {
if (node == null) return;
print(node.value);
preOrder(node.left);
preOrder(node.right);
}

如下二叉树将得出以下遍历结果:A B D H I E J C F K G

image-20200416215933995

9.3.1.2、中序遍历

在递归调用完左子节点,准备右子节点之前处理节点信息,代码逻辑:

1
2
3
4
5
6
void inOrder(node) {
if (node == null) return;
inOrder(node.left);
print(node.value);
inOrder(node.right);
}

二叉搜索树使用中序遍历,会得到一个排好序的列表。

以下二叉搜索树将得出如下遍历结果:1 3 4 5 6 7 8 15 16 20 21

image-20200416220244870

9.3.1.3、后序遍历

在递归完左右子树之后,再处理节点信息,代码逻辑:

1
2
3
4
5
6
void postOrder(node) {
if (node == null) return;
postOrder(node.left);
postOrder(node.right);
print(node.value);
}

以下二叉树得出如下遍历结果:1 4 3 6 7 5 16 15 21 20 8

image-20200416220244870

9.3.2、广度优先遍历

在广度遍历中,我们希望一层一层的处理节点信息,常用的数据结构为队列。每处理一个节点,同时把左右子节点放入队列,然后从队列中取节点进行处理,处理的同时把左右子节点放入队列,反复如此,直至处理完毕。

9.4、BST时间复杂度

操作 平均 最差
insert O(log(n)) O(n)
delete O(log(n)) O(n)
search O(log(n)) O(n)

9.5、编程实践

本文作者: 帅旋

本文链接: https://www.itzhai.com/columns/dsa/binary-tree.html

版权声明: 版权归作者所有,未经许可不得转载,侵权必究!联系作者请加公众号。

×
IT宅

关注公众号及时获取网站内容更新。

请帅旋喝一杯咖啡

咖啡=电量,给帅旋充杯咖啡,他会满电写代码!

IT宅

关注公众号及时获取网站内容更新。