经验总结

  1. 首页 > 生活 > >

二叉搜索树 - C++ 实现( 四 )

生活百科

< scan->data ? scan->left : scan->right;}return scan; } TreeNode *&p_find_ref(const int item) {TreeNode *scan = root;TreeNode *prev = nullptr;while (scan != nullptr && scan->data != item){prev = scan;scan = item < scan->data ? scan->left : scan->right;}if (root->data == item) return root;if (!scan) return (TreeNode *&) empty;return prev->left == scan ? (*prev).left : (*prev).right; } TreeNode *p_pred(int item) {TreeNode *itemNode = p_find(item);if (!itemNode)return nullptr;if (itemNode->left){return p_max(itemNode->left);}else{TreeNode *scan = itemNode->parent;while (scan && scan->left == itemNode){scan = scan->parent;itemNode = itemNode->parent;}return scan;} } TreeNode *p_succ(int item) {TreeNode *itemNode = p_find(item);if (!itemNode)return nullptr;if (itemNode->right){return p_min(itemNode->right);}else{TreeNode *scan = itemNode->parent;while (scan && scan->right == itemNode){scan = scan->parent;itemNode = itemNode->parent;}return scan;} } TreeNode *p_succ(TreeNode *itemNode) {if (itemNode->right){return p_min(itemNode->right);}else{TreeNode *scan = itemNode->parent;while (scan && scan->right == itemNode){scan = scan->parent;itemNode = itemNode->parent;}return scan;} } TreeNode *p_max(TreeNode *node) {if (!node)return nullptr;while (node->right){node = node->right;}return node; } TreeNode *p_min(TreeNode *node) {if (!node)return nullptr;while (node->left){node = node->left;}return node; }};结构分析 Analysis总结上文提到的所有操作, 对 BST 的每一步操作都是向树的深处再进一层, 而每一次进入一颗子树都意味着筛选掉了当前树中的一半节点, 对剩下来的一半节点继续操作.(二分思想)
由此, 我们可以容易的的得到一个结论: BST 中的最大查找次数取决于 BST 的最大深度, 即树高. 在最好情况下, 一个有着 n 个节点的树, 他的深度最小为 \(\log_2 n\). 此时, BST 可以达到最高效率.
但如果不是最好的情况呢? 很多时候 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++ 实现】

经验总结扩展阅读


上一篇：新鲜青豆焯水几分钟

下一篇：双子座和白羊座性格能相处吗