首页 > 其他分享 >普通二叉搜索树剖析

普通二叉搜索树剖析

时间：2023-08-17 22:32:18浏览次数：39  
标签：Node right BST 二叉 剖析 搜索 key root left

二叉搜索树概述

二叉搜索树是一种具有特殊性质的二叉树。二叉搜索树可以是一棵空树，若不为空树，其：

  • 若左子树不为空，则左子树所有的节点值小于根节点值；
  • 若右子树不为空，则右子树所有的节点值大于根节点值。

与二叉树一样，二叉搜索树也是递归定义的，二叉搜索树的左右子树都是二叉搜索树。

二叉搜索树的结构

二叉搜索树的结构是一棵二叉树，其左子树的节点值都小于根节点值，右子树的节点值都大于根节点值。二叉搜索树使用链式结构进行实现。

普通二叉搜索树剖析_递归

两种二叉搜索树及定义

二叉搜索树常用有两种模型：Key模型和Key-Value模型。

Key模型的二叉搜索树的节点只需要存储一个关键码Key即可，可以将关键码理解为需要搜索的值。这种模型主要用于解决快速判断一个值在不在集合中的问题。

template<typename Key>
struct BinarySearchTreeNode
{
    typedef BinarySearchTreeNode<Key> BST_Node;

    BinarySearchTreeNode(const Key& val)
        :_left(nullptr),
    	_right(nullptr),
    	_val(val)
    { };

    BST_Node* _left;
    BST_Node* _right;
    Key _val; //只存储一个关键码
};

template<typename Key>
class BinarySearchTree	
{
private:		
    typedef BinarySearchTreeNode<Key> BST_Node;
    typedef BinarySearchTree<Key> Self;
    
    /*…………*/
 
private:
    BST_Node* _root; //维护根节点
};

Key-Value模型的二叉搜索树的节点除了要存储关键码Key之外，还需要存储对应的键值Value，即需要存储一个(Key, Value)的键值对。这种模型主要用于解决通过一个值找另外一个值的映射问题。

template<typename Key, typename Value>
struct BinarySearchTreeNode
{
    typedef BinarySearchTreeNode<Key, Value> BST_Node;

    BinarySearchTreeNode<Key, Value>(const Key& k, const Value& v)
      :_key(k), _val(v),
    _left(nullptr), _right(nullptr)
    { }

    Key _key;
    Value _val; //存储一个键值对
    BST_Node* _left;
    BST_Node* _right;
};

template<typename Key, typename Value>
class BinarySearchTree
{
private:
  typedef BinarySearchTreeNode<Key, Value> BST_Node;
  
  /*…………*/
 
private:
  	BST_Node* _root;
};

上述的两种模型，前者是STL set的基本实现思路，后者是STL map的基本实现思路，二者的Key值都具有互异性，不允许重复。

二叉搜索树的接口实现

作为一种具有特殊性质的二叉树，二叉搜索树的接口大体上有两种实现方式：迭代方式实现和递归方式实现。下面的实现以Key-Value模型为例，Key模型与此类似。

迭代方式实现

template<typename Key, typename Value>
struct BinarySearchTreeNode
{
  typedef BinarySearchTreeNode<Key, Value> BST_Node;
  
  BinarySearchTreeNode<Key, Value>(const Key& k, const Value& v)
    :_key(k), _val(v),
 		 _left(nullptr), _right(nullptr)
  { }

  Key _key;
  Value _val;
  //存储一个键值对
  BST_Node* _left;
  BST_Node* _right;
};

template<typename Key, typename Value>
class BinarySearchTree
{
  private:
  typedef BinarySearchTreeNode<Key, Value> BST_Node;
  typedef BinarySearchTree<Key, Value> Self;

public:
  BinarySearchTree()
    :_root(nullptr)
    { }

  BinarySearchTree(const Self& BSTree)
  {
    //递归进行拷贝构造
    _root = _copyConstruct(BSTree);
  }

