详解二叉搜索树 --- key模型和key/value模型

这篇具有很好参考价值的文章主要介绍了详解二叉搜索树 --- key模型和key/value模型。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🍀作者阿润菜菜
📖专栏数据结构



一、认识二叉搜索树的key模型和key/value模型

  • key的模型是指每个节点只有一个键值,用于确定节点在树中的位置。节点的键值必须满足二叉搜索树的性质,即左子节点的键值小于父节点的键值,右子节点的键值大于父节点的键值。这种模型比较简单,但是不能存储额外的信息。
  • key/value模型是指每个节点有一个键值和一个数据值,键值用于确定节点在树中的位置,数据值用于存储节点的附加信息。节点的键值仍然必须满足二叉搜索树的性质,但是数据值可以是任意类型或对象。这种模型比较灵活,可以实现一些高级功能,比如映射或字典。

例如,如果我们要用二叉搜索树存储一些人的姓名和年龄,我们可以用key/value模型,把姓名作为键值,把年龄作为数据值。这样我们就可以根据姓名快速查找或插入一个人的信息。

在key/value模型中,我们需要定义一个内部类来表示节点,每个节点包含一个键值、一个数据值、一个左子链接和一个右子链接。我们还可以定义一个节点计数变量来记录以该节点为根的子树中的节点个数,这样可以方便地实现一些有序符号表的操作。

在key的模型中,我们只需要定义一个内部类来表示节点,每个节点包含一个键值、一个左子链接和一个右子链接。我们不需要定义一个数据值或一个节点计数变量。

本文以key模型进行讲解🌟 🌟 🌟

二、K结构的二叉搜索树实现

在二叉搜索树中,我们可以实现以下基本操作

  • 搜索:给定一个键值,在二叉搜索树中查找是否存在对应的节点。我们可以使用递归或迭代的方法来实现搜索。搜索算法基于二叉搜索树的性质:如果要查找的键值等于当前节点的键值,就返回当前节点;如果要查找的键值小于当前节点的键值,就在左子树中继续查找;如果要查找的键值大于当前节点的键值,就在右子树中继续查找;如果遇到空链接,就说明查找失败。
  • 插入:给定一个键值和一个数据值,在二叉搜索树中插入一个新的节点。我们也可以使用递归或迭代的方法来实现插入。插入算法基于二叉搜索树的性质:如果要插入的键值等于当前节点的键值,就更新当前节点的数据值;如果要插入的键值小于当前节点的键值,就在左子树中继续插入,并将返回的新的左子树赋给当前节点的左子链接;如果要插入的键值大于当前节点的键值,就在右子树中继续插入,并将返回的新的右子树赋给当前节点的右子链接;如果遇到空链接,就创建一个新的节点并返回它。
  • 删除:给定一个键值,在二叉搜索树中删除对应的节点。删除算法比较复杂,因为我们需要考虑三种情况:
    • 如果要删除的节点是叶子节点,就直接删除它,并返回空。
    • 如果要删除的节点只有一个子节点,就用该子节点替换它,并删除原来的节点。
    • 如果要删除的节点有两个子节点,就找到它的中序后继(即右子树中最小的节点或者左子树最大),并交换它们的键值,然后递归(或者非递归法)地在左子树中删除该键值。

我们可以使用递归或迭代的方法来实现删除。递归方法基于二叉搜索树的性质:如果要删除的键值等于当前节点的键值,就按照上述三种情况处理;如果要删除的键值小于当前节点的键值,就在左子树中继续删除,并将返回的新的左子树赋给当前节点的左子链接;如果要删除的键值大于当前节点的键值,就在右子树中继续删除,并将返回的新的右子树赋给当前节点的右子链接;如果遇到空链接,就说明查找失败。

迭代方法基于循环和栈来实现。首先,我们使用一个循环来查找要删除的节点,并记录它的父节点和左右方向。然后,我们使用一个栈来存储从根节点到要删除的节点的路径。接着,我们按照上述三种情况处理要删除的节点,并更新它的父节点和左右方向。最后,我们使用一个循环来更新从根节点到要删除的节点的路径上所有节点的计数变量。

Erase() 函数

  • 首先,检查根节点是否为空,如果为空,直接返回空。
  • 然后,比较要删除的键值和根节点的键值,如果小于根节点的键值,就递归地在左子树中删除该键值,并将返回的新的左子树赋给根节点的左子指针;如果大于根节点的键值,就递归地在右子树中删除该键值,并将返回的新的右子树赋给根节点的右子指针。
  • 最后,如果要删除的键值和根节点的键值相等,就分三种情况处理
    • 如果根节点是叶子节点,就直接删除它,并返回空。
    • 如果根节点只有一个子节点,就用该子节点替换根节点,并删除原来的根节点。
    • 如果要删除的节点有两个子节点,就找到它的中序后继(即右子树中最小的节点或者左子树最大),并交换它们的键值,然后递归(或者非递归法)地在左子树中删除该键值。

