湖南网站开发企业,如何做展示型网站,做网站要多大空间,建设通手机版目录 一、介绍二叉搜索树
二、二叉搜索树的基本性质
三、二叉搜索树的实现
四、总结 在计算机科学中#xff0c;数据结构是构建算法和程序的基础。其中#xff0c;二叉搜索树#xff08;Binary Search Tree#xff0c;简称 BST#xff09;作为一种常见的数据结构#…目录 一、介绍二叉搜索树
二、二叉搜索树的基本性质
三、二叉搜索树的实现
四、总结 在计算机科学中数据结构是构建算法和程序的基础。其中二叉搜索树Binary Search Tree简称 BST作为一种常见的数据结构在很多应用中发挥着重要作用。它具有以下特点每个节点最多有两个子节点左子节点的值小于父节点的值右子节点的值大于父节点的值。这一特性使得二叉搜索树具有快速的查找、插入和删除操作。
一、介绍二叉搜索树
定义和特点 有序性二叉搜索树中序遍历的结果是按照节点值的大小顺序排列的因此可以方便地进行有序性相关的操作。 快速查找在平衡的情况下对于含有 n 个节点的二叉搜索树查找、插入和删除操作的时间复杂度均为 O(log n)这使得它在大规模数据处理中具有明显的优势。
为什么选择二叉搜索树呢
二叉搜索树在各种算法和程序设计中都有广泛的应用。其快速的查找特性使得它成为了许多数据存储和检索系统中的重要组成部分例如数据库索引、编译器符号表等。同时二叉搜索树也作为其他高级数据结构的基础如平衡二叉树AVL 树、红黑树等的实现都离不开对二叉搜索树的理解和运用。
这些基本性质使得二叉搜索树成为一种高效的数据结构适用于需要频繁进行查找、插入和删除操作的场景。然而需要注意的是最坏情况下即树不平衡的情况下这些操作的时间复杂度可能会退化到 O(n)因此为了维持其优势可以采用平衡二叉搜索树如 AVL 树、红黑树我们将在后续文章中介绍这两种数据结构来保持树的平衡性。
通过以上介绍我们对二叉搜索树的定义、特点以及应用场景有了初步的了解。接下来我们将深入探讨二叉搜索树的基本性质、实现方式以及在实际应用中的价值。 二、二叉搜索树的基本性质 有序性若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树。 中序遍历有序性对二叉搜索树进行中序遍历可以得到一个有序的节点值序列。即遍历结果按照从小到大或从大到小的顺序排列。 查找操作的时间复杂度对于一个含有 n 个节点的平衡二叉搜索树查找特定值的节点的时间复杂度为 O(log n)。这是因为每次查找都可以通过与当前节点的比较缩小查找范围为树的一半并且随着树的平衡程度提高查找效率更高。 插入操作的时间复杂度在平衡的情况下插入新节点的时间复杂度也是 O(log n)。插入操作首先要找到合适的位置然后执行节点的插入。由于每次插入都会调整树的结构以保持平衡所以插入的时间复杂度与树的高度成对数关系。 删除操作的时间复杂度与插入操作类似在平衡的情况下删除节点的时间复杂度也是 O(log n)。删除操作涉及节点的查找、删除以及树的平衡调整。
这些基本性质使得二叉搜索树成为一种高效的数据结构适用于需要频繁进行查找、插入和删除操作的场景。然而需要注意的是最坏情况下即树不平衡的情况下这些操作的时间复杂度可能会退化到 O(n)因此为了维持其优势可以采用平衡二叉搜索树如 AVL 树、红黑树来保持树的平衡性。 三、二叉搜索树的实现 节点结构设计 templateclass Kstruct BSTreeNode {typedef BSTreeNode K Node;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}Node* _left;Node* _right;K _key;};
这段代码使用了模板类定义了一个简单的二叉搜索树节点结构包含了左子节点指针、右子节点指针和节点值并使用模板类支持存储不同类型的值。若对模板类使用存在疑问可以点击此处。这样的设计可以方便地构建二叉搜索树并在节点中存储不同类型的数据。 查找操作的实现
这个操作一般需要返回指向树中具有需查找的关键字的节点的指针如果不存在这个节点则返回nullptr。我们根据二叉树的特性可以将查找分为两种一种递归实现一种非递归实现。
a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。 b、最多查找高度次走到到空还没找到这个值不存在。 递归实现 bool _FindR(Node* root, const K key) {if (root nullptr)return false;if (root-_key key)return _FindR(root-_left, key);else if (root-_key key)return _FindR(root-_right, key);elsereturn true;}bool FindR(const K key) { return _FindR(_root, key); }
_FindR中的两次递归调用事实上都是尾递归。尾递归的使用在这里是合理的因为算法表达式的简明性是以速度的降低为代价的而这里所使用的栈空间也只不过是 O(log n) 而已。
非递归实现 Node* Find(const K key) {Node* cur _root;while (cur ! nullptr) {if (cur-_key key)cur cur-_left;else if (cur-_key key)cur cur-_right;elsereturn cur;}return nullptr;}
查找的代码较为简单我们不再进行赘述。 插入操作的实现
进行插入操作在概念上是简单的为了将节点 X 插入到树中我们可以像使用 Find一样沿着树查找。如果找到值为 X 的节点则什么也不做或是做一些”更新“。否则将 X 插入到遍历的路径上的最后一个节点上。插入操作同样拥有两种方式一种递归实现一种非递归实现。
递归实现 bool _InsertR(Node* root, const K key) {if (root nullptr) {root new Node(key);return true;}if (root-_key key)return _InsertR(root-_left, key);else if (root-_key key)return _InsertR(root-_right, key);elsereturn false;}bool InsertR(const K key) { return _InsertR(_root, key); }
非递归实现 bool Insert(const K key) {if (_root nullptr) {_root new Node(key);return true;}Node* cur _root;Node* parent nullptr;while (cur ! nullptr) {parent cur;if (cur-_key key)cur cur-_left;else if (cur-_key key)cur cur-_right;elsereturn false;}cur new Node(key);if (parent-_key cur-_key)parent-_left cur;elseparent-_right cur;return true;} 删除操作的实现
正如许多数据结构一样最困难的操作是删除。一旦发现要删除的节点我们就需要考虑多种可能的情况。
如果一个节点是一片树叶那么可以直接删除。如果节点有一个儿子则该节点可以将其父节点调整指针绕过该节点指向该节点的一个儿子然后删除该节点。如图 如果一个节点是一片树叶那么可以直接删除从图中来看就是删除节点 C 。那么我们只需要将 B 的右节点置空即可。如果节点有一个儿子从图中来看就是删除节点 B。我们只需要将 A 的右节点指向 节点 C然后将节点 B delete即可。
复杂的情况是处理具有两个儿子的节点。一般的删除策略是用其右子树中最小的数据代替该节点的数据并删除那个节点。因为右子树中最小的节点不可能有左儿子。将被删除节点的值与右子树中最小的节点的值进行交换然后按之前删除有一个儿子的节点的方式删除。从图中来看就说删除节点 A。我们来看下图 我们要删除节点 A 的话我们需要找到 A 的右子树中最小的节点并与其进行节点值的交换这样不会破坏处理除了要删除节点外的树的有序状态而且待删除的节点就变成了 A 的右子树中最小的节点。若待删除结点的右子树为空那么当我们在二叉搜索树当中找到该结点后只需先让其父结点指向该结点的左孩子结点其左孩子是nullptr然后再将该结点释放便完成了该结点的删除进行删除操作后仍保持二叉搜索树的特性。
删除操作同样拥有两种方式一种递归实现一种非递归实现。
递归实现 bool _EraseR(Node* root, const K key) {if (root nullptr)return false;if (root-_key key)return _EraseR(root-_left, key);else if (root-_key key)return _EraseR(root-_right, key);else {Node* del root;if (root-_right nullptr)root root-_left;else if (root-_left nullptr)root root-_right;else {Node* rightMin root-_right;while (rightMin-_left) {rightMin rightMin-_left;}swap(root-_key, rightMin-_key);return _EraseR(root-_right, key);}delete del;return true;}}bool EraseR(const K key) { return _EraseR(_root, key); }
我们一般将_EraseR 函数作为一个私有函数用于在二叉搜索树中递归地删除节点。将EraseR 函数作为一个公有函数用于被用户调用。具体分析如下 bool _EraseR(Node* root, const K key)函数接受二叉搜索树的根节点引用 root 和要删除的值 key。其中 Node* root 这是一个引用指向当前递归调用中正在处理的节点的指针。必须通过引用传递这样可以确保对节点的修改在递归结束后得以保留。否则无法保证二叉树当中各个结点的连接关系。 如果当前节点为空即到达叶子节点则表示找不到要删除的值返回 false。 如果当前节点的值大于要删除的值则递归地在左子树中删除节点。 如果当前节点的值小于要删除的值则递归地在右子树中删除节点。 如果当前节点的值等于要删除的值进行以下操作 创建一个指针 del 指向当前节点用于最后释放内存。 如果当前节点的右子树为空将当前节点的左子树作为当前节点的位置。 如果当前节点的左子树为空将当前节点的右子树作为当前节点的位置。 如果当前节点的左右子树都存在找到当前节点右子树中最小的节点 rightMin将其值与当前节点交换然后递归地在右子树中删除 rightMin 节点。 删除完成后释放内存并返回 true。
bool EraseR(const K key) 函数最终会返回 _EraseR 函数的返回值表示删除是否成功。
通过递归的方式实现了二叉搜索树的节点删除操作同时处理了不同情况下节点的替换和内存释放。需要注意的是在删除含有两个子节点的节点时找到右子树中最小的节点并进行交换操作确保删除后仍然满足二叉搜索树的性质。
非递归实现 bool Erase(const K key) {Node* cur _root;Node* parent nullptr;while (cur ! nullptr) {if (cur-_key key) {parent cur;cur cur-_left;}else if (cur-_key key) {parent cur;cur cur-_right;}else{if (cur-_left nullptr) {if (cur _root) {_root cur-_right;}else {if (parent-_left cur) parent-_left cur-_right;else parent-_right cur-_right;}delete cur;return true;}else if (cur-_right nullptr) {if (cur _root) {_root cur-_left;}else {if (parent-_left cur)parent-_left cur-_left;elseparent-_right cur-_left;}delete cur;return true;}else{//替换Node* rightMin cur-_right;Node* rightMinParent cur;while (rightMin-_left ! nullptr) {rightMinParent rightMin;rightMin rightMin-_left;}cur-_key rightMin-_key;if (rightMin rightMinParent-_left)rightMinParent-_left rightMin-_right;elserightMinParent-_right rightMin-_right;delete rightMin;return true;}}}return false;}
bool Erase(const K key) 函数接受一个键值 key用于删除二叉搜索树中对应键值的节点。
在函数内部 首先定义了两个指针 cur 和 parent分别初始化为根节点 _root 和空指针。 进入循环不断地在二叉搜索树中搜索要删除的节点直到找到对应的节点或者搜索到空节点为止。 在每一步迭代中根据当前节点的键值和目标键值的大小关系更新 parent 和 cur 指针以便后续操作使用。 如果找到了要删除的节点根据其左右子节点的情况执行相应的删除操作 - 如果要删除的节点没有左子节点直接将其右子节点替换当前节点的位置并删除当前节点。- 如果要删除的节点没有右子节点直接将其左子节点替换当前节点的位置并删除当前节点。- 如果要删除的节点有左右子节点找到其右子树中最小的节点 rightMin将其值替换到当前节点并删除 rightMin 节点。
最后如果成功删除了节点则返回 true否则返回 false。
这段代码与之前提到的 _EraseR 函数实现了相同的功能但是采用了迭代的方式进行操作。两种方法都可以有效地删除二叉搜索树中的节点选择使用哪种方法取决于个人偏好和具体情况。 初始化树与销毁树
构造函数非常简单构造一个空树即可。 //方法1:BSTree():_root(nullptr){}//方法2:class BSTree{public://...BSTree() default;private://....Node* _root nullptr;} 方法1构造函数 BSTree(): 这是一个无参数的构造函数在其中将 _root 初始化为 nullptr表示初始时二叉搜索树为空。 方法2类 BSTree 中的私有成员 _root 的初始化 在类 BSTree 中使用了私有成员 _root 来表示二叉搜索树的根节点而在这段代码中利用了成员初始化列表的方式将 _root 初始化为 nullptr。这样做可以确保对象被创建时 _root 成员变量会被正确初始化为 nullptr。
综合来说这两种方式都可以用来初始化 _root 成员变量其中一个是自定义的构造函数另一个是默认的构造函数。它们的效果是相同的都用于确保 _root 成员变量在创建二叉搜索树对象时被正确初始化为空。选择使用哪种方式取决于个人偏好和具体需求。
析构函数完成对象中二叉搜索树结点的释放注意释放时采用后序释放当二叉搜索树中的结点被释放完后将对象当中指向二叉搜索树的指针及时置空即可。 ~BSTree(){Destory(_root);}void Destory(Node* root) {if (root nullptr)return;Destory(root-_left);Destory(root-_right);delete root;}
类 BSTree 的析构函数 ~BSTree() 和一个辅助函数 Destory(Node* root)这两个函数的作用是销毁整棵二叉搜索树释放动态分配的内存。 析构函数 ~BSTree(): 这是 BSTree 类的析构函数用于销毁二叉搜索树对象。在析构函数中调用了一个辅助函数 Destory(_root)传入根节点指针 _root从根节点开始递归销毁整棵树。 辅助函数 Destory(Node* root): 这个函数用于递归销毁以 root 为根的子树。首先检查当前节点是否为空如果为空则直接返回。然后递归调用 Destory(root-_left) 和 Destory(root-_right)分别销毁左子树和右子树即后序释放。最后释放当前节点所占用的内存空间即 delete root。 通过这样的设计当二叉搜索树对象被销毁时析构函数会自动调用进而递归地销毁整棵树。这样可以有效释放二叉搜索树节点所占用的内存避免内存泄漏问题。这种在析构函数中进行递归释放的方式是常见的二叉树析构方法。 拷贝构造函数和赋值重载函数
首先是拷贝构造函数 //拷贝树Node* _Copy(Node* root){if (root nullptr) //空树直接返回return nullptr;Node* copyNode new Node(root-_key); //拷贝根结点copyNode-_left _Copy(root-_left); //拷贝左子树copyNode-_right _Copy(root-_right); //拷贝右子树return copyNode; //返回拷贝的树}//拷贝构造函数BSTree(const BSTreeK bst) {_root Copy(bst._root);}
用于拷贝二叉搜索树的辅助函数 _Copy 和拷贝构造函数 BSTree(const BSTreeK bst)。 辅助函数 _Copy: 这个函数用于深度拷贝一棵以 root 为根的二叉树。如果 root 为空则直接返回空指针否则创建一个新节点 copyNode并将根节点的键值拷贝过去。然后递归调用 _Copy 函数分别拷贝左子树和右子树并将得到的左右子树连接到 copyNode 的左右孩子上。最后返回拷贝的树的根节点。 拷贝构造函数 BSTree(const BSTreeK bst): 这是二叉搜索树类的拷贝构造函数用于根据给定的二叉搜索树 bst 进行拷贝构造。在拷贝构造函数中将给定二叉搜索树的根节点传入辅助函数 _Copy 中进行拷贝操作并将得到的拷贝树的根节点赋值给当前对象的根节点 _root。
通过这样的设计可以实现二叉搜索树的拷贝构造即创建一个与给定二叉搜索树结构相同但是完全独立的新二叉搜索树。这样的拷贝构造函数能够避免共享节点带来的问题确保每棵树都有自己独立的节点内存空间。避免了浅拷贝带来的危害。
其次是赋值重载函数 //方法1:BSTreeK operator(BSTreeK bst){swap(_root, bst._root);return *this;}//方法2:const BSTreeK operator(const BSTreeK bst){if (this ! bst) //防止自己给自己赋值{_Destory(_root); //先将当前的二叉搜索树中的结点释放_root _Copy(bst._root); //拷贝t对象的二叉搜索树}return *this; //支持连续赋值}
在上述代码中展示了两种不同的赋值操作符重载方法 方法1这里的赋值操作符重载接受一个传值参数 bst。在函数内部通过调用 swap 函数交换当前对象的根节点和参数对象 bst 的根节点实现了两个对象之间的指针交换。函数在接收右值时并没有使用引用进行接收即函数参数为 BSTreeK因为这样可以间接调用BSTree的拷贝构造函数完成拷贝构造。我们只需将这个拷贝构造出来的对象的二叉搜索树与this对象的二叉搜索树进行交换就相当于完成了赋值操作而拷贝构造出来的对象bst会在该赋值运算符重载函数调用结束时自动析构。最后返回当前对象的引用。 方法2这是一种使用常量引用作为参数的赋值操作符重载方式。在函数内部首先检查是否自己给自己赋值如果不是则先销毁当前对象的二叉搜索树然后通过 _Copy 函数深度拷贝参数对象 bst 的二叉搜索树将拷贝后的根节点赋值给当前对象的根节点。最后返回当前对象的引用以支持链式赋值操作。 四、总结
二叉搜索树Binary Search TreeBST是一种常见的数据结构在很多应用场景中都有广泛的应用。以下是一些二叉搜索树的应用场景 数据库系统在数据库系统中索引通常使用二叉搜索树来实现快速的数据查找和检索操作。 字典二叉搜索树可以用于实现字典数据结构使得插入、删除和查找单词等操作更加高效。 文件系统在文件系统中可以使用二叉搜索树来组织文件的目录结构以便快速地查找和管理文件。 符号表在编程语言中符号表用于存储变量名和对应的数值或对象二叉搜索树可以用于实现符号表的快速查找功能。 资源分配在资源管理系统中可以使用二叉搜索树来动态地分配和回收资源以实现高效的资源管理。
总的来说二叉搜索树在需要快速查找、插入和删除操作的场景中有着广泛的应用它的特性使得在大量数据中进行高效的搜索成为可能。
二叉搜索树插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。我们观察下图两种搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为O(log n)。 最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为\frac{N}{2}。
如果向一棵树中输入预先排序的数据那么一连串的 Insert 操作将花费二次时间而用链式表实现 Insert 的代价会非常巨大因为此时的树只由哪些没有左儿子的节点组成就退化成单支树二叉搜索树的性能就失去了。一种解决方法就是要有一个称为平衡的附加条件的结构条件即任何节点的深度均不能过深。
有许多一般的算法可以实现平衡树。但是大部分算法都要比标准的二叉查找树复得多而且更新要平均花费更长的时间不过它们确实防止了处理起来非常麻烦的一简单情形。我的下一篇文章中我们将介绍最老的一种平衡查找树即AVL树。
因此在选择数据结构时在选择数据结构时需要考虑问题的特点和需求。如果需要频繁进行查找和插入操作并且不关心维持有序性可以选择哈希表等数据结构。而如果需要快速查找有序元素、范围查询等操作并且不需要频繁修改数据二叉搜索树是一个不错的选择。如果希望在任何情况下都能保持树的平衡可以选择平衡二叉搜索树如AVL树或红黑树。 本文代码的完整实现在此处二叉搜素树 · 比奇堡的Zyb/每日学习 - 码云 - 开源中国 (gitee.com)。