  ~BinarySearchTree()
  {
    Destroy(_root); //递归销毁二叉树
  }
  //现代写法的赋值重载
  Self& operator=(Self BSTree) const
  {
    std::swap(_root, BSTree._root);
    return *this;
  }

  bool Insert(const Key& key, const Value& val)
  {
    //树为空的情况单独处理
    if (Empty()) {
      _root = new BST_Node(key, val);
    }
    BST_Node* cur = _root;
    BST_Node* parent = nullptr;
    //寻找合适的插入位置
    while (cur)
    {
      if (key < cur->_key) {
        parent = cur;
        cur = cur->_left;
      }
      else if (key > cur->_key) {
        parent = cur;
        cur = cur->_right;
      }
      else {
        return false;
      }
    }
    BST_Node* newNode = new BST_Node(key, val);
    //插入新节点
    //由于不能判断此时cur相对于parent的位置，所以需要再次判断
    if (key < parent->_key) {
      parent->_left = newNode;
    }
    else {
      parent->_right = newNode;
    }
    return true;
  }

  bool Erase(const Key& key)
  {
    BST_Node* pos = _root;
    BST_Node* parent = nullptr;
    //寻找目标节点
    while (pos)
    {
      if (key < pos->_key) {
        parent = pos;
        pos = pos->_left;
      }
      else if (key > pos->_key) {
        parent = pos;
        pos = pos->_right;
      } //找到目标节点
      else
      {
        /*
						 删除节点分三种情况：
						 1.需要删除的节点的子树数量为 0
						 2.需要删除的节点的子树数量为 1
						 3.需要删除的节点的子树数量为 2
						 对于前两种情况，将子树移交给目标节点的父节点；
						 对于第三种情况，寻找合适的临时节点替代目标节点，并删除临时节点
						*/
        if (pos->_left == nullptr)
        {
          //目标位置为根节点的情况需要独自处理
          if (pos == _root) {
            _root = pos->_right;
          }
          else
          {
            if (pos == parent->_left) {
              parent->_left = pos->_right;
            }
            else {
              parent->_right = pos->_right;
            }
          }
        }
        else if (pos->_right == nullptr)
        {
          if (pos == _root) {
            _root = pos->_left;
          }
          else
          {
            if (pos == parent->_left) {
              parent->_left = pos->_left;
            }
            else {
              parent->_right = pos->_left;
            }
          }
        }
        else
        {
          BST_Node* cur = pos->_left;
          BST_Node* parent = cur;
          //寻找目标节点的左子树的最右节点，以此节点作为临时节点
          while (cur->_right) {
            parent = cur;
            cur = cur->_right;
          }
          //交换节点的键值对以进行替换
          std::swap(cur->_key, pos->_key);
          std::swap(cur->_val, pos->_val);
          //删除临时节点
          //此处依然需要进行一次判断，因为不确定临时节点的位置
          //临时虽然是左子树的最右节点，但是并非一定是其父节点的右孩子
          if (cur->_left == nullptr)
          {
            if (cur == parent->_left) {
              parent->_left = cur->_right;
            }
            else {
              parent->_right = cur->_right;
            }
          }
          else
          {
            if (cur == parent->_left) {
              parent->_left = cur->_left;
            }
            else {
              parent->_right = cur->_left;
            }
          }
        }
        return true;
      }
    }
    return false;
  }

  BST_Node* Find(const Key& key) const
  {
    BST_Node* cur = _root;
    //根据二叉搜索树的性质进行搜索
    while (cur)
    {
      if (key < cur->_key) {
        cur = cur->_left;
      }
      else if (key > cur->_key) {
        cur = cur->_right;
      }
      else {
        return cur;
      }
    }
    return nullptr;
  }

  bool Empty() const
  {
    return _root == nullptr;
  }

  void InOrder() const
  {
    _InOrder(_root);
  }

