但如果不是最好的情况呢? 很多时候 BST 生成的树不会是理想的, 常常会有一些不满的子树, 产生额外的深度. 此时, BST 就会退化成更低级的数据结构. 也就是说, 这个数据结构的时间复杂度下限为 \(\Omega(\log n)\), 而其上限仍然为 O(n), 与数组和链表差不多. (甚至插入删除还不如链表的 O(1).)
具体来说, 实际上, BST 的结构与插入元素的顺序有着很大的关系. 举个例子, 同一组数列的不同排列可以形成不同的树. 虽然他们序列中元素都是相同的, 但是生成的树的结构却不尽相同. 当插入元素的顺序已然有序的时候. 根据在基本操作中插入操作的实现. 此时, 在形成的树中, 元素只会在树的一侧堆积. 也就是说, 这个时候 BST 会退化成一个单链表. 使得操作效率大大降低.
那么怎么才能让 BST 的深度尽量的小呢? 具体地说, 是否有解决方案可以让 BST 保证每次的插入都可以调整成最优的结构, 不再退化成链表?
是有的! 平衡树的提出解决了 BST 的退化问题. 通过保证树中每一个节点的左右子树高度尽可能相同. 可以使整颗树的深度近似等于前文提到的最小深度\(\log_2 n\).
本文中不再作详细讨论, 感兴趣可以自行搜索相关信息.
? 参考资料 ReferenceWikipedia - 二叉搜索树 - 维基百科, 自由的百科全书 (wikipedia.org)
Wikipedia - Binary search tree - Wikipedia
OI-Wiki - AVL 树 - OI Wiki (oi-wiki.org)
【二叉搜索树 - C++ 实现】
推荐阅读
- 原神掣电树传送点怎么开启
- 原神梦境与树任务怎么完成
- 野火 STM32MP157 开发板内核和设备树的编译烧写
- 原神探索莎兰树的梦任务怎么完成
- FHQ Treap 详解
- 原神3.0成就众花园中的一棵核桃树怎么完成
- 原神梦境与树前往指定地点任务怎么完成
- 树的邻接矩阵、双亲孩子表示法…… C++ 不知树系列之初识树
- C#实现生成Markdown文档目录树
- 给 hugo 博客添加搜索功能