此篇算是用C++讲高阶数据结构第一篇,在C++完结之前高阶数据结构内容都放在④⑤两个专栏,等后面C++完结还会学图和算法的内容。
先讲二叉搜索树是因为讲解 map 和 set 的特性需要二叉搜索树做铺垫,理解搜索二叉树有助于更好地理解 map 和 set 的特性。第二个原因是为了后期讲解查找效率极高的平衡搜索二叉树,随后再讲完红黑树,我们就可以模拟实现 map 和 set 了。
1. 二叉搜索树(BinarySearchTree)
概念:搜索二叉树(二叉搜索树)又称为二叉排序树,它或者是一颗空树,
或者是具有以下性质的二叉树:
- 若其左子树不是空,则左子树上所有节点的值都小于根结点的值
- 若其右子树不是空,则右子树上所有结点的值都大于根结点的值
- 其左右子树必须都是二叉搜索树
至于叫它 "搜索二叉树",还是 "二叉搜索树",都是可以的,就是叫搜索二叉树的英文缩写不太好。
结论:任意一个子树都需要满足,左子树的值 < 根 < 右子树的值,才能构成二叉搜索树。
1.1 二叉搜索树的优势和劣势
既然叫搜索二叉树,它肯定是用来搜索的,当满足搜索二叉树时你将可以快速地查找任意的值。
举个例子: 查找7
放到以前我们如果不用二分查找,可能会选择用暴力的方式去从头到尾遍历一遍。
但现在学了搜索二叉树,我们就可以轻松找到这个7了,7 比 8(根节点) 小,
根据搜索二叉树的性质,它必然不会出现在右子树 (右边大) ...
搜索二叉树查找一个值的最坏情况,也只是查找高度次。
二叉搜索树的时间复杂度:O(N)
上面的例子会让人误以为搜索二叉树的增删查改的时间复杂度是O(logN),
但实际上是O(N),因为这棵树是有可能会 蜕化 的,极端情况下会蜕化成一个 "单边树"
比如按有序插入:
最差情况:二叉搜索树退化为单边树(或类似单边),其平均比较次数为:O(N)
最优情况:二叉搜索树为完全二叉树(或接近完全二叉树),其平均比较次数为:O(logN)
对于时间复杂度的分析我们要做一个悲观主义者,根据最差情况去定时间复杂度:O(N)
1.2 二叉搜索树的改良
如果搜索二叉树退化成了单边树,其性能也就失去了,能否进行改进让它保持性能?
如何做到不论按照上面次序插入关键码,二叉搜索树的性能均能达到最优?
搜索二叉树由于控制不了极端情况,与 O(logN)失之交臂,但平衡二叉搜索树做到了。
严格意义上来说满二叉树才是O(logN),完全二叉树是接近O(logN)。
而平衡搜索二叉树维持左右两边均匀程度,让它接近完全二叉树,从而让效率趋近O(logN)。
后面我们学的各种树(AV树,红黑树)可以说都是二叉搜索树的改良。
2. 二叉搜索树的实现
2.1 二叉搜索树的定义
此时我们的BinarySearchTree就缩写成BSTree了。
这里我们用模板,模板参数我们给了一个K,表示 key 的意思(模板参数并非一定要用 T)。
template<class K> class BSTreeNode { public: BSTreeNode(const K& key) :_left(nullptr) , _right(nullptr) , _key(key) {} BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; };
下面我们来定义整个树,BSTreeNode 有些长了,这里将其 typedef 成 Node 。
构造函数都没必要写,它自己生成的就够用了:
template<class K> class BSTree { typedef BSTreeNode<K> Node; protected: Node* _root = nullptr; };
2.2 二叉搜索树的插入
二叉搜索树的插入是会“去重”的。
我们先来实现最简单的插入操作:
- 如果树为空,则直接新增结点,赋值给 root 指针。
- 如果树不为空,按二叉搜索树性质查找插入位置,插入新节点。
Insert 的实现我们可以用递归,也可以用非递归,这一块递归比非递归更难理解。
秉着先难后易的态度,我们先讲比较难理解的非递归版本
Step1:首先检查是否有根结点 _root,如果没有我们就 new 一个结点出来作为根结点。此时插入成功,返回 true。
Step2:插入就需要找到插入位置,我们定义一个 cur 变量,从根节点开始,
根据搜索二叉树 性质,将 cur 结点的值与插入的值 进行大小比较。
如果插入的值大于当前结点值,则将 cur 结点向右移动 cur=cur->_right ;
如果插入的值小于当前节点值,就将 cur 结点向左移动 cur=cur->_left。
值得注意的是,还需要额外记录一下 cur 的父结点,
因为你不知道什么时候会碰到nullptr结束。
并且当我们找到插入位置后,仅仅 new 上一个新结点给 cur 是完成不了插入操作的。
因为直接这么做 cur 也只是一个局部变量而已,需要 cur 跟上一层(cur 的父亲)相链接才行。
为了能找到上一层,所以我们还需要额外定义一个 prev 变量来记录 cur 的父结点,
在我们更换 cur 结点时记录父结点的位置 prev=cur 即可。
当然了,还有一种插入失败的情况,就是判断大小时出现等于的情况,返回 false 即可。
(重复的值是不允许插入的,默认情况是不允许冗余的!但是也有针对这个的变形,后续再说)
Step3:插入。new 一个新结点给 cur,此时 cur 只是一个局部变量,必须要和父亲链接,
此时应该链接父亲的左边,还是链接父亲的右边?我们不知道,所以我们需要再做一个比较:
如果父节点的值大于插入的值,则将 cur 链接到父亲左边 prev->_left=cur;
反之将 cur 链接到父亲右边 prev->_right=cur。
最后,插入成功返回 true。
insert 代码:
bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* prev = nullptr; Node* cur = _root; while (cur != nullptr) // 找到要插入的位置 { if (key < cur->_key) // 要插入的值比当前值小 { prev = cur; // 记录cur,等下cur更新就是cur的父亲 cur = cur->_left; // 到左边插入 } else if (key > cur->_key) { prev = cur; cur = cur->_right; } else { return false; // 相等,插入失败 } } cur = new Node(key); // 走到这,cur就是要插入的位置 if (key < prev->_key) // 如果key比cur的父亲小 { prev->_left = cur; // 插入到父亲的左孩子 } else { prev->_right = cur; } return true; }
再写一个中序遍历来测试一下插入的效果:
void InOrder(Node* root) { if (root == nullptr) { return; } InOrder(root->_left); cout << root->_key << " "; InOrder(root->_right); }
模拟出一个测试用例:
void TestBSTree1() { BSTree<int> t; int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 }; for (const auto& e : a) { t.Insert(e); } t.InOrder(); // 没法传根 }
此时会出现一个问题,因为根是私有的,我们没办法把根传过去。
此时我们可以选择在类内部写一个成员函数 GetRoot 去取根,但是这里我们可以选择这么做:
干脆将刚才我们实现的中序设为 protected 保护,然后再写一个 InOrder 放在公有的区域。
这就是在类内访问 _root 了,没有什么问题。
如此一来我们在类外就可以直接调用 InOrder,并且也不需要传递参数了。
BinarySearchTree.h:
#pragma once #include <iostream> using namespace std; template<class K> class BSTreeNode { public: BSTreeNode(const K& key) :_left(nullptr) , _right(nullptr) , _key(key) {} BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; }; template<class K> class BSTree { typedef BSTreeNode<K> Node; public: bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* prev = nullptr; Node* cur = _root; while (cur != nullptr) // 找到要插入的位置 { if (key < cur->_key) // 要插入的值比当前值小 { prev = cur; // 记录cur,等下cur更新就是cur的父亲 cur = cur->_left; // 到左边插入 } else if (key > cur->_key) { prev = cur; cur = cur->_right; } else { return false; // 相等,插入失败 } } cur = new Node(key); // 走到这,cur就是要插入的位置 if (key < prev->_key) // 如果key比cur的父亲小 { prev->_left = cur; // 插入到父亲的左孩子 } else { prev->_right = cur; } return true; } void InOrder() { _InOrder(_root); cout << endl; } protected: void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } Node* _root = nullptr; };
Test.c:
#include "BinarySearchTree.h" void TestBSTree1() { BSTree<int> t; int arr[] = { 8, 3, 1, 10, 2, 2, 3, 6, 4, 7, 14, 13 }; for (const auto& e : arr) { t.Insert(e); } t.InOrder(); } int main() { TestBSTree1(); return 0; }
2.3 二叉搜索树的查找
二叉搜索树的查找 Find 实现很容易,用和刚才一样的思路,从根结点开始查找。
从根开始,如果要查找的值大于 cur 目前的值,则让 cur 往右走,反之往左走。
当查找得值与 cur 的值相等时则说明找到了,返回 true。
当 cur 触及到空(while 循环结束)则说明找不到,返回 false。
代码:
bool Find(const K& key) { Node* cur = _root; while (cur != nullptr) { if (key < cur->_key) { cur = cur->_left; } else if (key > cur->_key) { cur = cur->_right; } else { return true; } } return false; }
从C语言到C++_24(二叉搜索树)概念+完整代码实现+笔试题(中):https://developer.aliyun.com/article/1521942?spm=a2c6h.13148508.setting.21.50c04f0eHmAr4x