  private:
  BST_Node* _copyConstruct(BST_Node* BSTreeRoot)
  {
    if (BSTreeRoot == nullptr) {
      return nullptr;
    }

    BST_Node* root = new BST_Node(BSTreeRoot->_key, BSTreeRoot->_val);
    root->_left = _copyConstruct(BSTreeRoot->_left);
    root->_right = _copyConstruct(BSTreeRoot->_right);

    return root;
  }

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

    Destroy(root->_left);
    Destroy(root->_right);
    delete root;
    root = nullptr;
  }
  
  void _InOrder(const BST_Node* root) const
  {
    if (root == nullptr) {
      return;
    }
    _InOrder(root->_left);
    cout << root->_val << ' ';
    _InOrder(root->_right);
  }

  private:
  BST_Node* _root;
};

递归方式实现

template<typename Key, typename Value>
struct BinarySearchTreeNode
{
  typedef BinarySearchTreeNode<Key, Value> BST_Node;

  BinarySearchTreeNode<Key, Value>(const Key& k, const Value& v)
    :_key(k), _val(v),
  _left(nullptr), _right(nullptr)
  { }

  Key _key;
  Value _val;
  BST_Node* _left;
  BST_Node* _right;
};

template<typename Key, typename Value>
class BinarySearchTree
{
  private:
  typedef BinarySearchTreeNode<Key, Value> BST_Node;

public:
  BinarySearchTree()
    :_root(nullptr)
    { }

    ~BinarySearchTree()
    {
      Destroy(_root);
    }
		//下面的接口都在子函数中进行递归调用
    bool Insert(const Key& key, const Value& val)
    {
      return _insert(key, val, _root);
    }

    bool Erase(const Key& key)
    {
      return _erase(key, _root);
    }

    BST_Node* Find(const Key& key) const
    {
      return _find(key, _root);
    }

    bool Empty() const
    {
      return _root == nullptr;
    }

    void InOrder() const
    {
      _InOrder(_root);
    }

private:
  //使用root指针的引用，使root与上层栈帧的指针保持关联，便于节点的链接
  bool _erase(const Key& key, BST_Node*& root)
  {
    if (root == nullptr) {
      return false;
    }

    if (key < root->_key) {
      return _erase(key, root->_left);
    }
    else if (key > root->_key) {
      return _erase(key, root->_right);
    }
    else
    {
      BST_Node* delNode = root;
      if (root->_left == nullptr) {
        root = root->_right;
        delete delNode;
      }
      else if (root->_right == nullptr) {
        root = root->_left;
        delete delNode;
      }
      else
      {
        //寻找左子树的最大节点
        BST_Node* leftMax = root->_left;
        while(leftMax->_right) {
          leftMax = leftMax->_right;
        }
        std::swap(leftMax->_key, root->_key);
        std::swap(leftMax->_val, root->_val);

        //此处可以直接递归删除关键码为key临时节点
        return _erase(key, root->_left);
      }
      return true;
    }
  }

  //使用root指针的引用，使root与上层栈帧的指针保持关联，便于节点的链接
  bool _insert(const Key& key, const Value& val, BST_Node*& root)
  {
    if (root == nullptr)
    {
      root = new BST_Node(key, val);
      return true;
    }

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

  BST_Node* _find(const Key& key, BST_Node* root) const
  {
    if (root == nullptr || key == root->_key) {
      return root;
    }
    //任意子树找到即返回
    BST_Node* ret_left = _find(key, root->_left);
    if (ret_left) {
      return ret_left;
    }
    BST_Node* ret_right = _find(key, root->_right);
    if (ret_right) {
      return ret_right;
    }
  }

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

    Destroy(root->_left);
    Destroy(root->_right);
    delete root;
    root = nullptr;
  }

  void _InOrder(const BST_Node* root) const
  {
    if (root == nullptr) {
      return;
    }
				_InOrder(root->_left);
				cout << root->_val << ' ';
				_InOrder(root->_right);
  }

  private:
  BST_Node* _root;
};

二叉搜索树实现细节

