深入了解二叉搜索树：原理、实现与应用

时间：2024-03-11 07:07:03

目录

一、介绍二叉搜索树

二、二叉搜索树的基本性质

三、二叉搜索树的实现

四、总结

在计算机科学中，数据结构是构建算法和程序的基础。其中，二叉搜索树（Binary Search Tree，简称 BST）作为一种常见的数据结构，在很多应用中发挥着重要作用。它具有以下特点：每个节点最多有两个子节点，左子节点的值小于父节点的值，右子节点的值大于父节点的值。这一特性使得二叉搜索树具有快速的查找、插入和删除操作。

一、介绍二叉搜索树

定义和特点

  1. 有序性：二叉搜索树中序遍历的结果是按照节点值的大小顺序排列的，因此可以方便地进行有序性相关的操作。

  2. 快速查找：在平衡的情况下，对于含有 n 个节点的二叉搜索树，查找、插入和删除操作的时间复杂度均为 O(log n)，这使得它在大规模数据处理中具有明显的优势。

为什么选择二叉搜索树呢？

二叉搜索树在各种算法和程序设计中都有广泛的应用。其快速的查找特性使得它成为了许多数据存储和检索系统中的重要组成部分，例如数据库索引、编译器符号表等。同时，二叉搜索树也作为其他高级数据结构的基础，如平衡二叉树（AVL 树、红黑树）等的实现都离不开对二叉搜索树的理解和运用。

这些基本性质使得二叉搜索树成为一种高效的数据结构，适用于需要频繁进行查找、插入和删除操作的场景。然而，需要注意的是，最坏情况下，即树不平衡的情况下，这些操作的时间复杂度可能会退化到 O(n)，因此为了维持其优势，可以采用平衡二叉搜索树（如 AVL 树、红黑树，我们将在后续文章中介绍这两种数据结构）来保持树的平衡性。

通过以上介绍，我们对二叉搜索树的定义、特点以及应用场景有了初步的了解。接下来，我们将深入探讨二叉搜索树的基本性质、实现方式以及在实际应用中的价值。

二、二叉搜索树的基本性质

  • 有序性：若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；若它的右子树不为空，则右子树上所有节点的值都大于根节点的值；它的左右子树也分别为二叉搜索树。

  • 中序遍历有序性：对二叉搜索树进行中序遍历，可以得到一个有序的节点值序列。即，遍历结果按照从小到大（或从大到小）的顺序排列。

  • 查找操作的时间复杂度：对于一个含有 n 个节点的平衡二叉搜索树，查找特定值的节点的时间复杂度为 O(log n)。这是因为每次查找都可以通过与当前节点的比较，缩小查找范围为树的一半，并且随着树的平衡程度提高，查找效率更高。

  • 插入操作的时间复杂度：在平衡的情况下，插入新节点的时间复杂度也是 O(log n)。插入操作首先要找到合适的位置，然后执行节点的插入。由于每次插入都会调整树的结构以保持平衡，所以插入的时间复杂度与树的高度成对数关系。

  • 删除操作的时间复杂度：与插入操作类似，在平衡的情况下，删除节点的时间复杂度也是 O(log n)。删除操作涉及节点的查找、删除以及树的平衡调整。

这些基本性质使得二叉搜索树成为一种高效的数据结构，适用于需要频繁进行查找、插入和删除操作的场景。然而，需要注意的是，最坏情况下，即树不平衡的情况下，这些操作的时间复杂度可能会退化到 O(n)，因此为了维持其优势，可以采用平衡二叉搜索树（如 AVL 树、红黑树）来保持树的平衡性。

三、二叉搜索树的实现

  • 节点结构设计

 template<class K>
 struct 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);
     else
         return 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;
         else
             return 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);
     else
         return 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;
         else
             return false;
     }
     cur = new Node(key);
     if (parent->_key > cur->_key)
         parent->_left = cur;
     else
         parent->_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;
                     else
                         parent->_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;
                 else
                     rightMinParent->_right = rightMin->_right;
                 delete rightMin;
                 return true;
             }
         }
     }
     return false;
 }

bool Erase(const K& key) 函数接受一个键值 key，用于删除二叉搜索树中对应键值的节点。

在函数内部：

  1. 首先，定义了两个指针 cur 和 parent，分别初始化为根节点 _root 和空指针。

  2. 进入循环，不断地在二叉搜索树中搜索要删除的节点，直到找到对应的节点或者搜索到空节点为止。

  3. 在每一步迭代中，根据当前节点的键值和目标键值的大小关系，更新 parent 和 cur 指针，以便后续操作使用。

  4. 如果找到了要删除的节点，根据其左右子节点的情况执行相应的删除操作：

 - 如果要删除的节点没有左子节点，直接将其右子节点替换当前节点的位置，并删除当前节点。
 - 如果要删除的节点没有右子节点，直接将其左子节点替换当前节点的位置，并删除当前节点。
 - 如果要删除的节点有左右子节点，找到其右子树中最小的节点 `rightMin`，将其值替换到当前节点，并删除 `rightMin` 节点。

最后，如果成功删除了节点，则返回 true，否则返回 false。

这段代码与之前提到的 _EraseR 函数实现了相同的功能，但是采用了迭代的方式进行操作。两种方法都可以有效地删除二叉搜索树中的节点，选择使用哪种方法取决于个人偏好和具体情况。

  • 初始化树与销毁树

