数据结构——二叉搜索树

🕗 发布于 2024-09-23 06:36 数据结构

二叉搜索树

二叉搜索树

二叉搜索树

⼆叉搜索树的概念

⼆叉搜索树⼜称⼆叉排序树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树：

若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值
若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结点的值
它的左右⼦树也分别为⼆叉搜索树
⼆叉搜索树中可以⽀持插⼊相等的值，也可以不⽀持插⼊相等的值，具体看使⽤场景定义，后续map/set/multimap/multiset系列容器底层就是⼆叉搜索树，其中map/set不⽀持插⼊相等值multimap/multiset⽀持插⼊相等值

在这里插入图片描述

⼆叉搜索树的性能分析

最优情况下，⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)，其⾼度为：O(log2 N)
最差情况下，⼆叉搜索树退化为单⽀树(或者类似单⽀)，其⾼度为：O(N/2 )

二叉搜索树（BST）的性能主要依赖于树的形状。以下是其性能的详细分析：

平均性能

查找：O(log N)
插入：O(log N)
删除：O(log N)

这些性能假设树是平衡的，即每个节点的左右子树高度差不超过1。在这种情况下，树的高度大约为 log N，因此操作的时间复杂度为 O(log N)。

最坏性能

查找：O(N)
插入：O(N)
删除：O(N)

在最坏情况下，例如树退化成链表（所有节点只有一个子节点），树的高度变为 N，操作的时间复杂度变为 O(N)。

平衡性对性能的影响

完全二叉树：在这种树中，每一层都被完全填充，性能接近于 O(log N)。

AVL 树：一种自平衡的二叉搜索树，任何时刻保持平衡，因此所有操作都能在 O(log N) 时间内完成。

红黑树：另一种自平衡的二叉搜索树，虽然略逊色于 AVL 树的严格平衡，但仍保证 O(log N) 的操作时间。

操作详解
查找：从根节点开始，按键值与当前节点键值比较决定向左或向右子树移动。这个过程在平衡树中是对数级别的时间复杂度。

插入：查找适当的位置后插入新节点，并可能需要调整树结构（例如，通过旋转）以保持树的平衡。这在自平衡树中通常是对数级别的时间复杂度。

删除：查找并删除节点后，需要调整树结构以保持平衡。删除操作可能涉及节点替换（例如，使用右子树的最小节点替代），并可能需要进行树结构的调整。

在这里插入图片描述

二叉搜索树的插入

在二叉搜索树（BST）中插入一个新节点的过程包括以下步骤：

从根节点开始：.

首先，将新节点的键值与当前节点的键值进行比较。

决定插入方向：

如果新节点的键值小于当前节点的键值，则移动到当前节点的左子树。

如果新节点的键值大于当前节点的键值，则移动到当前节点的右子树。

递归或迭代插入：

如果左子树或右子树为空（即到达一个叶节点的位置），则在该位置插入新节点。

如果左子树或右子树不为空，则递归或迭代执行插入过程，直到找到合适的位置。

更新树结构：插入节点后，树的结构可能需要更新。如果树是自平衡的（如 AVL 树或红黑树），可能需要调整树的平衡性，例如通过旋转操作来维持树的平衡。

示例代码（伪代码）

void insert(Node*& root, int key) {
    if (root == nullptr) {
        root = new Node(key); // 插入新节点
    } else if (key < root->key) {
        insert(root->left, key); // 递归插入到左子树
    } else {
        insert(root->right, key); // 递归插入到右子树
    }
}

关键点

查找插入位置：通过比较键值确定插入位置。

保持 BST 属性：插入新节点后，树仍应保持二叉搜索树的性质。

自平衡树处理：如果使用自平衡树，如 AVL 树或红黑树，插入后需要额外步骤来调整树的平衡。

二叉搜索树的查找

在二叉搜索树（BST）中，查找某个节点的步骤非常简单，因为 BST 的特性保证了每个节点的左子树中的所有节点值都小于该节点的值，右子树中的所有节点值都大于该节点的值。基于这一特性，查找操作可以高效地通过比较来进行。

