二叉搜索树 妖狐艹你老母 2021-11-22 07:30 303阅读 0赞 ## 二叉搜索树 ## **基本概念** 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 1. 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 2. 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值; 3. 它的左右子树也分别为二叉排序树。 如下图所示 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70] **二叉搜索树的查找** 1. 若根节点 = 要查找的节点 返回true 2. 若根节点 < 要查找的节点 ,在右子树种查找 3. 若根节点 > 要查找的节点 ,在左子树中查找 重复上述过程,直至查找成功返回找到的结点,否则返回false。 **二叉搜索树的插入** 1. 若二叉搜索树为空,直接插入 2. 若二叉搜索树不为空,按二叉搜索树性质查找插入位置,插入新节点 **二叉搜索树的删除** 首先查找元素是否在二叉搜索树中,如果不存在,则返回, 否则要删除的结点可能分下面四种情况: a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 看起来有待删除节点有4中情况,实际情况a可以与情况b或者c合并起来,因此真正的删除过程如下: 情况b:删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点 情况c:删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点 情况d:在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点中,再来处理该结点的删除问题 **二叉搜索树的实现** //实现简易版的二叉搜索树 // 插入 查找 删除 #include <iostream> using namespace std; template <class k,class v> class BSTreeNode { public: BSTreeNode(const pair<k, v> kv) :_kv(kv) , left(nullptr) , right(nullptr) { } public: pair<k, v> _kv; BSTreeNode<k, v>* left; BSTreeNode<k, v>* right; }; template<class k,class v> class BSTree { public: typedef BSTreeNode<k,v> Node; BSTree() :_root(nullptr) { } //插入 bool Insert(const pair<k, v> kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->left; } else { return false; } } cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->right = cur; } else { parent->left = cur; } return true; } //查找 Node* Find(const k& key) { Node* cur = _root; while (cur) { if (cur->_kv.first < key) { cur = cur->left; } else if(cur->_kv.first > key){ cur = cur->right; } else{ return cur; } } return nullptr; } //删除 bool Remove(const k& key) { Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first < key) { parent = cur; cur = cur->right; } else if(cur->_kv.first > key){ parent = cur; cur = cur->left; } else { //找到 //没有孩子,只有一个孩子,两个孩子都有 Node* del = cur; //只有右孩子 if (cur->left == nullptr) { if (parent == nullptr) { _root = cur->right; } else{ if (parent->left == cur) { parent->left = cur->right; } else { parent->right = cur->right; } } } //只有左孩子 else if (cur->right == nullptr) { if (parent->left == cur) { parent->left = cur->left; } else { parent->right = cur->left; } } //左右孩子都有 else { Node* reparent = cur; Node* replace = cur->right; while (replace->left) { //在右子树中找最左节点 reparent = replace; replace = replace->left; } cur->_kv = replace->_kv; //替换节点值 del = replace; if (reparent->left == replace) { reparent->left = replace->right; } else { reparent->right = replace->right; } } delete del; return true; } } return false; } //中序遍历 void InOrder() { _InOrder(_root); cout << endl; } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->left); cout << root->_kv.first << " "; _InOrder(root->right); } private: Node* _root; }; void TestBSTree1() { BSTree<int, int> tree; tree.Insert(make_pair(1, 1)); tree.Insert(make_pair(3, 1)); tree.Insert(make_pair(4, 1)); tree.Insert(make_pair(6, 1)); tree.Insert(make_pair(1, 1)); tree.Insert(make_pair(2, 1)); tree.InOrder(); tree.Remove(1); tree.Remove(3); tree.Remove(2); tree.Remove(6); tree.Remove(4); tree.Remove(1); tree.Remove(10); tree.InOrder(); } int main(void) { TestBSTree1(); system("pause"); return 0; } **二叉搜索树性能分析** 我们可以看出来其实它就是一个二分查找,所以BST的查找和插入删除关键字的速度较于一般的数组链表都比较快。这就是BST产生的原因。但是,创建好BST后,插入数据的随机性,所以会出现比较极端的BST。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70 1] 最优情况下,二叉搜索树为完全二叉树,其时间复杂度为:log(n) ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70 2] 最差情况下,二叉搜索树退化为单支树,其时间复杂度为:O(n) 第一张图的就是我们理想的情况,可是却可能出现第二张图的情况,第一张图操作的时间复杂度为log(n),而第二张图则为O(n),所以这也是BST没有广泛使用的原因。 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]: /images/20211122/f77061ebc4774de9b49dfd94eec43b39.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70 1]: /images/20211122/5f0cf784c16b43a697bd66f89e9db197.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70 2]: /images/20211122/4a97294ead444253bdb11a7810351760.png
相关 二叉搜索树 1 二叉搜索树 二叉搜索树是指一棵树的左子树上所有的节点都小于它的根节点;右子树上所有的节点都大于它的根节点。且对于它的所有子树都是如此。基于这个性质,当我们对二叉搜索树 心已赠人/ 2023年09月28日 09:18/ 0 赞/ 75 阅读
相关 二叉搜索树 在计算机术语中,二叉搜索树又叫二叉查找树、二叉排序树。 二叉搜索树(Binary Search Tree)的定义: 它或者是一棵空树,或者是具有下列性质的二叉树: 若它的 Myth丶恋晨/ 2022年09月30日 06:45/ 0 赞/ 158 阅读
相关 二叉搜索树 搜索树数据结构支持许多动态集合操作,包括SEARCH、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT和DELETE等。因此,我们使用一 ╰+哭是因爲堅強的太久メ/ 2022年08月14日 01:50/ 0 赞/ 158 阅读
相关 二叉搜索树 二叉搜索树的特征定义就是:一个节点的左子节点的关键字值小于这个节点,右子节点的关键字大于或等于这个父节点 package Trees; import java.ut 客官°小女子只卖身不卖艺/ 2022年05月31日 00:50/ 0 赞/ 244 阅读
相关 二叉搜索树 二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于 ゝ一世哀愁。/ 2022年04月24日 11:20/ 0 赞/ 203 阅读
相关 二叉搜索树 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RqaDYy た 入场券/ 2022年03月17日 02:18/ 0 赞/ 241 阅读
相关 二叉搜索树 思路 二叉排序树,二叉搜索树好像都行,原理应该都懂,比较基础,但要写出来还是有相当大的难度的。 查找 查找比较简单,基本都是一个while就解决。但查前驱与后继较 短命女/ 2021年12月21日 09:15/ 0 赞/ 232 阅读
相关 二叉搜索树 二叉查找树(Binary Search Tree),或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不 小咪咪/ 2021年12月20日 02:53/ 0 赞/ 256 阅读
相关 二叉搜索树 二叉搜索树 C++实现![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9 今天药忘吃喽~/ 2021年12月14日 08:47/ 0 赞/ 235 阅读
相关 二叉搜索树 二叉搜索树 基本概念 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 1. 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 妖狐艹你老母/ 2021年11月22日 07:30/ 0 赞/ 304 阅读
还没有评论,来说两句吧...