【C++指南】一文总结C++二叉搜索树

🌟 各位看官好，我是egoist2023！

🌍 种一棵树最好是十年前，其次是现在！

🚀 今天来学习C++二叉搜索树的实现。

👍 如果觉得这篇文章有帮助，欢迎您一键三连，分享给更多人哦

目录

何为二叉搜索树

性能分析 

搜索树的结构

插入和查找(非冗余版本)

中序遍历

删除

key/value

使用场景

代码实现

何为二叉搜索树

二叉搜索(排序)树具有如下特征：

• 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值；
• 若它的右⼦树不为空，则右子树上所有结点的值都大于等于根结点的值；
• 它的左右⼦树也分别为二叉搜索树；
• 二叉搜索树的中序遍历是有序的；
• 了解二叉搜索树是为了之后为map/set/multimap/multiset的关联式容器打下基础。特别地，二叉搜索树分为冗余和不冗余版本。(冗余即有相等值也可插入)

在冗余版本的二叉搜索树中，会出现如下两种情况，那这两都是正确的吗？

是的，并不影响搜索二叉树的性质。

性能分析 

可以发现在该二叉搜索树较为平衡的情况下

即在最优情况下，找到指定结点的情况下，只需要访问高度k次，即高度为： log2 N；

但在最差情况下，高度会达到N。（在红黑树章节会有详解如何平衡高度差）

综合来讲，二叉搜索树增删查改时间复杂度为： O(N)。

二分查找也能达到 log2 N 级别的查找效率，为何不使用二分查找呢？二分查找有以下缺陷：

1. 需要存储在⽀持下标随机访问的结构中，并且有序。

   平台声明：以上文章转载于《CSDN》，文章全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，仅作参考。

   版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

   原文链接：https://blog.csdn.net/egoist2023/article/details/146080046