AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

C++：二叉搜索树模拟实现（KV模型）

2024-03-28 58
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： C++：二叉搜索树模拟实现（KV模型）

前言

 二叉搜索树又称二叉排序树,他对数据有严格的要求，具体表现在以下几个方面：

  1. 如果一个根节点的左子树不为空，则左子树中所有节点的值都必须小于根节点的值；如果它的右子树不为空，则右子树中所有节点的值都必须大于根节点的值。
  2. 它的左右子树也都必须是一个二叉搜索树，也都必须满足第一条。
  3. 二叉搜索树中的每个节点都是唯一的，不允许重复！！！

二叉搜索树的实际应用主要分为K模型和KV模型。


  1. K模型：即Key作为关键码，二叉搜索树中只存储Key一个数据。而关键码则是待搜索的值。比如：我们经常通过软件查找是否存在某个单词，是否拼写正确。
  2. KV模型：存储的数据中，每个Key对应一个Value,即键值对<Key, Value>。 我们经常通过Key去查找对应的Val.比如:我们通过英文来查找对应的中文,就是一个最常见的KV场景。

模拟实现KV模型

1. 节点封装

由于是KV模型,我们需要存储Key和Value俩个值。同时二叉搜索树也是二叉树,我们需要它的左右节点。因此节点疯转如下:

template<class K, class V>
struct BSTreeNode
{
  K _key;
  V _value;
  BSTreeNode<K, V>* _left;
  BSTreeNode<K, V>* _right;

  //默认构造函数, 用于后续new创建节点
  BSTreeNode(const K& key, const V& value)
    :_key(key)
    , _value(value)
    , _right(nullptr)
    , _left(nullptr)
  {}
};

2、前置工作（默认构造、拷贝构造、赋值重载、析构函数等）

接下来是KV模型封装的框架，以及默认构造、拷贝构造、赋值重载、析构函数。比较简单，就直接给出代码了哈。

template<class K, class V>
  class BSTree
  {
    typedef BSTreeNode<K, V> Node;//节点重命名
  public:
    //默认构造
    BSTree()
      :_root(nullptr)
    {}

    //拷贝构造
    BSTree(BSTree<K, V>& t)
    {
      _root = Copy(t._root);
    }

    //赋值重载
    BSTree<K, V>& operator=(BSTree<K, V> t)
    {
      swap(_root, t._root);
      return *this;
    }

    //析构函数
    ~BSTree()
    {
      Destory(_root);
    }
  private:
    Node* _root = nullptr;
  };
}

2. 数据插入（递归和非递归版本）

首先我们需要查找数据待插入的位置(为了保证插入数据后整体依然是一颗二叉搜索树).。同时查找插入位置时，只有key是有严格要求的，Value只是附带。

即：如果根节点为空，即是待插入数据位置；否则开始查找，如果待插入数据大于根节点往右子树节点走；如果待插入数据小于根节点往左子树节点走。不断循环，直到查找到空节点时，即为数据待插入的位置；如果查找到的大小和待插入数据值相等则返回false（确保二叉搜索树中的每个节点唯一）

【非递归版本】：

bool Insert(const K& key, const V& value)
{
  if (_root == nullptr)//根节点为空
  {
    _root = new Node(key, value);
    return true;
  }

  Node* cur = _root;
  Node* parent = nullptr;//后续插入数据链接时，需要和父节点相连
  while (cur)
  {
    if (cur->_key > key)//待插入数据小于当前节点，往左子树查找
    {
      parent = cur;
      cur = cur->_left;
    }
    else if(cur->_key < key)//待插入数据大于当前节点，往右子树查找
    {
      parent = cur;
      cur = cur->_right;
    }
    else//待插入数据等于当前节点，不允许插入
    {
      return false;
    }
  }

  //链接
  Node* newNode = new Node(key, value); 
  //链接时，我们无法确定插入节点时在父节点的左边还是右边，需要进一步比较
  if (parent->_key > key)
    parent->_left = newNode;
  else
    parent->_right = newNode;
  return true;
}

【递归版本】：

