【C++杂货铺】一颗具有搜索功能的二叉树

在这里插入图片描述

文章目录

  • 一、二叉搜索树概念
  • 二、二叉搜索树的操作
    • 2.1 二叉搜索树的查找
    • 2.2 二叉搜索树的插入
    • 2.3 二叉搜索树的删除
  • 三、二叉搜索树的实现
    • 3.1 BinarySearchTreeNode（结点类）
    • 3.2 BinarySearchTree（二叉搜索树类）
      • 3.2.1 框架
      • 3.2.2 insert（插入）
      • 3.2.3 InOrder（中序遍历）
      • 3.2.4 find（查找）
      • 3.2.5 erase（删除）
      • 3.2.6 ~BinarySearchTree（析构）
      • 3.2.7 BinarySearchTree(const Self& tree)（拷贝构造）
      • 3.2.8 operator=（赋值运算符重载）
  • 四、二叉搜索树的应用
    • 4.1 K模型
    • 4.2 KV模型
      • 4.2.1 KV 模型手撕
  • 五、二叉搜索树的性能分析
  • 六、结语

一、二叉搜索树概念

二叉搜索树又称二插排序树，它要么是一个空树，要么就是具有以下性质的二叉树：

  • 若它的左子树不为空，则左子树上所有节点的值都小于（大于）根节点的值。

  • 若它的右子树不为空，则右子树上所有节点的值都大于（小于）根节点的值。

  • 它的左右子树也分别为二叉搜索树。

在这里插入图片描述

二、二叉搜索树的操作

2.1 二叉搜索树的查找

  • 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

  • 最多查找高度次，走到空还没找到，说明这个值不存在。

小Tips：这里最多查找高度次的时间复杂度并不是 O ( l o g N ) O(logN) O(logN)，这是建立在比较理想的情况下，即这颗二叉树是一颗满二叉树或者完全二叉树。在极端情况下，这棵二叉树只有一条路径，此时最多查找高度次的时间复杂度就是 O ( N ) O(N) O(N)。

2.2 二叉搜索树的插入

插入的具体过程如下：

  • 树为空：则直接新增节点，赋值给 root 指针。

  • 树不为空：先按二叉搜索树的性质寻找插入位置，插入新节点。

在这里插入图片描述

2.3 二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回，否则要删除的结点可能分下面四种情况:

  1. 要删除的结点没有孩子结点。

  2. 要删除的结点只有左孩子结点。

  3. 要删除的结点只有右孩子结点。

  4. 要删除的结点有左、右孩子节点。

虽然看起来删除一个结点有 4 中情况，但实际上情况1可以和情况2或者情况3合并起来，因此真正的删除过程如下：

  • 情况一（要删除的结点只有左孩子）：删除该节点且使被删除节点的双亲结点指向被删除结点的左孩子结点----直接删除。

  • 情况二（要删除的结点只有右孩子）：删除该结点且使被删除结点的双亲结点指向被删除结点的右孩子结点-----直接删除。

  • 情况三（要删除的结点有左、右孩子）：在它的左子树中寻找出关键码最大的结点，用它的值填补到被删除结点中，再来处理该结点的删除问题----替换法删除。

在这里插入图片描述

三、二叉搜索树的实现

二插搜索树只是一种结构，它本质上是由一个个结点链接而成，因此我们首先需要定义一个结点类，这个结点用来存储数据。有了结点类之后就需要定义一个二叉搜索树的类，这个类主要是用来维护结构的，实现增删查改等功能，因为它是维护结构的，因此这个类里面的成员变量只需要一个根节点即可，有了这个根节点就能对整个数的结构进行维护管理。

3.1 BinarySearchTreeNode（结点类）

template <class K>
struct BinarySearchTreeNode
{typedef BinarySearchTreeNode<K> TNode;BinarySearchTreeNode(const K& val = K()):_val(val),_left(nullptr),_right(nullptr){}K _val;TNode* _left;TNode* _right;
};

3.2 BinarySearchTree（二叉搜索树类）

3.2.1 框架

template <class K>
class BinarySearchTree
{typedef BinarySearchTreeNode<K> BSTNode;typedef BinarySearchTree<K> Self;
public:BinarySearckTree():_root(nullptr){}
private:BSTNode* _root;
};

3.2.2 insert（插入）

非递归版：

