北京网站搭建开发,乐都企业网站建设哪家快,网站怎么做高权重,wordpress 淘宝优惠券目录 #x1f347;二叉搜索树概念#x1f348;二叉搜索树查找#x1f349;二叉搜索树的插入#x1f34a;二叉搜索树的删除#x1f34d;二叉搜索树的查找、插入、删除实现#x1f34b;二叉搜索树的应用#x1f96d;二叉搜索树的性能分析#x1f353;总结 #x1f347;二… 目录 二叉搜索树概念二叉搜索树查找二叉搜索树的插入二叉搜索树的删除二叉搜索树的查找、插入、删除实现二叉搜索树的应用二叉搜索树的性能分析总结 二叉搜索树概念
二叉搜索树又称为二叉排序树是一种特殊的二叉树。它要么是一棵空树要么具有以下性质
若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树。
二叉搜索树的特点是可以快速地查找、插入和删除节点因为它的节点按照大小关系排列形成了一种有序结构。它常被用于实现关联数组、集合等数据结构也是许多其他算法的基础。 二叉搜索树查找
二叉搜索树的查找可以通过以下步骤进行 从根节点开始比较将待查找的值与根节点的值进行比较如果相等则返回该节点如果待查找的值比根节点的值大则往右子树走查找反之则往左子树走查找。 重复上述步骤直到找到待查找的值或者走到空节点仍未找到。如果走到空节点仍未找到则说明该值不存在于二叉搜索树中。
由于二叉搜索树的节点按照大小关系排列因此查找的时间复杂度为O(log n)其中n为二叉搜索树中节点的个数。 二叉搜索树的插入
二叉搜索树的插入可以通过以下步骤进行 如果二叉搜索树为空则直接将新节点作为根节点赋值给root指针。 如果二叉搜索树不为空则按照二叉搜索树的性质从根节点开始比较待插入节点的值和当前节点的值的大小关系如果待插入节点的值比当前节点的值小则往左子树走查找如果左子树为空则将待插入节点作为当前节点的左子节点 如果待插入节点的值比当前节点的值大则往右子树走查找如果右子树为空则将待插入节点作为当前节点的右子节点。 如果待插入节点的值与当前节点值相等表示已经存在这个值插入失败。 重复上述步骤直到找到合适的插入位置为止。
二叉搜索树的插入时间复杂度为O(log n)其中n为二叉搜索树中节点的个数。 二叉搜索树的删除
二叉搜索树的删除可以通过以下步骤进行
首先查找待删除的节点是否在二叉搜索树中如果不存在则直接返回否则进入下一步操作。
根据待删除节点的情况进行以下处理 如果待删除节点是叶子节点则直接删除该节点即可。 如果待删除节点只有左子树或者右子树则将待删除节点的父节点指向待删除节点的子节点然后删除待删除节点。 如果待删除节点既有左子树又有右子树则需要找到它的中序遍历下的后继节点即右子树中的最小节点将后继节点的值赋给待删除节点然后将待删除节点的右指向后继节点的右然后删除后继节点。
重复上述步骤直到完成待删除节点的删除。 需要注意的是二叉搜索树的删除操作可能会影响树的结构因此需要对树进行平衡操作以保证二叉搜索树的性质不被破坏。
二叉搜索树的删除时间复杂度为O(log n)其中n为二叉搜索树中节点的个数。 二叉搜索树的查找、插入、删除实现
二叉搜索树节点的定义
templateclass k
class BStreeNode
{
public:BStreeNode(const k key):_key(key), _left(nullptr), _right(nullptr){}k _key;BStreeNode* _left;BStreeNode* _right;
};二叉搜索树节点的定义有以下成员 key表示节点的关键码用于比较节点的大小关系通常是一个模板类型可以是整型、字符型、字符串、自定义类型等。 left表示节点的左子节点通常是一个指向BStreeNode类型的指针如果节点没有左子节点则该指针为空指针nullptr。 right表示节点的右子节点通常是一个指向BStreeNode类型的指针如果节点没有右子节点则该指针为空指针nullptr。
二叉搜索树的定义
templateclass k
class BStree
{typedef BStreeNodek Node;
public:Node* find(const k key);bool insert(const k key);bool erase(const k key); void InOrder();
private:Node* _root nullptr;void _InOrder(const Node* root);
};二叉搜索树的定义包括以下成员 Node表示二叉树的节点通常是一个模板类包括节点的关键码、左子节点、右子节点等成员。 find()用于在二叉树中查找指定关键码的节点如果找到则返回该节点的指针否则返回空指针nullptr。 insert()用于向二叉树中插入一个新节点如果插入成功则返回true否则返回false。 erase()用于从二叉树中删除指定关键码的节点如果删除成功则返回true否则返回false。 InOrder()用于对二叉树进行中序遍历按照节点的关键码从小到大输出节点的值。
二叉搜索树查找实现 Node* find(const k key){Node* cur _root;while (cur){if (cur-_key key) cur cur-_right; else if (cur-_key key)cur cur-_left;elsereturn cur;}return nullptr;}二叉搜索树的查找操作可以通过比较节点的键值来实现。从根节点开始若当前节点的键值小于要查找的键值则继续在右子树中查找若当前节点的键值大于要查找的键值则继续在左子树中查找若当前节点的键值等于要查找的键值则返回当前节点。
上述代码实现了二叉搜索树的查找操作。从根节点开始通过循环遍历整棵树比较节点的键值根据大小关系移动到左子树或右子树中直到找到要查找的节点或遍历到叶子节点为止。如果找到了要查找的节点则返回该节点指针否则返回空指针。
二叉搜索树插入实现 bool insert(const k key){//空树if (_root nullptr){Node* newnode new Node(key);_root newnode;return true;}//不为空Node* cur _root;Node* parent nullptr;while (cur){parent cur;if (cur-_key key)cur cur-_right;else if (cur-_key key)cur cur-_left;elsereturn false;}Node* newnode new Node(key);parent-_key key ? parent-_left newnode : parent-_right newnode;return true;}二叉搜索树的插入操作可以通过比较节点的键值来实现。从根节点开始若要插入的键值小于当前节点的键值则继续在左子树中插入若要插入的键值大于当前节点的键值则继续在右子树中插入若要插入的键值等于当前节点的键值则返回插入失败。
上述代码实现了二叉搜索树的插入操作。首先判断树是否为空如果为空则直接将新节点作为根节点否则从根节点开始循环遍历整棵树比较节点的键值根据大小关系移动到左子树或右子树中直到找到合适的插入位置或遍历到叶子节点为止。如果找到了合适的插入位置则创建新节点并插入到该位置否则返回插入失败。
二叉搜索树删除的实现 bool erase(const k key){//查找该节点及其父亲节点Node* cur _root;Node* parent nullptr;while (cur){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;} elsebreak;}if (cur nullptr)return false;//为叶子节点else if (cur-_left nullptr cur-_right nullptr)delete cur;//只有一个孩子else if ((cur-_left nullptr cur-_right) || (cur-_left cur-_right nullptr)){if (parent-_left cur){cur-_left nullptr ? parent-_left cur-_right : parent-_left cur-_left;}else{cur-_left nullptr ? parent-_right cur-_right : parent-_right cur-_left;}delete cur;}//有两个孩子else if (cur-_left cur-_right){Node* del cur-_right;//找右子树最小节点while (del-_left){del del-_left;}//赋值cur-_key del-_key;//待删除节点的右指向最小节点右cur-_right del-_right;//删除最小节点delete del;}return true;}二叉搜索树的删除操作比较复杂需要考虑删除节点的情况分为三种 待删除节点为叶子节点直接删除该节点即可。 待删除节点只有一个孩子将该节点的孩子节点接到该节点的父节点上然后删除该节点。 待删除节点有两个孩子找到该节点的右子树中的最小节点将其键值赋值给待删除节点然后删除最小节点。
上述代码实现了二叉搜索树的删除操作。首先从根节点开始循环遍历整棵树查找待删除节点及其父节点。如果没有找到待删除节点则返回删除失败否则根据待删除节点的情况进行不同的操作。如果待删除节点为叶子节点则直接删除该节点如果待删除节点只有一个孩子则将孩子节点接到父节点上然后删除该节点如果待删除节点有两个孩子则找到右子树中的最小节点将其键值赋值给待删除节点然后删除最小节点。最后返回删除成功。
二叉搜索树中序遍历实现 void _InOrder(const Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}二叉搜索树的中序遍历是指按照节点键值的大小关系先遍历左子树再遍历根节点最后遍历右子树。因为二叉搜索树的中序遍历结果是一个有序序列因此可以使用中序遍历来实现对二叉搜索树的排序操作。
上述代码实现了二叉搜索树的中序遍历操作。首先判断当前节点是否为空如果为空则返回否则按照左子树、根节点、右子树的顺序递归遍历整棵树并输出节点的键值。
二叉搜索树的应用 K模型K模型是指只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索的值。例如可以以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。 KV模型KV模型是指每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见例如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对再比如统计单词次数统计成功后给定单词就可以快速找到其出现的次数单词与其出现次数就是word, count就构成一种键值对。二叉搜索树可以用来实现KV模型以key作为二叉搜索树的节点value作为节点的值通过比较key的大小关系来实现快速查找、插入和删除节点的操作。
将上述二叉搜索树修改为KV模型
二叉树节点定义示例代码
templateclass K, class V
class BStreeNode
{
public:BStreeNode(const K key, const V value):_key(key), _value(value), _left(nullptr), _right(nullptr){}K _key;V _value;BStreeNode* _left;BStreeNode* _right;
};中序输出代码 void _InOrder(const Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key : root-_value endl;_InOrder(root-_right);}测试代码
void test1()
{BStreestring, string tree;tree.insert(apple, 苹果);tree.insert(banana, 香蕉);tree.insert(orange, 橘子);tree.insert(peach, 桃子);tree.insert(pear, 梨);tree.InOrder();
}运行结果 二叉搜索树的性能分析
插入和删除操作都需要先进行查找操作因此二叉搜索树的查找效率代表了二叉搜索树各个操作的性能。对于有n个节点的二叉搜索树如果每个元素查找的概率相等那么二叉搜索树的平均查找长度是节点在二叉搜索树的深度的函数即节点越深则比较次数越多。
需要注意的是对于同一个关键码集合如果各关键码插入的次序不同可能会得到不同结构的二叉搜索树。因为二叉搜索树的结构取决于插入顺序如果插入的顺序不同可能会导致树的结构不同进而影响树的查找效率。因此在实际应用中需要根据实际情况选择合适的插入顺序以获得更好的性能。 最优情况下二叉搜索树的高度为 log2N每一次查找可以将搜索范围缩小一半因此平均比较次数为 log2N。
最差情况下二叉搜索树的高度为 (N-1)每一次查找只能将搜索范围缩小一层因此平均比较次数为 (12…N)/N (N1)/2约等于 N/2。这种情况发生在插入的数据是有序的时候导致二叉搜索树退化为链表。此时可以使用平衡二叉树来解决这个问题。
总结
二叉搜索树是一种非常常见的数据结构它是一棵二叉树其中每个节点都包含一个键值且左子树的所有节点的键值小于当前节点的键值右子树的所有节点的键值大于当前节点的键值。这种特定的结构使得二叉搜索树能够快速地进行查找、插入、删除等操作。
在实际应用中二叉搜索树被广泛使用如在数据库索引、编译器符号表、路由表等领域。对于一个包含n个节点的二叉搜索树其查找、插入、删除的时间复杂度均为O(logn)这使得它在处理大数据量时具有很高的效率。
但是二叉搜索树也存在一些问题。当数据集合中的元素是随机分布的时二叉搜索树的性能是非常好的。但是当数据集合中的元素是有序的时二叉搜索树的性能会退化为O(n)这就是所谓的“不平衡问题”。为了解决这个问题我们可以使用平衡二叉树、红黑树等数据结构来优化二叉搜索树。
此外二叉搜索树在插入重复元素时也存在问题。如果我们简单地将重复元素插入到二叉搜索树中那么查找和删除操作就会变得非常麻烦。为了解决这个问题我们可以使用多重集合、哈希表等数据结构来处理重复元素。
总之二叉搜索树是一种非常重要的数据结构它能够快速地进行查找、插入、删除等操作但是在实际应用中需要注意避免和解决一些问题如不平衡问题、重复元素问题等。
文章总结不易如果觉得有所帮助的话就文中所有代码均放在gitee上关注博主持续更新中…