bool InsertR(const K& key, const V& value)
{
  //由于我们查找位置需要从根节点开始查找，所以这里通过另一个函数来传递实现
  return _InsertR(_root, key, value);
}
  
bool _InsertR(Node*& root, const K& key, const V& value)
{
  if (root == nullptr)
  {
    //注意上述我们形参都是引用，所以不用新增Parent节点
    root = new Node(key, value);
    return true;
  }

  if (root->_key > key)//待插入数据小于当前节点，往左子树查找
    return _InsertR(root->_left, key, value);
  else if (root->_key < key)//待插入数据大于当前节点，往右子树查找
    return _InsertR(root->_right, key, value);
  else
    return false;
}

3、数据删除（递归和非递归版本）

3.1 查找待删除节点位置

删除数据，我们首先需要和插入数据一样，先查找到待删除节点。和插入类似就不多说了。

【查找待删除数据】：

bool Erase(const K& key)
{
  if (_root == nullptr)//为空即不存在待删除数据
    return false;

  Node* cur = _root;
  Node* parent = nullptr;
  while (cur)
  {
    if (cur->_key > key)//待删除数据小于当前节点，往左子树查找
    {
      parent = cur;
      cur = cur->_left;
    }
    else if (cur->_key < key)//待删除数据大于当前节点，往右子树查找
    {
      parent = cur;
      cur = cur->_right;
    }
    else
    {
      //当前位置即为待删除节点，装备删除数据  
      
    }
  }
  return false;//整棵树中不存在待删除数据
}

3.2 删除数据及相关节点调整

插找到待删除数据后，显然如果只是简单将该节点删除，有可能将不满足二叉搜索树的要求，那怎么办呢？

删除数据分为以下三种情况：

  1. 左子树为空

左子树为空主要分为以下情形：右子树为空，左子树不为空；左右子树均为空（省略）。

 不管上述那种情况，我们发现只需将父节点的下一个节点指向待删除节点的右指针即可。但需要注意的是，如果待删除节点为根节点，它将没有父节点，需要单独处理。

【代码实现】：

if (cur->_left == nullptr)//左子树为空
{
  if (parent == _root)//cur为根节点
  {
    _root = cur->_right;
  }
  else
  {
    if (parent->_key > cur->_key)//待删除节点在父节点左子树中
    {
      parent->_left = cur->_right;
    }
    else//待删除节点在父节点右子树中
    {
      parent->_right = cur->_right;
    }
  }
  delete cur;
}
  1. 右子树为空

右子树为空分为单纯右子树为空和左右子树均为空（省）。具体处理方式和左子树为空类似就不多说了。

【代码实现】：

//左右子树均不为空，查找右子树最小元素进行交换后删除
if (parent == _root)//cur为根节点
{
    _root = cur->_left;
  }
  else
  {
    if (parent->_key > cur->_key)
    {
      parent->_left = cur->_left;
    }
    else
    {
      parent->_right = cur->_left;
    }
  }
  delete cur;
}
  1. 左右子树均不为空

这种情况我们可以查找左子树最大值或右子树最小值和待删除删除节点进行交换，交换后我们可以转化为上述两种子问题来删除数据。（接下来博主以交换右子树最小值为例）

Node* subLeft = cur->_right;
Node* parent = cur;
while (subLeft->_left)
{
  parent = cur;
  subLeft = subLeft->_left;
}
//交换
swap(cur->_key, subLeft->_key);
swap(cur->_value, subLeft->_value);
//删除
if (parent->_right = subLeft)
{
  parent->_right = subLeft->_right;
}
else
{
  parent->_left = subLeft->_right;
}
delete subLeft;

3.3 完整代码以及递归和非递归版本

递归思路和非递归差球不多，就不一一分析了，下面直接给出两种实现方式代码。

【非递归版本】：

