【数据结构】二叉搜索树--BST，Binary Search Tree

2024-06-05 07:20
文章标签 数据结构 搜索 二叉 tree search binary bst

本文主要是介绍【数据结构】二叉搜索树--BST，Binary Search Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 二叉搜索树
    • 1. 二叉搜索树的概念
    • 2. 二叉搜索树的接口
      • 2.1 查找
        • 非递归查找
        • 递归查找
      • 2.2 中序遍历
      • 2.3 插入
        • 非递归插入
        • 递归插入
      • 2.4 删除
        • 非递归删除
        • 递归删除
    • 3. 二叉搜索树的应用
      • key搜索模型
      • kv搜索模型
    • 5. oj题

二叉搜索树

1. 二叉搜索树的概念

二叉搜索树又称二叉排序树，它可以是一颗空树，或者是一个满足如下性质的二叉树：

  • 如果左子树不为空，左子树上所有节点的值都小于根节点；
  • 如果右子树不为空，右子树上所有节点的值都大于根节点；

且它的左右子树，也满足上述性质。

举个栗子吧，以6为根节点的BST树结构：

template<class K>
struct bstree_node
{bstree_node<K>(K key): _left(nullptr), _right(nullptr), _key(key){}bstree_node<K>* _left;bstree_node<K>* _right;K _key;
};template<class K>
class bstree
{
public:typedef bstree_node<K> node;
private:node* _root = nullptr;
};

两个又相同数组构成的二叉树，但是却形成了两个不同树结构。二叉搜索树最大的问题是会退化，比如右单枝，顺序插入时就会退化成一个链表。

搜索二叉树的效率体现在搜索上，最坏情况搜索高度次。所以树的高度越低，性能越好。所以一般不会使用单纯的搜索二叉树，而是使用升级版的AVL 树（平衡二叉搜索树）和红黑树

大概了解一下
AVL 树（平衡二叉搜索树）：
AVL树
红黑树
在这里插入图片描述

 

2. 二叉搜索树的接口

2.1 查找

若根节点不为空：

  • 如果节点值等于 k e y key key，返回 t r u e true true，
  • 如果节点值小于 k e y key key，到其右子树中查找，
  • 如果节点值大于 k e y key key，到其左子树中查找，

走到空树还没找到，则返回 f a l s e false false。

非递归查找
bool find(const K& key)
{// 从根节点开始查找node* cur = _root;// 循环遍历树，直到当前节点为空（即没有找到）while (cur){// 如果查找的键值小于当前节点的键值if (key < cur->_key){// 移动到当前节点的左子节点，因为左子节点的键值更小cur = cur->_left;}// 如果查找的键值大于当前节点的键值else if (key > cur->_key){// 移动到当前节点的右子节点，因为右子节点的键值更大cur = cur->_right;}// 如果查找的键值等于当前节点的键值else{return true;}}return false;
}

二叉搜索树的查找非常的迅速，在二叉树相对平衡的情况下，时间复杂度高度次 O ( l o g N ) O(logN) O(logN)。最差是线性状态，为 O ( N ) O(N) O(N)。

递归查找

递归函数 find_r 会沿着树的结构向下搜索，每次比较 key 和当前节点的键值，决定向左或向右移动。这种递归调用会一直持续到找到匹配的键值或者遍历完整个树。

基本情况（终止条件）：
如果 root 是 nullptr，表示已经到达了树的末端，没有找到匹配的键值，因此返回 false。

递归调用：
如果 key 小于 root->_key，说明要查找的键值可能在左子树中，因此递归调用 _find_r(root->_left, key)。
如果 key 大于 root->_key，说明要查找的键值可能在右子树中，因此递归调用 _find_r(root->_right, key)。

找到匹配键值：
如果 key 等于 root->_key，表示找到了匹配的键值，立即返回 true。

bool find_r(const K& key)
{return _find_r(_root, key);
}bool _find_r(node* root, const K& key)
{if (root == nullptr)return false;if (key < root->_key)return _find_r(root->_left, key);else if (key > root->_key)return _find_r(root->_right, key);elsereturn true;
}

2.2 中序遍历

二叉搜索树的中序遍历结果，就是树中元素排成升序的结果。

void inorder()
{_inorder(_root);std::cout << std::endl;
}void _inorder(node* root)
{if (root == nullptr)return;_inorder(root->_left);std::cout << root->_key << " ";_inorder(root->_right);
}

一般成员函数在类外调用时，无法直接传入成员变量作参数。故可以将主体逻辑包装成子函数，再由成员函数去调用即可。

void TestBSTree() 
{BSTree<int> t;int a[] = { 7,1,3,6,4,8,7,9,3,2,5 }; //排序数组for (auto e : a) {t.Insert(e); //插入二叉搜索树}t.Inorder(); //中序遍历
}