这样,就可以保证删除一个节点后,二叉搜索树的性质仍然成立。

代码示例: 已加上注释

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;  //创建一个指针del指向要删除的节点
    //开始准备删除
    if (root->_right == nullptr) {  //如果要删除的节点没有右子节点
      root = root->_left;           //就用它的左子节点替换它
    } else if (root->_left == nullptr) {  //如果要删除的节点没有左子节点
      root = root->_right;                //就用它的右子节点替换它
    } else {                        //如果要删除的节点有两个子节点
      Node* maxleft = root->_left;  //创建一个指针maxleft指向它的左子树
      while (maxleft->_right) {  //找到左子树中最右边的节点,即中序后继
        maxleft = maxleft->_right;
      }
      swap(root->_key, maxleft->_key);  //交换要删除的节点和中序后继的键值
      return _EraseR(root->_left, key);  //递归地在左子树中删除该键值
    }

    delete del;  //释放要删除的节点的内存空间

    return true;
  }
}

同时还有非递归方法: 直接看代码和注释

 bool Erase(const K& key) {
  Node* parent = nullptr;
  Node* cur = _root;

  while (cur) {
    if (cur->_key < key) {
      parent = cur;
      cur = cur->_right;
    } else if (cur->_key > key) {
      parent = cur;
      cur = cur->_left;
    } else {
      // 1、左为空
      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;  // 释放当前节点的内存
      }
      // 2、右为空
      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;  // 释放当前节点的内存
      }
      // 3、左右都不为空
      else  // 如果要删除的节点有两个子节点
      {
        // 找右树最小节点替代,也可以是左树最大节点替代
        Node* pminRight =
            cur;  // 定义一个指针指向当前节点,用来记录后继节点的父节点
        Node* minRight =
            cur->_right;  // 定义一个指针指向当前节点的右子树,用来寻找后继节点
        while (
            minRight->_left)  // 循环找到右子树中最小的节点,也就是最左边的节点
        {
          pminRight = minRight;        // 更新后继节点的父节点
          minRight = minRight->_left;  // 更新后继节点
        }

        cur->_key = minRight->_key;  // 将后继节点的值复制到当前节点

        if (pminRight->_left == minRight)  // 如果后继节点是它父节点的左孩子
        {
          pminRight->_left =
              minRight
                  ->_right;  // 将后继节点的父节点的左孩子改为后继节点的右子树
        } else  // 如果后继节点是它父节点的右孩子
        {
          pminRight->_right =
              minRight
                  ->_right;  // 将后继节点的父节点的右孩子改为后继节点的右子树
        }

        delete minRight;  // 释放后继节点的内存
      }

      return true;
    }
  }
  return false;
}

Find() 函数

搜索:给定一个键值,在二叉搜索树中查找是否存在对应的节点。我们可以使用递归或迭代的方法来实现搜索。
搜索算法基于二叉搜索树的性质:

  1. 如果要查找的键值等于当前节点的键值,就返回当前节点;
  2. 如果要查找的键值小于当前节点的键值,就在左子树中继续查找;
  3. 如果要查找的键值大于当前节点的键值,就在右子树中继续查找;如果遇到空链接,就说明查找失败。

循环:

        //查找
            bool 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 true;
                    }
                }
                return false;
            }

递归:

bool _FindR(Node* root, const K& key)
         {
             if (root == nullptr)
                 return false;

             if (root->_key == key)
                 return true;

             if (root->_key < key)
             {
                 return FindR(root->_right);
             }
             else
             {
                 return FindR(root->_left);
             }
         }

Insert() 函数

插入:给定一个键值和一个数据值,在二叉搜索树中插入一个新的节点。我们也可以使用递归或迭代的方法来实现插入。
插入算法基于二叉搜索树的性质:

  1. 如果要插入的键值等于当前节点的键值,就更新当前节点的数据值;
  2. 如果要插入的键值小于当前节点的键值,就在左子树中继续插入,并将返回的新的左子树赋给当前节点的左子链接;
  3. 如果要插入的键值大于当前节点的键值,就在右子树中继续插入,并将返回的新的右子树赋给当前节点的右子链接;如果遇到空链接,就创建一个新的节点并返回它。