bool Erase(const K& key)
{
  if (_root == nullptr)
    return false;

  Node* cur = _root;
  Node* parent = nullptr;
  while (cur)
  {
    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 (parent == _root)//cur为根节点
        {
          _root = cur->_right;
        }
        else
        {
          if (parent->_key > cur->_key)
          {
            parent->_left = cur->_right;
          }
          else
          {
            parent->_right = cur->_right;
          }
        }
        delete cur;
      }
      else if (cur->_right == nullptr)//右子树为空
      {
        if (parent == _root)//cur为根节点
        {
          _root = cur->_left;
        }
        else
        {
          if (parent->_key > cur->_key)
          {
            parent->_left = cur->_left;
          }
          else
          {
            parent->_right = cur->_left;
          }
        }
        delete cur;
      }
      else
      {//左右子树均不为空，查找右子树最小元素进行交换后删除
        Node* subLeft = cur->_right;
        Node* parent = cur;
        while (subLeft->_left)
        {
          parent = cur;
          subLeft = subLeft->_left;
        }
        //交换
        swap(cur->_key, subLeft->_key);
        swap(cur->_value, subLeft->_value);
        //删除
        if (parent->_right = subLeft)
        {
          parent->_right = subLeft->_right;
        }
        else
        {
          parent->_left = subLeft->_right;
        }
        delete subLeft;
      }
      return true;
    }
  }
  return false;
}

【递归版本】：

//删除：递归版本
bool EraseR(const K& key)
{
  return _EraseR(_root, key);//同理，由于需要根节点，在通过一层函数来实现
}
bool _EraseR(Node*& root, const K& key)
{
  if (root == nullptr)//非找到
    return false;
  if (root->_key > key)//转化成递归子问题，在左子树中删除key
    return _EraseR(root->_left, key);
  else if (root->_key < key)//转化成递归子问题，在右子树中删除key
    return _EraseR(root->_right, key);
  else
  {//删除数据
    if (root->_left == nullptr)
    {
      Node* del = root;
      root = root->_right;
      delete del;
      return true;
    }
    else if (_root->_right == nullptr)
    {
      Node* del = root;
      root = root->_left;
      delete del;
      return true;
    }
    else
    {
      Node* subLeft = root->_right;
      while (subLeft->_left)
      {
        subLeft = subLeft->_left;
      }
      //交换
      swap(root->_key, subLeft->_key);
      swap(root->_value, subLeft->_value);

      return _EraseR(root->_right, key); 
    }

  }
}

四、查找数据

【递归版本】：

//查找：递归版本
Node* FindR(const K& key)
{
  return _FindR(_root, key);
}
Node* _FindR(Node*& root, const K& key)
{
  if (root == nullptr)
    return nullptr;
  if (root->_key > key)
    return _FindR(root->_left, key);
  else if (root->_key < key)
    return _FindR(root->_right, key);
  else
    return root;
}

【非递归版本】：

//查找：非递归版本
Node* Find(const K& key)
{
  Node* cur = _root;
  while (cur)
  {
    if (cur->_key > key)
      cur = cur->_left;
    else if (cur->_key < key)
      cur = cur->_right;
    else
    {//找到了
      return cur;
    }
  }
  return nullptr;
}

五、中序遍历

//中序遍历
void Inorder()
{
  _Inorder(_root);
  cout << endl;
}

void _Inorder(Node* root)
{
  if (root == nullptr)
    return;
  _Inorder(root->_left);
  cout << root->_key << "->" << root->_value << " " << endl;
  _Inorder(root->_right);
}

六、所有代码

gitee：所有代码及测试代码

namespace KeyValue
{
  template<class K, class V>
  struct BSTreeNode
  {
    K _key;
    V _value;
    BSTreeNode<K, V>* _left;
    BSTreeNode<K, V>* _right;

    //默认构造函数
    BSTreeNode(const K& key, const V& value)
      :_key(key)
      , _value(value)
      , _right(nullptr)
      , _left(nullptr)
    {}
  };

  template<class K, class V>
  class BSTree
  {
    typedef BSTreeNode<K, V> Node;
  public:
//
    //默认构造
    BSTree()
      :_root(nullptr)
    {}

    //拷贝构造
    BSTree(BSTree<K, V>& t)
    {
      _root = Copy(t._root);
    }

    //赋值重载
    BSTree<K, V>& operator=(BSTree<K, V> t)
    {
      swap(_root, t._root);
      return *this;
    }