如上代码，相当于利用二叉搜索树排序数组，而二叉搜索树结构天然具有排序加去重的功能。

2.3 插入

二叉搜索树的插入也很简单，共分两种情况：

  1. 树为空，则直接插入，
  2. 树不为空，则按性质查找到插入位置，再插入新节点。

cur指针进行比较并向下移动的同时，父指针parent始终指向cur的父节点。当cur走到空的时候，就创建新节点并链接到父节点的指针上。

  1. 插入的值比当前节点的值小，则插入到左子树中，
  2. 反之，比当前节点的值大，则插入到右子树中。
非递归插入

非递归插入方法通过迭代遍历二叉搜索树来找到新节点的插入位置。首先检查树是否为空，如果是，则直接将新节点设为根节点。如果树不为空，则从根节点开始，使用一个当前节点指针 cur 和一个父节点指针 parent 来跟踪遍历过程。在遍历过程中，根据新键值与当前节点键值的比较结果，决定向左子树还是右子树移动。如果新键值小于当前节点键值，则移动到左子节点；如果大于，则移动到右子节点。如果遇到相同键值的节点，则插入失败并返回 false。当 cur 为空时，表示已经到达了插入位置，此时根据新键值与 parent 节点键值的比较结果，在父节点的左或右子节点位置插入新节点。这种方法直观且易于理解，不需要额外的栈空间，适用于大多数情况下的树操作。

bool insert(const K& key)
{// 如果根节点为空，直接将新节点作为根节点if (_root == nullptr){_root = new node(key);return true;}node* cur = _root;node* parent = nullptr;// 循环找到合适的插入位置while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}elsereturn false; // 如果存在相同键值的节点，不插入}// 根据键值大小插入新节点if (key < parent->_key)parent->_left = new node(key);elseparent->_right = new node(key);return true;
}

可见，二叉搜索树的每次插入都是把节点放在叶节点的位置上。

递归插入

递归插入方法通过递归调用函数自身来遍历二叉搜索树，并找到新节点的插入位置。递归函数 _insert_r 接受当前节点指针的引用和要插入的键值作为参数。如果当前节点为空，表示到达了插入位置，此时创建一个新节点并将其赋值给当前节点指针，然后返回 true 表示插入成功。如果新键值小于当前节点键值，则递归调用函数在左子树中继续查找插入位置；如果新键值大于当前节点键值，则递归调用函数在右子树中查找。如果遇到相同键值的节点，则返回 false 表示插入失败。递归插入方法简洁优雅，代码量少，但可能会因为递归调用导致栈空间的使用增加，对于大型树结构可能存在性能问题。然而，对于小型或中型树结构，递归插入是一种高效且易于实现的方法。

bool insert_r(const K& key)
{return _insert_r(_root, key);
}bool _insert_r(node*& root, const K& key)
{// 如果当前节点为空，创建新节点并返回trueif (root == nullptr){root = new node(key);return true;}// 根据键值大小递归插入左子树或右子树if (key < root->_key)return _insert_r(root->_left, key);else if (key > root->_key)return _insert_r(root->_right, key);elsereturn false; // 如果存在相同键值的节点，不插入
}

参数类型是节点指针的引用，使得root不仅是节点指针，还是其父节点的左或右孩子指针，修改root也就修改了父节点的左右孩子。

2.4 删除

二叉搜索树的难点在于删除，因为节删除节点需要维护剩余节点的链接关系。

删除叶节点很容易，释放节点并置空父节点的指针即可。删除非叶结点，可以将子树中满足条件的节点替换上来。

如果节点不存在先返回 f a l s e false false，如果存在，则分以下几种情况：
1.直接删除：

直接删除解释
删除的节点有单个子节点左为空就让父节点指向右子树，右为空就让父节点指向左子树
删除的节点无子节点归类到上一类处理

2.替换删除：
在这里插入图片描述

替换删除解释
删除的节点左右子节点都有用左树的最大节点，或右树的最小节点，替换被删节点。
  1. 先将左树最大节点的左孩子托，或是右树最小节点的右孩子托付给父节点。
  2. 再将左树最大节点覆盖待删除的节点。