查找步骤

从根节点开始：

如果树为空，则返回 null 或相应的错误提示，因为节点不存在。

比较节点值：

如果查找的值等于当前节点的值，说明找到了目标节点，返回该节点。
如果查找的值小于当前节点的值，则在当前节点的左子树中继续查找。
如果查找的值大于当前节点的值，则在当前节点的右子树中继续查找。

递归或迭代：

递归方法会调用自身来继续查找，直到找到目标节点或到达树的末端。
迭代方法使用循环来进行查找，直到找到目标节点或遍历完整棵树。

示例代码（C++）
下面是一个使用 C++ 实现的二叉搜索树查找操作的示例代码，包括递归和迭代两种方式：

#include <iostream>

class TreeNode {
public:
    int key;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int val) : key(val), left(nullptr), right(nullptr) {}
};

class BinarySearchTree {
public:
    BinarySearchTree() : root(nullptr) {}
    
    void insert(int key) {
        TreeNode* newNode = new TreeNode(key);
        
        if (root == nullptr) {
            root = newNode;
            return;
        }
        
        TreeNode* current = root;
        TreeNode* parent = nullptr;
        
        while (true) {
            parent = current;
            if (key < current->key) {
                current = current->left;
                if (current == nullptr) {
                    parent->left = newNode;
                    return;
                }
            } else {
                current = current->right;
                if (current == nullptr) {
                    parent->right = newNode;
                    return;
                }
            }
        }
    }

    TreeNode* search(int key) {
        return searchRec(root, key);
    }
    
    TreeNode* searchIter(int key) {
        TreeNode* current = root;
        while (current != nullptr) {
            if (key == current->key) {
                return current;
            } else if (key < current->key) {
                current = current->left;
            } else {
                current = current->right;
            }
        }
        return nullptr; // Node not found
    }

private:
    TreeNode* root;

    TreeNode* searchRec(TreeNode* node, int key) {
        if (node == nullptr || node->key == key) {
            return node;
        }
        
        if (key < node->key) {
            return searchRec(node->left, key);
        } else {
            return searchRec(node->right, key);
        }
    }
};

int main() {
    BinarySearchTree bst;
    
    bst.insert(50);
    bst.insert(30);
    bst.insert(20);
    bst.insert(40);
    bst.insert(70);
    bst.insert(60);
    bst.insert(80);
    
    int keyToSearch = 40;
    
    // Using recursive search
    TreeNode* resultRec = bst.search(keyToSearch);
    if (resultRec != nullptr) {
        std::cout << "Found " << keyToSearch << " using recursive search." << std::endl;
    } else {
        std::cout << "Did not find " << keyToSearch << " using recursive search." << std::endl;
    }
    
    // Using iterative search
    TreeNode* resultIter = bst.searchIter(keyToSearch);
    if (resultIter != nullptr) {
        std::cout << "Found " << keyToSearch << " using iterative search." << std::endl;
    } else {
        std::cout << "Did not find " << keyToSearch << " using iterative search." << std::endl;
    }
    
    return 0;
}

关键点

递归查找：

searchRec 函数递归地在左子树或右子树中查找，直到找到目标节点或到达树的末端。

迭代查找：

searchIter 函数使用循环来查找目标节点，直到找到目标节点或遍历完整棵树。

二叉搜索树的删除

在二叉搜索树（BST）中，删除节点是一个涉及多种情况的操作。我们可以按照以下步骤进行删除：

删除节点的步骤
找到要删除的节点：首先，我们需要找到树中要删除的节点。这个过程类似于查找节点。

处理删除节点的不同情况：

情况 1：要删除的节点没有子节点（即叶节点）直接删除这个节点。

情况 2：要删除的节点只有一个子节点替换节点用其唯一的子节点，然后删除原来的节点。