构造函数非常简单，构造一个空树即可。

 //方法1:
 BSTree()
     :_root(nullptr)
 {}
 //方法2:
 class BSTree{
 public:
     //...
     BSTree() = default;
 private:
     //....
     Node* _root = nullptr;
 }

  1. 方法1：构造函数 BSTree(): 这是一个无参数的构造函数，在其中将 _root 初始化为 nullptr，表示初始时二叉搜索树为空。

  2. 方法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)，这两个函数的作用是销毁整棵二叉搜索树，释放动态分配的内存。

  1. 析构函数 ~BSTree(): 这是 BSTree 类的析构函数，用于销毁二叉搜索树对象。在析构函数中调用了一个辅助函数 Destory(_root)，传入根节点指针 _root，从根节点开始递归销毁整棵树。

  2. 辅助函数 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 BSTree<K>& bst) {
     _root = Copy(bst._root);
 }

用于拷贝二叉搜索树的辅助函数 _Copy 和拷贝构造函数 BSTree(const BSTree<K>& bst)。

  1. 辅助函数 _Copy: 这个函数用于深度拷贝一棵以 root 为根的二叉树。如果 root 为空，则直接返回空指针；否则，创建一个新节点 copyNode，并将根节点的键值拷贝过去。然后递归调用 _Copy 函数分别拷贝左子树和右子树，并将得到的左右子树连接到 copyNode 的左右孩子上。最后返回拷贝的树的根节点。

  2. 拷贝构造函数 BSTree(const BSTree<K>& bst): 这是二叉搜索树类的拷贝构造函数，用于根据给定的二叉搜索树 bst 进行拷贝构造。在拷贝构造函数中，将给定二叉搜索树的根节点传入辅助函数 _Copy 中进行拷贝操作，并将得到的拷贝树的根节点赋值给当前对象的根节点 _root。

通过这样的设计，可以实现二叉搜索树的拷贝构造，即创建一个与给定二叉搜索树结构相同但是完全独立的新二叉搜索树。这样的拷贝构造函数能够避免共享节点带来的问题，确保每棵树都有自己独立的节点内存空间。避免了浅拷贝带来的危害。

其次是赋值重载函数：

 //方法1:
 BSTree<K>& operator=(BSTree<K> bst){
     swap(_root, bst._root);
     return *this;
 }
 //方法2:
 const BSTree<K>& operator=(const BSTree<K>& bst)
 {
     if (this != &bst) //防止自己给自己赋值
     {
         _Destory(_root); //先将当前的二叉搜索树中的结点释放
         _root = _Copy(bst._root); //拷贝t对象的二叉搜索树
     }
     return *this; //支持连续赋值
 }

在上述代码中，展示了两种不同的赋值操作符重载方法：

  1. 方法1：这里的赋值操作符重载接受一个传值参数 bst。在函数内部，通过调用 swap 函数交换当前对象的根节点和参数对象 bst 的根节点，实现了两个对象之间的指针交换。函数在接收右值时并没有使用引用进行接收（即函数参数为 BSTree<K>），因为这样可以间接调用BSTree的拷贝构造函数完成拷贝构造。我们只需将这个拷贝构造出来的对象的二叉搜索树与this对象的二叉搜索树进行交换，就相当于完成了赋值操作，而拷贝构造出来的对象bst会在该赋值运算符重载函数调用结束时自动析构。最后返回当前对象的引用。

  2. 方法2：这是一种使用常量引用作为参数的赋值操作符重载方式。在函数内部，首先检查是否自己给自己赋值，如果不是，则先销毁当前对象的二叉搜索树，然后通过 _Copy 函数深度拷贝参数对象 bst 的二叉搜索树，将拷贝后的根节点赋值给当前对象的根节点。最后返回当前对象的引用，以支持链式赋值操作。

四、总结

二叉搜索树（Binary Search Tree，BST）是一种常见的数据结构，在很多应用场景中都有广泛的应用。以下是一些二叉搜索树的应用场景：

  • 数据库系统：在数据库系统中，索引通常使用二叉搜索树来实现快速的数据查找和检索操作。

  • 字典：二叉搜索树可以用于实现字典数据结构，使得插入、删除和查找单词等操作更加高效。

  • 文件系统：在文件系统中，可以使用二叉搜索树来组织文件的目录结构，以便快速地查找和管理文件。

  • 符号表：在编程语言中，符号表用于存储变量名和对应的数值或对象，二叉搜索树可以用于实现符号表的快速查找功能。

  • 资源分配：在资源管理系统中，可以使用二叉搜索树来动态地分配和回收资源，以实现高效的资源管理。

总的来说，二叉搜索树在需要快速查找、插入和删除操作的场景中有着广泛的应用，它的特性使得在大量数据中进行高效的搜索成为可能。

二叉搜索树插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。我们观察下图两种搜索树：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：O(log n)。 最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：\frac{N}{2}。

如果向一棵树中输入预先排序的数据，那么一连串的 Insert 操作将花费二次时间，而用链式表实现 Insert 的代价会非常巨大，因为此时的树只由哪些没有左儿子的节点组成，就退化成单支树，二叉搜索树的性能就失去了。一种解决方法就是要有一个称为平衡的附加条件的结构条件，即任何节点的深度均不能过深。

有许多一般的算法可以实现平衡树。但是，大部分算法都要比标准的二叉查找树复得多，而且更新要平均花费更长的时间，不过，它们确实防止了处理起来非常麻烦的一简单情形。我的下一篇文章中，我们将介绍最老的一种平衡查找树，即AVL树。

因此，在选择数据结构时，在选择数据结构时，需要考虑问题的特点和需求。如果需要频繁进行查找和插入操作，并且不关心维持有序性，可以选择哈希表等数据结构。而如果需要快速查找有序元素、范围查询等操作，并且不需要频繁修改数据，二叉搜索树是一个不错的选择。如果希望在任何情况下都能保持树的平衡，可以选择平衡二叉搜索树，如AVL树或红黑树。

本文代码的完整实现在此处，二叉搜素树 · 比奇堡的Zyb/每日学习 - 码云 - 开源中国 (gitee.com)。

相关文章