非递归删除
bool erase(const K& key)
{node* parent = nullptr; // 父节点指针初始化为nullptrnode* cur = _root; // 当前节点指针指向根节点while (cur) // 循环遍历直到当前节点为空{if (key < cur->_key) // 如果搜索键小于当前节点键值{parent = cur; // 更新父节点指针为当前节点cur = cur->_left; // 移动到左子节点}else if (key > cur->_key) // 如果搜索键大于当前节点键值{parent = cur; // 更新父节点指针为当前节点cur = cur->_right; // 移动到右子节点}else // 如果搜到到匹配的键值{if (!cur->_left) // 如果当前节点没有左子节点{if (parent == nullptr)_root = _root->_right;else if (cur == parent->_left)parent->_left = cur->_right;elseparent->_right = cur->_right;delete cur; // 删除当前节点}else if (!cur->_right) // 如果当前节点没有右子节点{if (parent == nullptr)_root = _root->_left;else if (cur == parent->_left)parent->_left = cur->_left;elseparent->_right = cur->_left;delete cur; // 删除当前节点}else // 如果当前节点有左右子节点{
#ifdef 方式1 // 采用方式1删除节点--直接删除node* min = cur->_right; // 当前节点的右子树中找到最小节点while (min->_left)min = min->_left;K minkey = min->_key;erase(min->_key);cur->_key = minkey;
#endif#ifdef 方式2 // 采用方式2删除节点--替换删除node* min_parent = cur; // 最小节点的父节点node* min = cur->_right; // 当前节点的右子树中找到最小节点while (min->_left){min_parent = min;min = min->_left;}cur->_key = min->_key; // 更新当前节点的键值为最小节点的键值if (min == min_parent->_left)min_parent->_left = min->_right;elsemin_parent->_right = min->_right;delete min; // 删除最小节点
#endif}return true;}}return false;
}
递归删除
bool erase_r(const K& key)
{// 调用递归删除函数，传入根节点指针和搜索键值return _erase_r(_root, key);
}bool _erase_r(node*& root, const K& key)
{// 如果当前子树根节点为空，返回falseif (root == nullptr)return false;// 根据搜索键值与当前节点键值的比较，决定进入左子树或右子树进行递归删除if (key < root->_key)return _erase_r(root->_left, key);else if (key > root->_key)return _erase_r(root->_right, key);else{// 保存当前节点指针node* del = root;// 如果当前节点没有左子节点，将右子节点替换当前节点if (!root->_left)root = root->_right;// 如果当前节点没有右子节点，将左子节点替换当前节点else if (!root->_right)root = root->_left;else{// 寻找右子树中的最小节点node* min = root->_right;while(min->_left)min = min->_left;root->_key = min->_key; // 更新当前节点键值为最小节点键值// 递归删除最小节点，并返回结果return _erase_r(root->_right, min->_key);}// 释放删除节点delete del;return true; // 返回删除成功}
}

 

3. 二叉搜索树的应用

搜索树有两种应用，key搜索模型和key/value搜索模型。此外，二叉搜索树插入重复值会失败，所以自带去重功能。

key搜索模型

key搜索模型查找返回真假，只能用来判断数据是否存在。应用场景如存储车牌号判断是否放行等。

kv搜索模型

通过key查找对应value，两个值是强相关的映射关系。 应用场景如中英互译，身份绑定等。