bool insert(const K& val)
{if (_root == nullptr){_root = new BSTNode(val);return true;}BSTNode* newnode = new BSTNode(val);BSTNode* cur = _root;BSTNode* parent = nullptr;while (cur){if (val < cur->_val){parent = cur;cur = cur->_left;}else if (val > cur->_val){parent = cur;cur = cur->_right;}else{return false;//相等就说明树中已经有了，就应该插入失败}}//if (parent->_left == cur)//左右都是空，每次就走上面这个了if(val < parent->_val){parent->_left = newnode;}else{parent->_right = newnode;}return true;
}

小Tips：需要单独考虑根节点为空的情况。用 cur 找到该结点应该要插入的位置，用 parent 指向该位置的双亲结点，以实现链接关系。最后还需要判断插入到双亲结点的左侧还是右侧。我们实现的这个二叉搜索树要求存储相同值的结点在一个二叉搜索树中只能出现一次，因此当插入一个值 val 的时候，如果检测到树中已经有一个结点存的是 val，那么就应该返回 false，表明插入失败。

递归版：

//插入(递归---版本一)
private:bool _InsertR(BSTNode*& root, BSTNode* parent, const K& key){if (root == nullptr)//为空说明就是在该位置插入{BSTNode* newnode = new BSTNode(key);if (parent != nullptr){if (key < parent->_val){parent->_left = newnode;}else{parent->_right = newnode;}}else{root = newnode;}return true;}//root不为空说明还没有找到待插入的位置，还得继续找if (key < root->_val){return _InsertR(root->_left, root, key);}else if (key > root->_val){return _InsertR(root->_right, root, key);}else{return false;}}
public://插入(递归)bool InsertR(const K& key){return _InsertR(_root, _root, key);}

//插入(递归---版本二)
private:bool _InsertR(BSTNode*& root, const K& key){if (root == nullptr)//为空说明就是在该位置插入{root = new BSTNode(key);return true;}//root不为空说明还没有找到待插入的位置，还得继续找if (key < root->_val){return _InsertR(root->_left, key);}else if (key > root->_val){return _InsertR(root->_right, key);}else{return false;}}
public://插入(递归)bool InsertR(const K& key){return _InsertR(_root, key);}

小Tips：在空树的时候执行插入，是需要改变根节点 _root 的，即需要对指针进行修改，因此这里需要使用引用或者二级指针。

3.2.3 InOrder（中序遍历）

private:void _InOrder(BSTNode* root) const{if (root == nullptr){return;}_InOrder(root->_left);cout << root->_val << " ";_InOrder(root->_right);}
public:void InOrder(){_InOrder(_root);cout << endl;}

小Tips：这里的中序遍历用的是递归的方式来实现的，但是递归函数一定是需要一个参数的，要中序遍历整个二叉树，用户一定是要把根节点 _root 传给这个函数，但是根节点 _root 是私有的成员变量，用户是访问不到的，因此我们不能直接提供中序遍历函数给用户。正确的做法是，虽然用户访问不到根结点，但是类里面可以访问呀，所以我们可以在类里面实现一个中序遍历的子函数 _InOrder，在这个子函数中实现中序遍历的逻辑，然后我们再去给用户提供一个中序遍历的函数接口 InOrder，由它去调用 _InOrder。这样以来用户就可以正常去使用中序遍历啦。

3.2.4 find（查找）

非递归版：

bool find(const K& key)
{BSTNode* cur = _root;while (cur){if (key < cur->_val){cur = cur->_left;}else if (key > cur->_val){cur = cur->_right;}else{return true;}}return false;
}

递归版：

private:bool _FindR(BSTNode* root, const K& key){if (root == nullptr){return false;}if (key < root->_val){return _FindR(root->_left, key);}else if (key > root->_val){return _FindR(root->_right, key);}else{return true;}}
public:bool FindR(const K& key){return _FindR(_root, key);}

3.2.5 erase（删除）

非递归版：

bool erase(const K& key)
{BSTNode* cur = _root;BSTNode* parent = nullptr;//先找需要删除的结点while (cur){if (key < cur->_val){parent = cur;cur = cur->_left;}else if (key > cur->_val){parent = cur;cur = cur->_right;}else{//到这里说明cur就是待删除的节点if (cur->_left == nullptr)//如果cur只有一个孩子(只有右孩子)，直接托孤{if (parent == nullptr)//说明删除的是根结点{_root = _root->_right;}else if (cur == parent->_left)//判断cur是左孩子还是右孩子{parent->_left = cur->_right;}else if(cur == parent->_right){parent->_right = cur->_right;}}else if(cur->_right == nullptr)//如果cur只有一个孩子(只有左孩子){if (parent == nullptr)//说明删除的是根结点{_root = _root->_left;}else if (cur == parent->_left)//判断cur是左孩子还是右孩子{parent->_left = cur->_left;}else if (cur == parent->_right){parent->_right = cur->_left;}}else//到这里说明cur有两个孩子{BSTNode* parent = cur;BSTNode* leftmax = cur->_left;//找到左孩子中最大的那个while (leftmax->_right){parent = leftmax;leftmax = leftmax->_right;}swap(cur->_val, leftmax->_val);cur = leftmax;//有一种极端情况就是左边只有一条路径if (leftmax == parent->_left){parent->_left = leftmax->_left;}else{parent->_right = leftmax->_left;}}delete cur;return true;}}return false;
}

小Tips：在上面的代码中我们始终让 cur 指向待删除节点，parent 指向待删除结点的双亲，也就是 cur 的双亲。删除大体上就分为2. 3小节中提到的三种情况。但是里面任然有一些细节需要我们注意，比如删除根结点的情况，即 parent == nullptr 的时候。在情况一和情况二中，我们还需要判断待删除结点 cur 是其双亲结点 parent 的左孩子还是右孩子，以保证让 cur 的孩子和 parent 建立正确的链接关系。情况三，待删除的结点有两个孩子，我们这里的做法是，找出 cur 左子树中最大的那个节点 leftmax，让它来替换 cur，帮助 cur 带“孩子”。找到左子树中值最大的结点很容易，从 cur 的左孩子开始，一路往右即可。找到后交换 cur 和 leftmax 中存储的值。交换后 leftmax 就变成了要删除的结点，所以所以此时需要让 cur 重新指向 leftmax 这个结点。由于要删除 leftmax 结点，为了方便后面修改链接关系，这里我们还需要找到 leftmax 的双亲结点，因此在这个局部域中我们重新定义了一个 parent，它和外面那个 parent 并不冲突，优先使用局部的，但是注意里面这个 parent 表示的意义和外面 parent 的意义是有所不同的，前者表示 cur 左树中最大节点的双亲结点，后者表示 cur 的双亲结点。最后我们需要通过修改链接关系来实现 cur 结点的删除，这里的链接关系有以下两种情形：

情形一：
在这里插入图片描述
小Tips：Step2 中的交换是交换节点中的值，并不是交换两个结点。最终 leftmax 和 cur 指向同一个结点。

情形二：
在这里插入图片描述
小Tips：情形二与情形一最大的不同点体现在两个地方，第一情形二中的 parent 就是 cur，只说明我们在定义 parent 赋初值的时候不能让 parent = nullptr，应该让 parent = cur，否则后面修改链接关系会出现访问空指针的问题。第二点不同在于修改链接关系，情形二是让 parent 的左孩子指向 leftmax 的左孩子；情形一是让 parent 的右孩子指向 leftmax 的左孩子。因此在修改链接关系的时候要进行判断，看是哪种情形。在第二点不同里面又有一个相同点，即无论是 parent 的左孩子，还是 parent 的右孩子，最终都指向了 leftmax 的左孩子，这是为什么呢？原因其实很简单，leftmax 的右孩子一定为空，而左孩子则不一定为空。为什么可以肯定右孩子一等为空，因为 leftmax 是左子树中最大的那个结点，如果它的右孩子不为空，说明当前这个 leftmax 一定不是最大的那个结点。因此在修改链接关系的时候，要让 parent 与 leftmax 的左孩子建立连接。最后需要注意，交换完之后，只能通过修改链接关系去删除 cur 结点，不能通过递归调用去删除，因为这个函数每次都是从根节点开始查找的，交换后这棵树暂时不满足二叉搜索树的结构，以情形一为例，它就找不到存储8的结点。

递归版：

private:
//删除递归版bool _eraseR(BSTNode*& root, const K& key){if (root == nullptr){return false;}if (key < root->_val){return _eraseR(root->_left, key);}else if (key > root->_val){return _eraseR(root->_right, key);}else{//相等了，需要进行删除了BSTNode* del = root;if (root->_left == nullptr)//左为空{root = root->_right;}else if (root->_right == nullptr)//右为空{root = root->_left;}else//左右都不为空{BSTNode* parent = root;BSTNode* leftmax = root->_left;//找到左孩子中最大的那个while (leftmax->_right){parent = leftmax;leftmax = leftmax->_right;}swap(root->_val, leftmax->_val);return _eraseR(root->_left, key);}delete del;del = nullptr;return true;}}
public://删除递归版bool eraseR(const K& key){return _eraseR(_root, key);}

小Tips：在交换后，虽然整棵树可能不满足二叉搜索树的结构，但是 root 结点的左子树一定是满足二叉搜索树的，因为我们交换的是 root 结点的 _val 和左子树中最大的那个 _val，而 root 结点的 _val 一定是比左子树中最大的那个 _val 还要大的，所以交换完之后 root 的左子树任然满足二叉搜索树的结构，此时我们就可以通过递归调用去 root 的左子树中找要删除的结点，并且交换后待删除的结点一定变成了情况一或者情况二中的一种。递归版中对情况一和情况二的处理变简单了许多，因为 root 是一个引用，如果发现 root 的一个孩子为空，直接把 root 的另一个孩子赋值给它即可，在赋值之前记得保存一下 root 的值，这个值指向的结点就是要删除的结点，把这个值保存下来后面才能去 delete，否则赋值后就没有指针指向该结点，那就没办法释放这个结点的空间资源，就会造成内存泄漏。非递归中即使用了引用也不能这样搞，因为非递归中，一个引用始终是在一个函数栈帧里面，而引用是不能改变指向的。但是递归就不一样了，每一次递归调用都会开辟新的函数栈帧，每一个函数栈帧中 root 都是不同结点的别名。

3.2.6 ~BinarySearchTree（析构）

private://析构子函数void Destruction(BSTNode*& root){if (root == nullptr){return;}//先去释放左孩子和右孩子的空间资源Destruction(root->_left);Destruction(root->_right);//再去释放root自己的空间资源delete root;root = nullptr;//形参root如果不加引用，这里置空是没有任何意义的，因为不加引用这里仅仅是一份拷贝return;}
public://析构函数~BinarySearckTree(){Destruction(_root);}

3.2.7 BinarySearchTree(const Self& tree)（拷贝构造）

注意拷贝构造不能直接去调用 insert，因为数据插入的顺序不同，这棵树最终的结构也是不同的，虽然最终也符合二叉树的结构，但是还是和被拷贝的树有所不同。正确做法是，走一个前序遍历，遍历到 tree 的一个结点时，去 new 一个结点，存储同样的值。

写法一：

//拷贝构造函数的子函数
private:void Construct(BSTNode*& root, BSTNode* copy){if (copy == nullptr){root = nullptr;return;}root = new BSTNode(copy->_val);//通过引用直接来实现链接关系Construct(root->_left, copy->_left);Construct(root->_right, copy->_right);}
public://拷贝构造BinarySearchTree(const Self& tree):_root(nullptr){Construct(_root, tree._root);}

写法二：

private:
//拷贝构造子函数(写法二)BSTNode* Construct(BSTNode* root){if (root == nullptr){return nullptr;}BSTNode* newnode = new BSTNode(root->_val);newnode->_left = Construct(root->_left);//通过返回值来实现链接关系newnode->_right = Construct(root->_right);return newnode;}
public://拷贝构造(写法二)BinarySearchTree(const Self& tree){_root = Construct(tree._root);}

小Tips：上面两种写法的不同点在于，方法一是通过引用去实现链接关系，方法二则是通过返回值的方式来实现链接关系。

3.2.8 operator=（赋值运算符重载）

public:
//赋值运算符重载(现代写法)Self& operator=(Self tree){swap(_root, tree._root);//交换两颗搜索二叉树就是交换它们里面维护的根节点return *this;}

四、二叉搜索树的应用

4.1 K模型

K模型即只有一个 Key 作为关键码，结构中只需要存储 Key 即可，关键码即为需要搜索到的值。比如：给一个单词 word，判断该单词是否拼写正确，具体方式如下：

  • 以词库中所有单词集合中的每个单词作为 Key，构建一颗二叉搜索树。

  • 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

我们上面手搓的这可二叉搜索树就是 Key 模型，因为这颗树的结点里面只能存储一个值，这个值就是 Key。

4.2 KV模型

KV 模型即每一个关键码 Key，都有与之对应的的值 Value，即 <Key，Value> 的键值对。这种方式在现实生活中十分常见：

  • 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文 <word，Chinese> 就构成一种键值对。

  • 再比如统计单词次数，统计成功后，给定单词就可以快速找到其出现的次数，单词与其出现次数就是 <word，count> 就构成一种键值对。

4.2.1 KV 模型手撕

#pragma oncenamespace K_V
{template <class K, class V>struct BinarySearchTreeNode{typedef BinarySearchTreeNode<K, V> TNode;BinarySearchTreeNode(const K& key = K(), const V& val = V()):_key(key), _val(val), _left(nullptr), _right(nullptr){}K _key;V _val;TNode* _left;TNode* _right;};template <class K, class V>class BinarySearchTree{typedef BinarySearchTreeNode<K, V> BSTNode;typedef BinarySearchTree<K, V> Self;private:void _InOrder(BSTNode* root) const{if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << "--" << root->_val << endl;_InOrder(root->_right);}BSTNode* _FindR(BSTNode* root, const K& key)//KV模型中的Key不能被修改，但是Val可以被修改{if (root == nullptr){return nullptr;}if (key < root->_key){return _FindR(root->_left, key);}else if (key > root->_key){return _FindR(root->_right, key);}else{return root;}}//插入(递归---版本一)//bool _InsertR(BSTNode*& root, BSTNode* parent, const K& key)//{//	if (root == nullptr)//为空说明就是在该位置插入//	{//		BSTNode* newnode = new BSTNode(key);//		if (parent != nullptr)//		{//			if (key < parent->_key)//			{//				parent->_left = newnode;//			}//			else//			{//				parent->_right = newnode;//			}//		}//		else//		{//			root = newnode;//		}//		return true;//	}//	//root不为空说明还没有找到待插入的位置，还得继续找//	if (key < root->_key)//	{//		return _InsertR(root->_left, root, key);//	}//	else if (key > root->_key)//	{//		return _InsertR(root->_right, root, key);//	}//	else//	{//		return false;//	}//}//插入(递归---版本二)bool _InsertR(BSTNode*& root, const K& key, const V& val){if (root == nullptr)//为空说明就是在该位置插入{root = new BSTNode(key, val);return true;}//root不为空说明还没有找到待插入的位置，还得继续找if (key < root->_key){return _InsertR(root->_left, key, val);}else if (key > root->_key){return _InsertR(root->_right, key, val);}else{return false;}}//删除递归版bool _eraseR(BSTNode*& root, const K& key){if (root == nullptr){return false;}if (key < root->_key){return _eraseR(root->_left, key);}else if (key > root->_key){return _eraseR(root->_right, key);}else{//相等了，需要进行删除了BSTNode* del = root;if (root->_left == nullptr)//左为空{root = root->_right;}else if (root->_right == nullptr)//右为空{root = root->_left;}else//左右都不为空{BSTNode* parent = root;BSTNode* leftmax = root->_left;//找到左孩子中最大的那个while (leftmax->_right){parent = leftmax;leftmax = leftmax->_right;}std::swap(root->_key, leftmax->_key);return _eraseR(root->_left, key);}delete del;del = nullptr;return true;}}//析构子函数void Destruction(BSTNode*& root){if (root == nullptr){return;}//先去释放左孩子和右孩子的空间资源Destruction(root->_left);Destruction(root->_right);//再去释放root自己的空间资源delete root;root = nullptr;//形参root如果不加引用，这里置空是没有任何意义的，因为不加引用这里仅仅是一份拷贝return;}//拷贝构造函数的子函数(写法一)void Construct(BSTNode*& root, BSTNode* copy){if (copy == nullptr){root = nullptr;return;}root = new BSTNode(copy->_key);Construct(root->_left, copy->_left);Construct(root->_right, copy->_right);}//拷贝构造子函数(写法二)BSTNode* Construct(BSTNode* root){if (root == nullptr){return nullptr;}BSTNode* newnode = new BSTNode(root->_key);newnode->_left = Construct(root->_left);newnode->_right = Construct(root->_right);return newnode;}public:BinarySearchTree():_root(nullptr){}//拷贝构造(写法一)/*BinarySearchTree(const Self& tree):_root(nullptr){Construct(_root, tree._root);}*///拷贝构造(写法二)BinarySearchTree(const Self& tree){_root = Construct(tree._root);}//赋值运算符重载(现代写法)Self& operator=(Self tree){swap(_root, tree._root);//交换两颗搜索二叉树就是交换它们里面维护的根节点return *this;}//插入(非递归)bool insert(const K& key, const V& val){if (_root == nullptr){_root = new BSTNode(key, val);return true;}BSTNode* newnode = new BSTNode(key, val);BSTNode* cur = _root;BSTNode* parent = nullptr;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{return false;//相等就说明树中已经有了，就应该插入失败}}//if (parent->_left == cur)//左右都是空，每次就走上面这个了if (key < parent->_key){parent->_left = newnode;}else{parent->_right = newnode;}return true;}//插入(递归)bool InsertR(const K& key, const V& val){return _InsertR(_root, key, val);}//中序遍历void InOrder(){_InOrder(_root);cout << endl;}//查找(非递归)BSTNode* find(const K& key){BSTNode* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}else{return cur;}}return nullptr;}//查找(递归)BSTNode* FindR(const K& key){return _FindR(_root, key);}//删除(非递归)bool erase(const K& key){BSTNode* cur = _root;BSTNode* parent = nullptr;//先找需要删除的结点while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{//到这里说明cur就是待删除的节点if (cur->_left == nullptr)//如果cur只有一个孩子(只有右孩子)，直接托孤{if (parent == nullptr){_root = _root->_right;}else if (cur == parent->_left)//判断cur是左孩子还是右孩子{parent->_left = cur->_right;}else if (cur == parent->_right){parent->_right = cur->_right;}}else if (cur->_right == nullptr)//如果cur只有一个孩子(只有左孩子){if (parent == nullptr){_root = _root->_left;}else if (cur == parent->_left)//判断cur是左孩子还是右孩子{parent->_left = cur->_left;}else if (cur == parent->_right){parent->_right = cur->_left;}}else//到这里说明cur有两个孩子{BSTNode* parent = cur;BSTNode* leftmax = cur->_left;//找到左孩子中最大的那个while (leftmax->_right){parent = leftmax;leftmax = leftmax->_right;}std::swap(cur->_key, leftmax->_key);cur = leftmax;//有一种极端情况就是左边只有一条路径if (leftmax == parent->_left){parent->_left = leftmax->_left;}else{parent->_right = leftmax->_left;}}delete cur;return true;}}return false;}//删除递归版bool eraseR(const K& key){return _eraseR(_root, key);}//析构函数~BinarySearchTree(){Destruction(_root);}private:BSTNode* _root = nullptr;};
}void TestBSTree4()
{// 统计水果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };K_V::BinarySearchTree<string, int> countTree;for (const auto& str : arr){// 先查找水果在不在搜索树中// 1、不在，说明水果第一次出现，则插入<水果, 1>// 2、在，则查找到的节点中水果对应的次数++//BSTreeNode<string, int>* ret = countTree.Find(str);auto ret = countTree.FindR(str);if (ret == NULL){countTree.insert(str, 1);}else{ret->_val++;}}countTree.InOrder();
}

在这里插入图片描述
小Tips：虽然变成了 KV 模型，但它仍然是一颗二叉搜索树，因此整棵树的结构没有发生任何变化。唯一的变化在于树的结点，对与 KV 模型来说，树中的结点不仅要存 Key，还要存 Value，这就进一步导致在插入时不仅要插入 Key，还要插入一个与该 Key 对应的 Value。其次对 KV 模型来说，Key 不允许被修改，Value 可以被修改，因此对 KV 模型来说，在 Find 的时候应该返回结点的指针，这样方便后续进行一些操作。

五、二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。对有 n 个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二插搜索树的深度的函数，即结点越深，则比较次数越多。但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树。

在这里插入图片描述

  • 最优情况下：二叉搜索树为完全二叉树（或者接近完全二叉树），其平均比较次数为： l o g 2 n log2^n log2n。

  • 最差情况下：二叉搜索树退化为单支树（或者类似单支），其平均比较次数为： N 2 \frac{N}{2} 2N​。如果退化成了单支树，那么二叉搜索树的性能就失去了。此时就需要用到即将登场的 AVL 树和红黑树了。

六、结语

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，春人的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是春人前进的动力！

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/142843.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Linux系统100条命令：关于Ubuntu和 CentOS 7 相同功能的不同的终端操作命令

Linux系统100条命令：关于Ubuntu和 CentOS 7 相同功能的不同的终端操作命令

安装软件包&#xff1a; Ubuntu&#xff1a;apt-get install package_name CentOS 7&#xff1a;yum install package_name 更新软件包列表&#xff1a; Ubuntu&#xff1a;apt-get update CentOS 7&#xff1a;yum update 卸载软件包&#xff1a; Ubuntu&#xff1a;apt-…
阅读更多...
Diffusion Autoencoders: Toward a Meaningful and Decodable Representation

Diffusion Autoencoders: Toward a Meaningful and Decodable Representation

Diffusion Autoencoders: Toward a Meaningful and Decodable Representation (Paper reading) Konpat Preechakul, VISTEC, Thailand, CVPR22 Oral, Cited:117, Code, Paper 1. 前言 扩散概率模型 (DPM) 在图像生成方面取得了显着的质量&#xff0c;可与 GAN 相媲美。但是与…
阅读更多...
C++ - 红黑树 介绍 和 实现

C++ - 红黑树 介绍 和 实现

前言 前面 学习了 AVL树&#xff0c;AVL树虽然在 查找方面始终拥有 O(log N &#xff09;的极高效率&#xff0c;但是&#xff0c;AVL 树在插入 ,删除等等 修改的操作当中非常的麻烦&#xff0c;尤其是 删除操作&#xff0c;在实现当中细节非常多&#xff0c;在实现上非常难掌控…
阅读更多...
如何套用模板制作大屏？

如何套用模板制作大屏？

在山海鲸可视化的资源中心里内置了大量的二维、三维大屏模板&#xff0c;大家可以根据需要找到自己想要的模板&#xff0c;然后点击下载直接进行使用。 有需要可自行前往哔哩哔哩账号中观看相关内容的视频教程↓↓↓ 山海鲸可视化的个人空间-山海鲸可视化个人主页-哔哩哔哩视频…
阅读更多...
cocos2dx查看版本号的方法

cocos2dx查看版本号的方法

打开文件&#xff1a;项目根目录\frameworks\cocos2d-x\docs\RELEASE_NOTES.md 知道引擎版本号的意义&#xff1a; 1.面试中经常被问到(面试官想知道你会不会查版本号&#xff0c;你会查也不一定会去看&#xff0c;如果你去看了说明你是一个有心人&#xff0c;或者想深入研究下…
阅读更多...
Java内存泄漏知识（软引用、弱引用等）

Java内存泄漏知识（软引用、弱引用等）

关于作者&#xff1a;CSDN内容合伙人、技术专家&#xff0c; 从零开始做日活千万级APP。 专注于分享各领域原创系列文章 &#xff0c;擅长java后端、移动开发、商业变现、人工智能等&#xff0c;希望大家多多支持。 未经允许不得转载 目录 一、导读二、概览三、相关知识3.1 内存…
阅读更多...
工作中Git管理项目和常见问题处理

工作中Git管理项目和常见问题处理

工作中Git管理项目和常见问题处理 Git仓库的管理方式为什么会出现无法push到线上处理方法 Git仓库的管理方式 共用统一仓库,不同开发人员使用不同分支 步骤 下载代码 git clone <url>查看分支 git branch创建并切换分支 git checkout -b dev分支名称保持和远程分支一…
阅读更多...
计算机视觉与深度学习-图像分割-视觉识别任务03-实例分割-【北邮鲁鹏】

计算机视觉与深度学习-图像分割-视觉识别任务03-实例分割-【北邮鲁鹏】

目录 参考定义Mark R-CNN结构思路Mask R-CNN训练阶段使用的Mask样例Mask R-CNN实例分割结果Mask R-CNN检测姿态 参考 论文题目&#xff1a;Mask R-CNN 论文链接&#xff1a;论文下载 论文代码&#xff1a;Facebook代码链接&#xff1b;Tensorflow版本代码链接&#xff1b; K…
阅读更多...
微信里怎么添加阅读付费链接

微信里怎么添加阅读付费链接

在微信中添加阅读付费链接为主题&#xff0c;首先需要开通微信支付商户号&#xff0c;然后创建自定义菜单&#xff0c;并设置跳转到付费链接的逻辑。以下是详细步骤&#xff1a; 注册并开通微信支付商户号 在微信开放平台上注册并开通微信支付商户号。这一步需要营业执照、法…
阅读更多...
出现 conda虚拟环境默认放在C盘 解决方法

出现 conda虚拟环境默认放在C盘 解决方法

目录 1. 问题所示2. 原理分析3. 解决方法3.1 方法一3.2 方法二1. 问题所示 通过conda配置虚拟环境的时候，由于安装在D盘下，但是配置的环境默认都给我放C盘 通过如下命令：conda env list，最后查看该环境的确在C盘下 2. 原理分析 究其根本原因，这是因为默认路径没有足够的…
阅读更多...
go sync.Map包装过的对象nil值的判断

go sync.Map包装过的对象nil值的判断

被sync.Map包装过的nil 对象&#xff0c;是不能直接用if xxx nil的方式来判断的 func testnil() *interface{} {return nil }func main() {var ptr *interface{}test : testnil()//p &Person{}fmt.Printf("ptr 的值为 : %v\n", ptr)fmt.Printf("ptr 的值…
阅读更多...
uni-app：实现元素在屏幕中的居中（绝对定位absolute）

uni-app：实现元素在屏幕中的居中（绝对定位absolute）

一、实现水平居中 效果 代码 <template><view><view class"center">我需要居中</view></view> </template><style>.center {position: absolute;left:50%;transform: translateX(-50%);border:1px solid black;} </s…
阅读更多...
20个提升效率的JS简写技巧，告别屎山！

20个提升效率的JS简写技巧，告别屎山！

JavaScript 中有很多简写技巧&#xff0c;可以缩短代码长度、减少冗余&#xff0c;并且提高代码的可读性和可维护性。本文将介绍 20 个提升效率的 JS 简写技巧&#xff0c;助你告别屎山&#xff0c;轻松编写优雅的代码&#xff01; 移除数组假值 可以使用 filter() 结合 Bool…
阅读更多...
智能机器学习：人工智能的下一个巨大飞跃

智能机器学习：人工智能的下一个巨大飞跃

文章目录 第1节&#xff1a;智能机器学习的背景1.1 传统机器学习1.2 人工智能 第2节&#xff1a;智能机器学习的定义2.1 智能机器学习的原理2.1.1 自主学习2.1.2 强化学习2.1.3 自适应性 2.2 智能机器学习的关键技术2.2.1 深度学习2.2.2 强化学习算法2.2.3 自然语言处理&#x…
阅读更多...
Stable Diffusion 参数介绍及用法

Stable Diffusion 参数介绍及用法

大模型 CheckPoint 介绍 作用&#xff1a;定调了作图风格&#xff0c;可以理解为指挥者 安装路径&#xff1a;models/Stable-diffusion 推荐&#xff1a; AnythingV5Ink_v32Ink.safetensors cuteyukimixAdorable_midchapter2.safetensors manmaruMix_v10.safetensors counterf…
阅读更多...
线性约束最小方差准则(LCMV)波束形成算法仿真

线性约束最小方差准则(LCMV)波束形成算法仿真

常规波束形成仅能使得主波束对准目标方向&#xff0c;从而在噪声环境下检测到目标&#xff0c;但无法对复杂多变的干扰做出响应&#xff0c;所以不能称之为真正意义上的自适应滤波。自适应阵列处理指的是采用自适应算法对空间阵列接收的混合信号进行处理&#xff0c;又可称为自…
阅读更多...
晨控CK-FR08系列读写器与LS可编程逻辑控制器MODBUSRTU连接手册

晨控CK-FR08系列读写器与LS可编程逻辑控制器MODBUSRTU连接手册

晨控CK-FR08系列读写器与LS可编程逻辑控制器MODBUSRTU连接手册 晨控CK-FR08是一款基于射频识别技术的高频RFID标签读卡器&#xff0c;读卡器工作频率为13.56MHZ&#xff0c;支持对I-CODE 2、I-CODE SLI等符合ISO15693国际标准协议格式标签的读取。读卡器内部集成了射频部分通信…
阅读更多...
【Linux】生产者和消费者模型

【Linux】生产者和消费者模型

生产者和消费者概念基于BlockingQueue的生产者消费者模型全部代码 生产者和消费者概念 生产者消费者模式就是通过一个容器来解决生产者和消费者的强耦合问题。 生产者和消费者彼此之间不直接通讯&#xff0c;而通过这个容器来通讯&#xff0c;所以生产者生产完数据之后不用等待…
阅读更多...
微信小程序 工具使用(HBuilderX)

微信小程序 工具使用(HBuilderX)

微信小程序 工具使用:HBuilderX 一 HBuilderX 的下载二 工具的配置2.1 工具 --> 设置 --> 运行配置2.1.1 微信开发者工具路径2.1.2 node 运行配置 2.2 插件 工具 --> 插件安装2.2.1 下载插件 三 微信小程序端四 同步运行五 BUG5.1 nodemon在终端无法识别 一 HBuilderX…
阅读更多...
AnV-X6使用及总结

AnV-X6使用及总结

目录 1 简介2 安装3 基础概念3.1 画布Graph3.2 基类Cell3.3 节点Node3.4 边Edge 4 使用4.1 创建节点4.2 节点连线4.3 事件系统 5 总结 1 简介 AntV是一个数据可视化&#xff08;https://x6.antv.antgroup.com/&#xff09;的工具&#xff08;https://antv.vision/zh/ &#xf…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023