备案控制台
探索云世界
开发者社区 开发与运维 文章 正文

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

2024-03-28 26
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 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++ kv模型
C++模型
C++二叉搜索树
是小宇吖
目录
相关文章
5i77ajz5u7ji6
|
2月前
|
缓存 并行计算 C++
实践教程｜旋转目标检测模型-TensorRT 部署(C++)
实践教程｜旋转目标检测模型-TensorRT 部署(C++)
5i77ajz5u7ji6
38 0
杭电码农-NEO
|
4天前
|
存储 搜索推荐 C++
【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构
【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构
杭电码农-NEO
18 1
快乐的流畅
|
1月前
|
存储 C++
【C++练级之路】【Lv.14】二叉搜索树（进化的二叉树——BST）
【C++练级之路】【Lv.14】二叉搜索树（进化的二叉树——BST）
快乐的流畅
31 0
【C++练级之路】【Lv.14】二叉搜索树（进化的二叉树——BST）
进击的小C
|
1月前
C++-你知道二叉搜索树吗？（循环版）
C++-你知道二叉搜索树吗？（循环版）
进击的小C
22 0
醋溜马桶圈
|
2月前
|
存储 编译器 C语言
【c++】类对象模型
【c++】类对象模型
醋溜马桶圈
21 2
【c++】类对象模型
godspeed_lucip
|
2月前
|
存储 C++
C++类与对象【对象模型和this指针】
C++类与对象【对象模型和this指针】
godspeed_lucip
18 0
godspeed_lucip
|
2月前
|
程序员 编译器 C++
C++核心编程一：内存分区模型（持续更新）
C++核心编程一：内存分区模型（持续更新）
godspeed_lucip
24 0
会飞翔的羊
|
2月前
|
设计模式 前端开发 安全
C++23种设计模式&软件设计模型
C++23种设计模式&软件设计模型
会飞翔的羊
53 0
Aries_Ro
|
3月前
|
Java C++
线程池-手写线程池C++11版本（生产者-消费者模型）
线程池-手写线程池C++11版本（生产者-消费者模型）
Aries_Ro
70 0
北海。
|
4月前
|
存储 安全 C++
C++【二叉搜索树】
C++【二叉搜索树】
北海。
40 0

热门文章

最新文章

  • 1
    从Proto到C++：探索Protocol Buffers的强大转换机制
  • 2
    【C/C++ 数据库 sqlite3】SQLite C语言API返回值深入解析
  • 3
    【C++ 职业方向】C++ 职业方向探索：工作职责、编程技能与MBTI人格匹配
  • 4
    拓扑排序解析：计算机与数学的交汇点以及C++ 实现
  • 5
    【C++ 可调用对象的应用】C++设计模式与现代编程技巧：深入可调用对象的世界
  • 6
    【C/C++ 性能优化】提高C++程序的缓存命中率以优化性能
  • 7
    【C++ 软件设计思路】学习C++中如何生成唯一标识符：从UUID到自定义规则
  • 8
    C++代码复用策略及与标准兼容性指南
  • 9
    【C++ 基本知识】现代C++内存管理：探究std::make_系列函数的力量
  • 10
    深入对比：Qt 的 QFile/QFileInfo 和与 C++17 Filesystem 和标准文件流 的细节剖析
  • 1
    【C++】—— c++11之智能指针
    45
  • 2
    【C++】—— C++11之线程库
    36
  • 3
    【C++】—— C++11之可变参数模板
    28
  • 4
    【C++】—— c++11新的类功能
    27
  • 5
    【C++】—— C++11新特性之 “右值引用和移动语义”
    30
  • 6
    【C++】—— c++11新特性之 lambda
    25
  • 7
    【C++】容器篇（五）—— map和set的基本介绍
    35
  • 8
    【C++】容器篇（四）—— queue的基本介绍以及模拟实现
    28
  • 9
    【C++】容器篇（三）—— stack的基本介绍及其模拟实现
    25
  • 10
    【C++】容器篇（二）——List的基本概述以及模拟实现
    31

    • 相关课程

    更多
  • C++ 入门教程开发文档
  • 【算法实战】10. 树回归算法

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）