cppCopy code
// 结构体定义包括键值对节点和左右子节点指针
template<class K, class V>
struct bstree_node
{bstree_node<K, V>* _left;bstree_node<K, V>* _right;K _key;V _val;// 构造函数初始化键、值和左右子节点指针bstree_node<K, V>(const K& key, const V& val): _key(key), _val(val), _left(nullptr), _right(nullptr){}
};// 二叉搜索树类
template<class K, class V>
class bstree
{typedef bstree_node<K, V> node; // 节点类型定义为树节点结构体
public:// 插入节点函数，传入键值和值，返回插入是否成功bool insert(const K& key, const V& val){if (_root == nullptr) // 如果根节点为空{_root = new node(key, val); // 创建新节点作为根节点return true;}node* parent = nullptr; // 父指针初始化为空node* cur = _root; // 当前节点指针指向根节点while (cur) // 循环查找插入位置{if (key < cur->_key) // 如果插入键值小于当前节点键值{parent = cur; // 更新父指针为当前节点cur = cur->_left; // 移动到左子节点}else if (key > cur->_key) // 如果插入键值大于当前节点键值{parent = cur; // 更新父指针为当前节点cur = cur->_right; // 移动到右子节点}elsereturn false; // 如果键值相等，返回失败}if (key < parent->_key) // 根据父节点键值判断位置插入左子节点或右子节点parent->_left = new node(key, val); // 创建新节点作为左子节点else if (key > parent->_key)parent->_right = new node(key, val); // 创建新节点作为右子节点return true; // 返回插入成功}// 查找键值对应节点，返回找到的节点指针，如果不存在返回空指针node* find(const K& key){node* cur = _root; // 当前节点指针指向根节点while (cur) // 循环查找节点{if (key < cur->_key) // 如果搜索键值小于当前节点键值cur = cur->_left; // 移动到左子节点else if (key > cur->_key) // 如果搜索键值大于当前节点键值cur = cur->_right; // 移动到右子节点elsereturn cur; // 找到匹配键值时返回当前节点}return nullptr; // 没找到返回空指针}// 删除节点函数，传入键值，返回删除是否成功bool erase(const K& key){node* parent = nullptr; // 父节点指针初始化为空node* cur = _root; // 当前节点指针指向根节点while (cur) // 循环查找删除节点{if (key < cur->_key) // 如果键值小于当前节点键值{parent = cur; // 更新父节点指针为当前节点cur = cur->_left; // 移动到左子节点}else if (key > cur->_key) // 如果键值大于当前节点键值{parent = cur; // 更新父节点指针为当前节点cur = cur->_right; // 移动到右子节点}else // 找到匹配键值的节点{if (!cur->_left) // 如果当前节点没有左子节点{if (!parent) // 如果父节点为空，说明当前节点为根节点_root = _root->_right; // 将根节点替换为右子节点else if (cur == parent->_left) // 如果当前节点是父节点的左子节点parent->_left = cur->_right; // 将父节点的左子节点替换为当前节点的右子节点elseparent->_right = cur->_right; // 将父节点的右子节点替换为当前节点的右子节点delete cur; // 删除当前节点}else if (!cur->_right) // 如果当前节点没有右子节点{if (!parent) // 如果父节点为空，说明当前节点为根节点_root = _root->_left; // 将根节点替换为左子节点else if (cur == parent->_left) // 如果当前节点是父节点的左子节点parent->_left = cur->_left; // 将父节点的左子节点替换为当前节点的左子节点elseparent->_right = cur->_left; // 将父节点的右子节点替换为当前节点的左子节点delete cur; // 删除当前节点}else // 如果当前节点有左右子节点{node* min_parent = cur; // 最小节点的父节点初始化为当前节点node* min = cur->_right; // 最小节点指针初始化为当前节点的右子节点while (min->_left) // 寻找右子树中的最小节点{min_parent = min;min = min->_left;}cur->_key = min->_key; // 更新当前节点键值为最小节点键值cur->_val = min->_val; // 更新当前节点值为最小节点值if (min == min_parent->_left) // 将最小节点的父节点指向最小节点右子节点min_parent->_left = min->_right;elsemin_parent->_right = min->_right;delete min; // 删除最小节点}return true; // 返回删除成功}}return false; // 未找到匹配键值，返回删除失败}// 中序遍历函数，输出键值对void inorder(){_inorder(_root); // 调用内部中序遍历函数cout << endl; // 换行}// 中序遍历辅助函数void _inorder(node* root){if (!root) // 如果当前节点为空，返回return;_inorder(root->_left); // 递归遍历左子树cout << root->_key << "-" << root->_val << endl; // 输出当前节点键值对_inorder(root->_right); // 递归遍历右子树}private:node* _root = nullptr; // 根节点指针初始化为空
};

 

5. oj题

OJ链接题解链接
606. 根据二叉树创建字符串题解
102. 二叉树的分层遍历题解
107. 二叉树的层序遍历 II题解
236. 二叉树的最近公共祖先题解
剑指 Offer 36. 二叉搜索树与双向链表题解
105. 从前序与中序遍历序列构造二叉树题解
106. 从中序与后序遍历序列构造二叉树题解
144. 二叉树的前序遍历题解
94. 二叉树的中序遍历题解
145. 二叉树的后序遍历题解

这篇关于【数据结构】二叉搜索树--BST，Binary Search Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1032425。

相关文章

Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...
C# ComboBox下拉框实现搜索方式

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu1240、hdu1253（三维搜索题）

hdu1240、hdu1253（三维搜索题）

1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下： #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
uva 575 Skew Binary（位运算）

uva 575 Skew Binary（位运算）

求第一个以（2^(k+1)-1)为进制的数。 数据不大，可以直接搞。 代码： #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
hdu 4517 floyd+记忆化搜索

hdu 4517 floyd+记忆化搜索

题意： 有n（100）个景点，m（1000）条路，时间限制为t（300），起点s，终点e。 访问每个景点需要时间cost_i，每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问，并且当前点的访问价值应该严格大于前一个访问的点。 现在求，从起点出发，到达终点，在时间限制内，能得到的最大
阅读更多...
AI基础 L9 Local Search II 局部搜索

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态，生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案，则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时，算法停止。 — Choose k successors randomly, biased towards good ones — Close
阅读更多...
hdu4277搜索

hdu4277搜索

给你n个有长度的线段，问如果用上所有的线段来拼1个三角形，最多能拼出多少种不同的？ import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2