无论是迭代写法还是递归写法，二叉搜索树的erase()接口都相对麻烦，需要分三种情况进行考虑(如上面代码中的注释所述)。在转交子树和删除结点的过程中，要全面地考虑节点可能的分布情况，若一欲贪图方便就会产生意料不到的问题。例如删除具有两棵子树的节点，最后删除临时节点时依旧需要判断临时节点的位置。

标签：Node,right,BST,二叉,剖析,搜索,key,root,left
From： https://blog.51cto.com/158SHI/7128150

相关文章

  • 平衡二叉树
    110.平衡二叉树-力扣（LeetCode）确定思路如果左右子树都是平衡二叉树，并且左右子树的高度相差不超过1，那么就是平衡二叉树，如果左子树不是平衡二叉树也就不用对右子树进行递归了确定终止条件应该是遍历到叶子节点，因为叶子节点不能构成二叉树了，因为就没有再往下遍历的必要了——......
  • 剑指 Offer 07. 重建二叉树（中等）
    题目：classSolution{//本题思路：利用中序遍历，从前序遍历中找到左、右子树的根节点public:unordered_map<int,int>dic;//创建字典，映射当前根节点在中序遍历中的位置，以便于划分当前根节点的左右子树vector<int>preorder;//即下面的this->preorder......
  • [代码随想录]Day20-二叉树part09
    题目：669.修剪二叉搜索树思路：遍历到的值小于最小值，说明左子树里的所有节点都小于最小值，舍弃左子树。遍历到的值大于最大值，说明右子树里的所有节点都大于最大值，舍弃右子树。如果在范围内，就拼接左右子树然后返回节点代码：/***Definitionforabinarytreenode.*typeTr......
  • 基础算法之搜索与回溯算法C++
    1、组合的输出【题目描述】排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。现要求你用递归的方法输出所有组合。例如n＝5，r＝3，所有组合为：12312412513413514523......
  • ubuntu 下 GCC/G++ 的 include 搜索路径查看与设置
    https://blog.csdn.net/quicmous/article/details/106790319 一、如何查看include搜索路径输入如下命令：>echo'main(){}'|gcc-E-v-1显示结果如下：Usingbuilt-inspecs.COLLECT_GCC=gccOFFLOAD_TARGET_NAMES=nvptx-noneOFFLOAD_TARGET_DEFAULT=1Target:x86_64-linux-gn......
  • 力扣-搜索插入元素
    给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(logn) 的算法。 示例1:输入:nums=[1,3,5,6],target=5输出:2示例 2:输入:nums=[1,3,5,6],target=2输出:1示......
  • 代码随想录算法训练营第十八天| 513.找树左下角的值 112. 路径总和 106.从中序与
     找树左下角的值     卡哥建议：本地递归偏难，反而迭代简单属于模板题， 两种方法掌握一下   题目链接/文章讲解/视频讲解：https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html   做题思路：   题目说......
  • 代码随想录算法训练营第十七天| 110.平衡二叉树 257. 二叉树的所有路径 404.左叶子
     卡哥建议：迭代法，大家可以直接过，二刷有精力的时候 再去掌握迭代法。  110.平衡二叉树 （优先掌握递归）   卡哥建议：再一次涉及到，什么是高度，什么是深度，可以巩固一下。   题目链接/文章讲解/视频讲解：https://programmercarl.com/0110.%E5%B9%B3%E8%A1%A1%E4%BA%8C%......
  • 济南 CSP-J 刷题营 Day2 搜索
    SolutionT1排列计数原题链接4077:排列计数简要思路直接用next_permutation枚举全排列计算答案即可。完整代码#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;intn,k;inta[100];intans;//可能的答案数量signedmain(){......
  • 【剑指Offer】58、对称的二叉树
    【剑指Offer】58、对称的二叉树题目描述：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。解题思路：本题判断一棵树是不是对称的，和第18题可以对比分析：二叉树的镜像，和LeetCode第101题：101.对称二叉树是同一道题。解......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99