    //析构函数
    ~BSTree()
    {
      Destory(_root);
    }
//
    //插入， 非递归版本
    bool Insert(const K& key, const V& value)
    {
      if (_root == nullptr)
      {
        _root = new Node(key, value);
        return true;
      }

      Node* cur = _root;
      Node* parent = nullptr;
      while (cur)
      {
        if (cur->_key > key)
        {
          parent = cur;
          cur = cur->_left;
        }
        else if(cur->_key < key)
        {
          parent = cur;
          cur = cur->_right;
        }
        else
        {
          return false;
        }
      }

      //链接
      Node* newNode = new Node(key, value); 
      if (parent->_key > key)
        parent->_left = newNode;
      else
        parent->_right = newNode;
      return true;
    }

    // 插入: 递归遍布
    bool InsertR(const K& key, const V& value)
    {
      return _InsertR(_root, key, value);
    }
/
    //查找：非递归版本
    Node* Find(const K& key)
    {
      Node* cur = _root;
      while (cur)
      {
        if (cur->_key > key)
          cur = cur->_left;
        else if (cur->_key < key)
          cur = cur->_right;
        else
        {//找到了
          return cur;
        }
      }
      return nullptr;
    }

    //查找：递归版本
    Node* FindR(const K& key)
    {
      return _FindR(_root, key);
    }
/
    //删除：非递归版本
    bool Erase(const K& key)
    {
      if (_root == nullptr)
        return false;

      Node* cur = _root;
      Node* parent = nullptr;
      while (cur)
      {
        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 (parent == _root)//cur为根节点
            {
              _root = cur->_right;
            }
            else
            {
              if (parent->_key > cur->_key)
              {
                parent->_left = cur->_right;
              }
              else
              {
                parent->_right = cur->_right;
              }
            }
            delete cur;
          }
          else if (cur->_right == nullptr)//右子树为空
          {
            if (parent == _root)//cur为根节点
            {
              _root = cur->_left;
            }
            else
            {
              if (parent->_key > cur->_key)
              {
                parent->_left = cur->_left;
              }
              else
              {
                parent->_right = cur->_left;
              }
            }
            delete cur;
          }
          else
          {//左右子树均不为空，查找右子树最小元素进行交换后删除
            Node* subLeft = cur->_right;
            Node* parent = cur;
            while (subLeft->_left)
            {
              parent = cur;
              subLeft = subLeft->_left;
            }
            //交换
            swap(cur->_key, subLeft->_key);
            swap(cur->_value, subLeft->_value);
            //删除
            if (parent->_right = subLeft)
            {
              parent->_right = subLeft->_right;
            }
            else
            {
              parent->_left = subLeft->_right;
            }
            delete subLeft;
          }
          return true;
        }
      }
      return false;
    }

    //删除：递归版本
    bool EraseR(const K& key)
    {
      return _EraseR(_root, key);
    }
/
    //中序遍历
    void Inorder()
    {
      _Inorder(_root);
      cout << endl;
    }
    void _Inorder(Node* root)
    {
      if (root == nullptr)
        return;
      _Inorder(root->_left);
      cout << root->_key << "->" << root->_value << " " << endl;
      _Inorder(root->_right);
    }

  private:
    Node* Copy(Node*& root)
    {
      if (root == nullptr)
        return nullptr;
      Node* newRoot = new Node(root->_key, root->_value);
      newRoot->_left = Copy(root->_left);
      newRoot->_right = Copy(root->_right);
      return newRoot;
    }

    void Destory(Node*& root)
    {
      if (root == nullptr)
        return;
      Destory(root->_right);
      Destory(root->_left);
      delete root;
      root = 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
      {//删除数据
        if (root->_left == nullptr)
        {
          Node* del = root;
          root = root->_right;
          delete del;
          return true;
        }
        else if (_root->_right == nullptr)
        {
          Node* del = root;
          root = root->_left;
          delete del;
          return true;
        }
        else
        {
          Node* subLeft = root->_right;
          while (subLeft->_left)
          {
            subLeft = subLeft->_left;
          }
          //交换
          swap(root->_key, subLeft->_key);
          swap(root->_value, subLeft->_value);

          return _EraseR(root->_right, key); 
        }

      }
    }

    bool _InsertR(Node*& root, const K& key, const V& value)
    {
      if (root == nullptr)
      {
        root = new Node(key, value);
        return true;
      }

      if (root->_key > key)
        return _InsertR(root->_left, key, value);
      else if (root->_key < key)
        return _InsertR(root->_right, key, value);
      else
        return false;
    }

    Node* _FindR(Node*& root, const K& key)
    {
      if (root == nullptr)
        return nullptr;
      if (root->_key > key)
        return _FindR(root->_left, key);
      else if (root->_key < key)
        return _FindR(root->_right, key);
      else
        return root;
    }

    Node* _root = nullptr;
  };
}