循环:


// 插入一个键值为key的节点到二叉搜索树中
bool Insert(const K& key) {
  // 如果根节点为空,直接创建一个新节点作为根节点
  if (_root == nullptr) {
    _root = new Node(key);
    return true;
  }

  // 定义一个父节点指针和一个当前节点指针,从根节点开始遍历
  Node* parent = nullptr;
  Node* cur = _root;
  while (cur) {
    // 如果当前节点的键值小于要插入的键值,向右子树查找,并更新父节点
    if (cur->_key < key) {
      parent = cur;
      cur = cur->_right;
    }
    // 如果当前节点的键值大于要插入的键值,向左子树查找,并更新父节点
    else if (cur->_key > key) {
      parent = cur;
      cur = cur->_left;
    }
    // 如果当前节点的键值等于要插入的键值,说明已经存在,返回false
    else {
      return false;
    }
  }

  // 创建一个新节点,键值为key
  cur = new Node(key);
  // 根据父节点的键值判断新节点是左孩子还是右孩子,并链接
  if (parent->_key < key) {
    parent->_right = cur;
  } else {
    parent->_left = cur;
  }

  // 返回true表示插入成功
  return true;
}

递归方式:

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

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

copy( ) 函数

这个复制函数是属于先复制后链接的方法。它的思想是先创建一个新的节点,然后再递归地复制它的左右子树,并将它们链接到新节点上。这样,每个节点都会被复制一次,并且保持了原始树的结构和顺序。你可以这样理解:

  • 假设原始树是这样的:
    A
   / \
  B   C
 / \ / \
D  E F  G
  • 那么复制函数会先创建一个新的节点A’,然后递归地复制A的左子树和右子树,并将它们链接到A’上,得到这样的树:
    A'
   / \
  B'  C'
 / \ / \
D' E'F' G'
  • 其中,每个节点都是原始树对应节点的副本,例如B’是B的副本,C’是C的副本,以此类推。

代码:

  Node* copy(Node* root) //先复制后链接
         {
             if (root == nullptr)
             {
                 return nullptr;
             }

             Node* newRoot = new Node(root->_key);
             newRoot->_left = copy(root->_left);
             newRoot->_right = copy(root->_right);

             return newRoot;
         }

整体代码

贴上码云仓库的连接:二叉搜索树K模型实现

另一个知识点:
例如查找给定的键是否存在于二叉搜索树中,调用私有的_FindR函数。这种方式是为了把_root作为参数传递给私有函数,这样私有函数就可以递归地操作二叉搜索树的节点。如果不这样做,私有函数就无法访问_root,因为它是一个私有的成员变量。

三、 二叉搜索树的性能分析

二叉搜索树的性能分析主要取决于树的高度,即从根节点到最深的叶子节点的层数。树的高度决定了每次操作需要访问的节点个数,因为每次操作都是沿着树的路径进行的。

二叉搜索树的高度又取决于树的形状,即节点在树中的分布。树的形状又取决于插入节点的顺序。如果插入节点的顺序是随机的,那么二叉搜索树会趋向于平衡,即左右子树的高度相差不大。如果插入节点的顺序是有序的,那么二叉搜索树会退化为链表,即只有一条单边路径。

我们可以用以下公式来估计二叉搜索树操作的平均时间复杂度:

  • 如果插入节点是随机顺序的,那么二叉搜索树的高度约为 ,其中 为节点个数,为自然对数底。因此,每次操作需要比较约 次键值。
  • 如果插入节点是有序顺序的,那么二叉搜索树的高度约为 ,其中 为节点个数。因此,每次操作需要比较约 次键值。

对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数,即结点越深,则比较次数越多。
但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:
详解二叉搜索树 --- key模型和key/value模型
可以看出,随机顺序插入节点可以使二叉搜索树保持较低的高度,从而提高操作效率。

最优情况下,二叉搜索树为完全二叉树(或者接近完全二叉树),其平均比较次数为: l o g 2 N log_2 N log2N
最差情况下,二叉搜索树退化为单支树(或者类似单支),其平均比较次数为: N 2 \frac{N}{2} 2N

**问题:**如果退化成单支树,二叉搜索树的性能就失去了。那能否进行改进,不论按照什么次序插
入关键码,二叉搜索树的性能都能达到最优?后续介绍平衡二叉搜索树 — AVL树和红黑树。

详解二叉搜索树 --- key模型和key/value模型文章来源地址https://www.toymoban.com/news/detail-428238.html

