二叉搜索树 - C++ 实现
2022/11/9 1:24:05
本文主要是介绍二叉搜索树 - C++ 实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
二叉查找树(英语:Binary Search Tree, 后文中简称 BST), 也称为二叉搜索树、有序二叉树(ordered binary tree)或排序二叉树(sorted binary tree), 是在 20 世纪 60 年代为解决标记数据的高效存储问题而设计的, 由 Conway Berners-Lee 和 David Wheeler 发明.
具体指的是一棵空树或者具有下列性质的二叉树:
- 若任意节点的左子树不空, 则左子树上所有节点的值均小于它的根节点的值;
- 若任意节点的右子树不空, 则右子树上所有节点的值均大于它的根节点的值;
- 任意节点的左、右子树也分别为二叉查找树;
简单来说, 二叉搜索树中的每一个节点都满足: 左子树中的所有元素均小于该节点元素; 右子树中的所有元素均大于该节点元素. 左子树元素≤本节点元素≤右子树元素左子树元素≤本节点元素≤右子树元素. 左小右大.
这种结构上的设计使得 BST 可以以二分查找思路实现 Ω(logn)Ω(logn) (不是大o, 而是下限在logn)级别的快速增, 删, 查等操作, 因为在树中的每一步操作都能排除一半的元素. 完成一颗二叉搜索树的建立之后, 我们还可以以中序遍历的方式得到排序后的序列, 这也是二叉搜索树被称为排序二叉树的原因.
需要注意的是, 二叉搜索树的效率与在建立时输入的元素顺序有很大的关系. 在最坏情况下, 二叉搜索树会退化成链表. 树层数大大增加使得查找等操作需要消耗更多的时间)此时, 需要对树进行额外的优化 - 平衡, 来保证高效的运行效率. 在本文中我们不作讨论, 本文仅介绍朴素的二叉搜索树.
如果看完之后还是不太理解的话, 可以看看这个美国旧金山大学CS做的一个算法可视化. Binary Search Tree Visualization (usfca.edu) 在这个网站上详细地看到 BST 每一步的操作. 做的很好, 不妨去玩玩!
这篇关于二叉搜索树 - C++ 实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!
- 2024-05-08今天开始程序员不用再发愁写commit message了,全部由CodeGeeX自动完成!