1. 二叉搜索树的概念
二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
• 若它的左子树不为空,则左子树上所有结点的值都小于等于根结点的值。
• 若它的右子树不为空,则右子树上所有结点的值都大于等于根结点的值。
• 它的左右子树也分别为二叉搜索树。
• 二叉搜索树中可以支持插入相等的值,也可以不支持插入相等的值,具体看使用场景定义,后续我们学习map/set/multimap/multiset系列容器底层就是二叉搜索树,其中map/set不支持插入相等值,multimap/multiset支持插入相等值。
除了支不支持插入相同的值以外,二叉搜索树还可以按照其带的值分为两类:key和key/value。
key:只带一个值key
key/value:带两个相绑定的值,构建二叉树与进行查找时都以key为准。
这两种搜索二叉树的实现大同小异,接下来的介绍中我们以key类型为例,key/value类型的只需要在结点的结构中加上value即可(函数随之微调)。
2. 二叉搜索树的性能分析
二叉搜索树查找的时间复杂度与其高度相同。
最优情况下,二叉搜索树为完全二叉树(或者接近完全二叉树),其高度为:
最差情况下,二叉搜索树退化为单支树(或者类似单支),其高度为:
所以综合而言二叉搜索树增删查改时间复杂度为:
那么这样的效率显然是无法满足我们需求的,为了使二叉搜索树的搜索效率足够高,我们需要使得二叉搜索树尽可能地接近完全二叉树,于是就有了我们之后会讲到的平衡二叉搜索树,以及AVL树和红黑树等。
另外需要说明的是,二分查找也可以实现 O(logN) 级别的查找效率,但是二分查找有两大缺陷:
1. 需要存储在支持下标随机访问的结构中,并且有序。
2. 插入和删除数据效率很低,因为存储在下标随机访问的结构中,插入和删除数据一般需要挪动数据。这里也就体现出了平衡二叉搜索树的价值。
3. 二叉搜索树的实现
3.1 结点定义及二叉搜索树类的框架
template<class K>struct BSTreeNode{K _key;BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;BSTreeNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}};template<class K>class BSTree{typedef BSTreeNode<K> Node;public: //强制生成默认构造BSTree() = default; //拷贝构造BSTree(const BSTree& tree); //析构~BSTree(); //赋值重载BSTree& operator=(BSTree tree); //插入bool Insert(const K& key);//查找Node* Find(const K& key); //删除bool Erase(const K& key);//中序遍历void InOrder();private: //辅助拷贝构造进行递归拷贝Node* Construct(Node* root); //辅助析构函数进行递归释放结点void Destroy(Node* root); //辅助进行递归中序遍历void _InOrder(Node* root);private:Node* _root = nullptr;};
3.2 默认成员函数
3.2.1 构造函数
由于我们给了_root缺省值,所以编译器自动生成的默认构造函数就够用。
而拷贝构造需要我们自己实现深拷贝,即访问被拷贝的树的全部结点并拷贝链接。
对于树形结构,访问一棵树的全部结点,递归永远是最方便的选择。可是,如何在类内部设计递归函数呢?毕竟需要直接将树结点的指针作为参数才好实现递归。
这时,我们就可以选择在递归函数的外面套一层成员函数的壳。
BSTree() = default;BSTree(const BSTree& tree){_root = Construct(tree._root);}
Node* Construct(Node* root){if (root == nullptr)return nullptr;Node* copy = new Node(root->_key);copy->_left = Construct(root->_left);copy->_right = Construct(root->_right);return copy;}
3.2.2 赋值重载
有了拷贝构造,就可以考虑现代写法:
BSTree& operator=(BSTree tree){swap(_root, tree._root);return *this;}
3.2.3 析构函数
递归访问每个结点并释放,同理需要套一层外壳:
~BSTree(){Destroy(_root);_root = nullptr;}
void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}
3.3 二叉搜索树的插入
1. 树为空,则直接新增结点,赋值给root指针。
2. 树不空,按二叉搜索树性质,插入值比当前结点大往右走,插入值比当前结点小往左走,找到空位置,插入新结点。
3. 如果支持插入相等的值,插入值跟当前结点相等的值可以往右走,也可以往左走,找到空位置,插入新结点。(要注意的是要保持逻辑一致性,插入相等的值不要一会往右走,一会往左走)
下面的代码是不支持插入相等的值的情形:
bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root, *parent = nullptr;while (cur){parent = cur;if (key < cur->_key)cur = cur->_left;else if (key > cur->_key)cur = cur->_right;elsereturn false;}cur = new Node(key);if (key < parent->_key)parent->_left = cur;elseparent->_right = cur;return true;}
3.4 二叉搜索树的查找
1. 从根开始比较,查找x,x比根的值大则往右边走查找,x比根值小则往左边走查找。
2. 最多查找高度次,走到到空,还没找到,这个值不存在。
3. 如果不支持插入相等的值,找到x即可返回。
4. 如果支持插入相等的值,意味着有多个x存在,一般要求查找中序的第一个x。如下图,查找3,要找到1的右孩子的那个3返回。
3.5 二叉搜索树的删除
首先查找元素是否在二叉搜索树中,如果不存在,则返回false。
如果查找元素存在则分以下四种情况分别处理:(假设要删除的结点为N)
1. 要删除结点N左右孩子均为空
2. 要删除的结点N左孩子位空,右孩子结点不为空
3. 要删除的结点N右孩子位空,左孩子结点不为空
4. 要删除的结点N左右孩子结点均不为空
对应以上四种情况的解决方案:
1. 把N结点的父亲对应孩子指针指向空,直接删除N结点(情况1可以当成2或者3处理,效果是一样的)
2. 把N结点的父亲对应孩子指针指向N的右孩子,直接删除N结点
3. 把N结点的父亲对应孩子指针指向N的左孩子,直接删除N结点
4. 无法直接删除N结点,因为N的两个孩子无处安放,只能用替换法删除。找N左子树的值最大结点LR(最右结点)或者N右子树的值最小结点RL(最左结点)替代N,因为这两个结点中任意一个,放到N的位置,都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换,转而变成删除R结点,R结点符合情况2或情况3,可以直接删除。
另外,在每种情况中,都要注意判断被删除的结点是否为根结点_root,因为在删除的过程中需要记录被删除结点的父节点,而根节点没有父节点,在通用逻辑下会导致对空指针的访问。
bool Erase(const K& key){Node* del = _root, *parent = nullptr;while (del && del->_key != key){parent = del;if (key < del->_key)del = del->_left;elsedel = del->_right;}if (del == nullptr)return false;if (del->_left == nullptr)//左结点为空(或者左右都为空){if (parent == nullptr)//被删除的是根结点{_root = del->_right;}else if (del->_key < parent->_key)parent->_left = del->_right;elseparent->_right = del->_right;delete del;}else if (del->_right == nullptr)//右结点为空且左节点不为空{if (parent == nullptr)//被删除的是根结点{_root = del->_left;}else if (del->_key < parent->_key)parent->_left = del->_left;elseparent->_right = del->_left;delete del;}else//左右结点都不为空{Node* replace = del->_right;parent = del;while (replace->_left){parent = replace;replace = replace->_left;}del->_key = replace->_key;del->_value = replace->_value;if (parent->_right == replace)parent->_right = replace->_right;elseparent->_left = replace->_right;delete replace;}return true;}
3.6 完整代码
template<class K>struct BSTreeNode{K _key;BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;BSTreeNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}};template<class K>class BSTree{typedef BSTreeNode<K> Node;public:BSTree() = default;BSTree(const BSTree& tree){_root = Construct(tree._root);}~BSTree(){Destroy(_root);_root = nullptr;}BSTree& operator=(BSTree tree){swap(_root, tree._root);return *this;}bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root, *parent = nullptr;while (cur){parent = cur;if (key < cur->_key)cur = cur->_left;else if (key > cur->_key)cur = cur->_right;elsereturn false;}cur = new Node(key);if (key < parent->_key)parent->_left = cur;elseparent->_right = cur;return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (key == cur->_key)return cur;else if (key < cur->_key)cur = cur->_left;elsecur = cur->_right;}return nullptr;}bool Erase(const K& key){Node* del = _root, *parent = nullptr;while (del && del->_key != key){parent = del;if (key < del->_key)del = del->_left;elsedel = del->_right;}if (del == nullptr)return false;if (del->_left == nullptr){if (parent == nullptr){_root = del->_right;}else if (del->_key < parent->_key)parent->_left = del->_right;elseparent->_right = del->_right;delete del;}else if (del->_right == nullptr){if (parent == nullptr){_root = del->_left;}else if (del->_key < parent->_key)parent->_left = del->_left;elseparent->_right = del->_left;delete del;}else{Node* replace = del->_right;parent = del;while (replace->_left){parent = replace;replace = replace->_left;}del->_key = replace->_key;del->_value = replace->_value;if (parent->_right == replace)parent->_right = replace->_right;elseparent->_left = replace->_right;delete replace;}return true;}void InOrder(){_InOrder(_root);cout << endl;}private:Node* Construct(Node* root){if (root == nullptr)return nullptr;Node* copy = new Node(root->_key);copy->_left = Construct(root->_left);copy->_right = Construct(root->_right);return copy;}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root = nullptr;};
4. 二叉搜索树key和key/value的使用场景
4.1 key搜索场景
只有key作为关键码,结构中只需要存储key即可,关键码即为需要搜索到的值,搜索场景只需要判断key在不在。
key的搜索场景实现的二叉树搜索树支持增删查,但是不支持修改,因为修改key会破坏搜索树结构。
场景1:小区无人值守车库,小区车库买了车位的业主车才能进小区,那么物业会把买了车位的业主的车牌号录入后台系统,车辆进入时扫描车牌在不在系统中,在则抬杆,不在则提示非本小区车辆,无法进入。
场景2:检查一篇英文文章单词拼写是否正确,将词库中所有单词放入二叉搜索树,读取文章中的单词,查找是否在二叉搜索树中,不在则波浪线标红提示。
4.2 key/value搜索场景
每一个关键码key,都有与之对应的值value,value可以任意类型对象。
树的结构中(结点)除了需要存储key还要存储对应的value,增/删/查还是以key为关键字走二叉搜索树的规则进行比较,可以快速查找到key对应的value。
key/value的搜索场景实现的二叉树搜索树支持修改,但是同样不支持修改key,可以修改value。
场景1:简单中英互译字典,树的结构中(结点)存储key(英文)和vlaue(中文),搜索时输入英文,则同时查找到了英文对应的中文。
场景2:商场无人值守车库,入口进场时扫描车牌,记录车牌(key)和入场时间(value),出口离场时,扫描车牌,查找入场时间,用当前时间-入场时间计算出停车时长,计算出停车费用,缴费后抬杆,车辆离场。
场景3:统计一篇文章中单词(key)出现的次数(value),读取一个单词,查找单词是否存在,不存在这个说明第一次出现,(单词,1),单词存在,则++单词对应的次数。
void TestBSTree(){ // 四个单词的简单词典BSTree<string, string> dict;dict.Insert("insert", "插入");dict.Insert("erase", "删除");dict.Insert("left", "左边");dict.Insert("string", "字符串");string str;while (cin >> str){auto ret = dict.Find(str);if (ret){cout << str << ":" << ret->_value << endl;}else{cout << "单词拼写错误" << endl;}} // 统计水果出现次数string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };// 统计水果出现的次BSTree<string, int> countTree;for (auto str : strs){auto ret = countTree.Find(str);if (ret == nullptr){countTree.Insert(str, 1);}else{ret->_value++;}}countTree.InOrder();}
4.3 key/value版本二叉搜索树
template<class K, class V>struct BSTreeNode{K _key;V _value;BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;BSTreeNode(const K& key, const V& value):_key(key),_value(value),_left(nullptr),_right(nullptr){}};template<class K, class V>class BSTree{typedef BSTreeNode<K, V> Node;public:BSTree() = default;BSTree(const BSTree& tree){_root = Construct(tree._root);}~BSTree(){Destroy(_root);_root = nullptr;}BSTree& operator=(BSTree tree){swap(_root, tree._root);return *this;}bool Insert(const K& key, const V& value){if (_root == nullptr){_root = new Node(key, value);return true;}Node* cur = _root, *parent = nullptr;while (cur){parent = cur;if (key < cur->_key)cur = cur->_left;else if (key > cur->_key)cur = cur->_right;elsereturn false;}cur = new Node(key, value);if (key < parent->_key)parent->_left = cur;elseparent->_right = cur;return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (key == cur->_key)return cur;else if (key < cur->_key)cur = cur->_left;elsecur = cur->_right;}return nullptr;}bool Erase(const K& key){Node* del = _root, *parent = nullptr;while (del && del->_key != key){parent = del;if (key < del->_key)del = del->_left;elsedel = del->_right;}if (del == nullptr)return false;if (del->_left == nullptr){if (parent == nullptr){_root = del->_right;}else if (del->_key < parent->_key)parent->_left = del->_right;elseparent->_right = del->_right;delete del;}else if (del->_right == nullptr){if (parent == nullptr){_root = del->_left;}else if (del->_key < parent->_key)parent->_left = del->_left;elseparent->_right = del->_left;delete del;}else{Node* replace = del->_right;parent = del;while (replace->_left){parent = replace;replace = replace->_left;}del->_key = replace->_key;del->_value = replace->_value;if (parent->_right == replace)parent->_right = replace->_right;elseparent->_left = replace->_right;delete replace;}return true;}void InOrder(){_InOrder(_root);cout << endl;}private:Node* Construct(Node* root){if (root == nullptr)return nullptr;Node* copy = new Node(root->_key, root->_value);copy->_left = Construct(root->_left);copy->_right = Construct(root->_right);return copy;}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << ":" << root->_value << " ";_InOrder(root->_right);}private:Node* _root = nullptr;};