到了这里,关于详解二叉搜索树 --- key模型和key/value模型的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++要笑着学】搜索二叉树 (SBTree) | K 模型 | KV 模型

      🔥 订阅量破千的火热 C++ 教程 👉 火速订阅 《C++要笑着学》   🔥 CSDN 累计订阅量破千的火爆 C/C++ 教程的 2023 重制版,C 语言入门到实践的精品级趣味教程。 了解更多: 👉  \\\"不太正经\\\" 的专栏介绍  ← 试读第一章 订阅链接: 🔗 《C语言趣味教程》 ← 猛戳订阅! 💭

    2023年04月13日
    浏览(53)
  • js遍历对象key,value

    方法一:转化为操作数组forEach遍历 遍历对象属性 关于Object.keys()方法 Object.keys() 方法会返回一个由一个给定对象的自身可枚举属性组成的数组,数组中属性名的排列顺序和正常循环遍历该对象时返回的顺序一致。 例子 遍历对象属性值 关于Object.values()方法 object .values()静态方

    2024年02月11日
    浏览(43)
  • python基础之字典{key:value}

    一、什么是字典 字典是可以存储键值对( key=value 对用冒号 )的容器。每一个键与一个值相关联,键和值之间用冒号分隔,而键-值对之间用逗号分隔,一个字典可以存储多个键值对 实例:存储一个键值对的字段,key=name,value=linda 二、字典的查询、添加、修改、删除 1、查

    2024年02月09日
    浏览(37)
  • Map按单个或多个Value排序,当Value相同时按Key排序

    Map可以先按照value进行排序,然后按照key进行排序。 或者先按照key进行排序,然后按照value进行排序,这都是可以的。 并且,大家可以制定自己的排序规则。 按单个value排序: 按多个value排序: 下面的代码中,首先按照value的数值从大到小进行排序,当value数值大小相同时,

    2024年02月15日
    浏览(59)
  • Python之字典一个key对应多个value

    python的字典是一个key对应一个value,如果想要一个key对应多个value,那么可以用以下几种方法来实现。 输出结果如下: 输出结果如下: 输出结果如下: defaultdict是Python内建dict类的一个子类,其使用一个factory_function作为输入,这个factory_function可以是list、set、str等等。 在实际

    2024年02月08日
    浏览(42)
  • js如何遍历对象的key和value

    在JavaScript中,可以使用for…in循环来遍历对象的键(key)和值(value)。以下是一个示例: 在这个例子中,for…in循环会遍历对象obj的所有键。然后,hasOwnProperty函数会检查这个键是否是对象obj自身的一个属性,而不是从其原型链继承的。如果是对象自己的属性,就输出这个键

    2024年02月10日
    浏览(43)
  • 深入篇【C++】手搓模拟实现二叉搜索树(递归/非递归版本)&&常见应用场景(K模型与KV模型)

    二叉搜索树又称二叉排序树,它或者是一颗空树或者是具有以下性质的二叉树: 1.当它的左子树不为空,则左子树上所有的结点的值都要小于根节点。 2.当它的右子树不为空,则右子树上所有的结点的值都要大于根结点。 3.它的左右子树都是二叉搜索树。 ①.定义结点 二叉树

    2024年02月12日
    浏览(40)
  • JavaScript 中遍历字典(对象)的键(key)和值(value)

    要在 JavaScript 中遍历字典(对象)的键(key)和值(value),可以使用 Object.entries() ​ 方法。这个方法会返回一个由键值对(key-value pairs)组成的数组,然后可以使用 for...of ​ 循环或数组的 forEach() ​ 方法遍历键值对。 以下是使用 for...of ​ 循环和 forEach() ​ 方法遍历字典

    2024年02月15日
    浏览(37)
  • JavaScript获取数组对象里面的键(key)和值(value)

    知识专栏 专栏链接 JavaScript知识专栏 https://blog.csdn.net/xsl_hr/category_12024214.html?spm=1001.2014.3001.5482 有关JavaScript的相关知识可以前往JavaScript知识专栏查看复习!! 在后台管理系统的项目开发中,对于 后端接口返回的数据进行处理 是一件很重要的事情。有时候返回的值是 json格式

    2023年04月15日
    浏览(40)
  • JS对Json数组进行抽取 获取key: “value“

    这篇文章 不是拿key或value 是 抽取需要的 key: “value” 【必须是单一数组 若是多组数据需要for循环】 // row 是json串 !!! 一、我有一个单一的json【row】 只要 id 和 appStatus 且分开成新数组 二、我有一个单一的json【row】 只要 id 和 appStatus 不分开在一起 方式1:row[0] 括号里面用数字

    2023年04月24日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包