情况 3：要删除的节点有两个子节点找到该节点的右子树中最小的节点（即“后继节点”），将这个后继节点的值替换到要删除的节点，然后删除后继节点。

C++ 代码实现
下面是一个基于 C++ 的示例代码，展示了如何在二叉搜索树中删除节点。

#include <iostream>
using namespace std;

// 定义树节点结构
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 找到树中最小的节点
TreeNode* findMin(TreeNode* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

// 删除节点
TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == NULL) return NULL;

    // 查找要删除的节点
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        // 处理节点的不同情况

        // 情况 1: 节点没有子节点
        if (root->left == NULL && root->right == NULL) {
            delete root;
            return NULL;
        }

        // 情况 2: 节点只有一个子节点
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        }
        if (root->right == NULL) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }

        // 情况 3: 节点有两个子节点
        TreeNode* temp = findMin(root->right); // 找到右子树中的最小节点
        root->val = temp->val; // 替换值
        root->right = deleteNode(root->right, temp->val); // 删除替换值的节点
    }
    return root;
}

// 中序遍历
void inorder(TreeNode* root) {
    if (root == NULL) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

int main() {
    // 创建一个简单的二叉搜索树
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(7);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(8);

    cout << "Original BST (Inorder Traversal): ";
    inorder(root);
    cout << endl;

    // 删除节点
    root = deleteNode(root, 7);

    cout << "BST after deleting 7 (Inorder Traversal): ";
    inorder(root);
    cout << endl;

    return 0;
}

代码解释
findMin：这是一个辅助函数，用于找到以指定节点为根的子树中的最小值节点。

deleteNode：这是删除节点的主函数。它递归地查找节点并处理不同的删除情况。

inorder：这是一个中序遍历函数，用于展示树的内容，方便验证删除操作是否正确。

main：在 main 函数中，创建了一个简单的 BST，并展示了删除节点后的结果。

key/value版本中二叉搜索树的实现（模板类）

#include<iostream>
#include<vector>
#include <string>
using namespace std;


template<class K, class V>
class BSTreeNode
{
public:
K _key;
V _value;
public:

BSTreeNode(K k, V v)
{
_key = k;
_value = v;
left = nullptr;
right = nullptr;
}

BSTreeNode* left;
BSTreeNode* right;
};



template<class K, class V>
class BSTree
{
typedef BSTreeNode<K, V> Node;
public:
bool Insert(const K& key, const V& value)
{
Node* pn = new Node(key, value);
if (_root == nullptr)
{
_root = pn;
}

Node* cur = _root;
while (cur)
{
if (cur->_key < pn->_key)
{
if (cur->right == nullptr)
{
cur->right = pn;
return true;
}
cur = cur->right;
}
else if (cur->_key > pn->_key)
{
if (cur->left == nullptr)
{
cur->left = pn;
return true;
}
cur = cur->left;
}
else
{
break;
}
}

return false;
}

Node* Find(const K& key)
{
Node* cur = _root;

while (cur)
{
if (cur->_key == key)
{
return cur;
}
else if (cur->_key < key)
{
cur = cur->right;
}
else
{
cur = cur->left;
}
}

return nullptr;
}

bool Erase(const K& key)
{
Node* cur = _root;
Node* par = _root;
while (cur)
{
if (cur->_key < key)
{
par = cur;
cur = cur->right;
}
else if (cur->_key > key)
{
par = cur;
cur = cur->left;
}
else
{
break;
}
}

if (cur == nullptr) return false;

if (cur->left == nullptr && cur->right == nullptr)
{
if (cur == par)
{
delete cur;
_root = nullptr;
return true;
}
if (par->left == cur)
{
par->left = nullptr;
}
else
{
par->right = nullptr;
}

delete cur;
}
else if (cur->left == nullptr && cur->right != nullptr)
{
if (par == cur)
{
_root = cur->right;
delete cur;
return true;
}

if (par->left == cur)
{
par->left = cur->right;
}
else
{
par->right = cur->right;
}

delete cur;
}
else if (cur->left != nullptr && cur->right == nullptr)
{
if (par == cur)
{
_root = cur->left;
delete cur;
return true;
}
if (par->left == cur)
{
par->left = cur->left;
}
else
{
par->right = cur->left;
}

delete cur;
}
else
{
Node* rminl = cur->right;
par = rminl;
while (rminl->left)
{
par = rminl;
rminl = rminl->left;
}

cur->_key = rminl->_key;

if (rminl == par)
{
cur->right = rminl->right;
delete rminl;
}
else
{
par->left = nullptr;
delete rminl;
}

}

return true;
}


void _InOrder(Node* root)
{
if (!root) return;

_InOrder(root->left);

cout << root->_key << " ";

_InOrder(root->right);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}

~BSTree()
{
Destroy(_root);
}
private:
Node* _root = nullptr;

void Destroy(Node* root)
{
if (root == nullptr)
{
return;
}

Destroy(root->left);
Destroy(root->right);

delete root;
}
};

原文地址：https://blog.csdn.net/qq_34434522/article/details/142307144

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：算法-K个一组翻转链表
下一篇：将相机深度图转接为点云的ROS2功能包

特权帐户安全 CyberArk
它隔离、控制和监控整个数据中心的所有特权活动，补充了CyberArk在市场领先的特权身份管理套件‌。‌CyberArk PTA（Privileged Threat Analytic）‌：特权威胁分析，
阅读更多2024-11-16
消息中间件分类
1. JMS（Java Message Service）：这是 Java 平台上的一套消息服务 API 标准，它定义了消息系统的基本功能，如消息的创建、发送、接收和读取等。5. 其他消息中间件：除了上
阅读更多2024-11-16
企业知识中台：构建智慧企业的核心
知识中台是企业数字化转型的重要一环，它能够帮助企业更有效地管理和利用知识资产，提升企业的竞争力。在选择搭建知识中台的工具时，HelpLook是一个值得考虑的选择。HelpLook以其直观易用的内容管理
阅读更多2024-11-16
如何恢復電腦IP地址的手動設置？
如何恢復電腦IP地址的手動設置。
阅读更多2024-11-16
OSPF动态路由配置(Cisco Packet Tracer)
OSPF路由协议通过向全网扩散本设备的链路状态信息，使网络中每台设备最终同步一个具有全网链路状态的数据库，然后路由器采用OSPF算法，以自己为根，计算到达其他网络的最短路径，最终形成全网路由信息。（4
阅读更多2024-11-16
HarmonyOS ArkTs 解决流式传输编码问题
使用 HarmonyOS ArkTs 解决流式传输中的编码和 JSON 解析问题。
阅读更多2024-11-16
每日论文20-24RFIC四核三模带自动模式跟踪输出缓冲器的VCO
每日论文20-24RFIC四核三模带自动模式跟踪输出缓冲器的VCO
阅读更多2024-11-16
PG数据库数据库时间字段开始时间和结束时间，判断和查询条件的开始和截止时间存在交集，SQL如何编写
假设你的表名是 events，开始时间字段为 start_time，结束时间字段为 end_time，而你要检查的时间段是 query_start_time 和 query_end_time。在 Po
阅读更多2024-11-16
cls(c基础)
作用清屏格式#include
阅读更多2024-11-16
see的本质是什么？
如果你喜欢看【龙虎斗】，看【猫蛇大战】相关的视频，你会发现，蛇的头会跟随性地转动，这不仅是因为蛇很紧张，更重要的，是因为蛇的眼睛的问题，蛇的眼睛对稍远一点的东西，其实是看不太清楚的，而且蛇的眼睛是没有
阅读更多2024-11-16

数据结构——二叉搜索树

二叉搜索树

二叉搜索树

⼆叉搜索树的概念

⼆叉搜索树的性能分析

二叉搜索树的插入

二叉搜索树的查找

二叉搜索树的删除

key/value版本中二叉搜索树的实现（模板类）

相关文章