二叉树就是每个节点最多有两个分叉的树。这里我们写一写一个典型的例子二叉搜索树，它存在的实际意义是什么呢?

在P1.1链表中，我们清楚了链表的优势是善于删除添加节点，但是其取值很慢；数组的优势是善于取值，但是不利于删除添加节点。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

而二叉搜索树，正是两者的折中方案。首先，它是树状结构，因此它便于插入和删除节点，需要花费LogN级别的时间，其次，它

在每一个节点上都满足`左子树 <= 当前节点 <= 右子树`,因此便于使用二叉搜索，所以查找数据和取数据也是LogN级别的。

 

时间比较 链表 二叉搜索树 数组
取值 N LogN C
查找 N LogN 有序数组:LogN 无序数组:N
插入和删除 C LogN N

 

 

 

 

 

 

常见的二叉搜索树操作有:

1.插入新节点

2.按值查找节点

3.删除节点

4.三种遍历方式

5.二叉搜索树的宽度

6.二叉搜索树最大距离

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