文章标签：
C++
存储
关键词：
C++模型
C++二叉搜索树
C++ kv模型
C++二叉搜索树kv模型
是小宇吖
目录
相关文章
数据知道
|
3月前
|
程序员 编译器 C++
【C++核心】C++内存分区模型分析
这篇文章详细解释了C++程序执行时内存的四个区域：代码区、全局区、栈区和堆区，以及如何在这些区域中分配和释放内存。
数据知道
58 2
技术员阿伟
|
14天前
|
机器学习/深度学习 人工智能 自然语言处理
C++构建 GAN 模型：生成器与判别器平衡训练的关键秘籍
生成对抗网络（GAN）是AI领域的明星，尤其在C++中构建时，平衡生成器与判别器的训练尤为关键。本文探讨了GAN的基本架构、训练原理及平衡训练的重要性，提出了包括合理初始化、精心设计损失函数、动态调整学习率、引入正则化技术和监测训练过程在内的五大策略，旨在确保GAN模型在C++环境下的高效、稳定训练，以生成高质量的结果，推动AI技术的发展。
技术员阿伟
38 10
chian-ocean
|
21天前
|
存储 C++
【C++】二叉搜索树（BST）
二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，其每个节点的左子树所有节点值小于该节点值，右子树所有节点值大于该节点值，且左右子树也均为二叉搜索树。BST支持高效的数据查找、插入和删除操作，时间复杂度通常为O(log n)。本文档详细介绍了BST的基本概念、存储结构及其实现，包括迭代和递归两种方式的查找、插入、删除等操作的具体代码示例。
chian-ocean
29 3
呆呆宝
|
5月前
|
存储 数据格式 运维
开发与运维C++问题之更改数据模型为通用数据结构如何解决
开发与运维C++问题之更改数据模型为通用数据结构如何解决
呆呆宝
30 1
花开富贵111
|
5月前
|
编译器 程序员 调度
协程问题之C++20 的协程实现是基于哪种协程模型的
协程问题之C++20 的协程实现是基于哪种协程模型的
花开富贵111
41 1
დ旧言~
|
5月前
|
存储 C++
【C++】二叉树进阶之二叉搜索树（下）
【C++】二叉树进阶之二叉搜索树（下）
დ旧言~
35 4
დ旧言~
|
5月前
|
Java 编译器 C++
【C++】二叉树进阶之二叉搜索树（上）
【C++】二叉树进阶之二叉搜索树（上）
დ旧言~
39 3
Eternity._
|
5月前
|
算法 测试技术 C++
【C++高阶】掌握AVL树：构建与维护平衡二叉搜索树的艺术
【C++高阶】掌握AVL树：构建与维护平衡二叉搜索树的艺术
Eternity._
39 2
嘟嘟嘟嘟嘟嘟
|
5月前
|
机器学习/深度学习 PyTorch 算法框架/工具
C++多态崩溃问题之在PyTorch中，如何定义一个简单的线性回归模型
C++多态崩溃问题之在PyTorch中，如何定义一个简单的线性回归模型
嘟嘟嘟嘟嘟嘟
35 0
嘎嘎旺
|
6月前
|
C++
【c++】二叉搜索树
【c++】二叉搜索树
嘎嘎旺
36 0