数据结构之二叉搜索树（Binary Search Tree）
- 1. ⼆叉搜索树的概念
- 2. ⼆叉搜索树的性能分析
- 3.⼆叉搜索树的 查，删，插（没有改，因为没有意义会破坏本质）（源码）
1. ⼆叉搜索树的概念
⼆叉搜索树⼜称⼆叉排序树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树:
• 若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值
• 若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结点的值
• 它的左右⼦树也分别为⼆叉搜索树
2. ⼆叉搜索树的性能分析
最优情况下，⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)，其⾼度为： O(log2 N)
最差情况下，⼆叉搜索树退化为单⽀树(或者类似单⽀)，其⾼度为： O( n/2)
所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为： O(N)
那么这样的效率显然是⽆法满⾜我们需求的，我们后续课程需要继续讲解⼆叉搜索树的变形，平衡⼆叉搜索树AVL树和红⿊树，才能适⽤于我们在内存中存储和搜索数据。另外需要说明的是，⼆分查找也可以实现 O(logN) 级别的查找效率，但是⼆分查找有两⼤缺陷：
1. 需要存储在⽀持下标随机访问的结构中，并且有序。
2. 插⼊和删除数据效率很低，因为存储在下标随机访问的结构中，插⼊和删除数据⼀般需要挪动数据。
这⾥也就体现出了平衡⼆叉搜索树的价值。
3.⼆叉搜索树的 查，删，插（没有改，因为没有意义会破坏本质）（源码）
#pragma once
#include <iostream>
using namespace std;
//bst时间复杂度：最差情况下 ：会退化成链表形状 O(N)
//理想状态下：O(logn)
template <class k>
struct bstnode {k _key;bstnode<k>* _left;bstnode<k>* _right;bstnode(const k& key):_key(key), _left(nullptr), _right(nullptr){};
};
template<class k>
class bstree {typedef bstnode<k> node;
public:bool insert(const k& key)//插入-(不支持相等值插入，要想实现，"改"下面判断条件){//先处理空树if (_root == nullptr){_root = new node(key);return true;}node* parent = nullptr;//作用：为了最后连接插入节点node* cur = _root;//把root赋给cur，让key从根节点开始找while (cur){if (cur->_key > key)//往左走{parent = cur;cur = parent->_left;}else if (cur->_key < key)//往右走{parent = cur;cur = parent->_right;}else //相等{return false;}}//循环走完，cur来到空节点//开始插入cur = new node(key);//走到这里不知道key比当前的parent大还是小，所以进行比较if (key > parent->_key)//去右{parent->_right = cur;}else//这里包含 小于 和 等于 两种情况{parent->_left = cur;}}bool find(const k& key)//查找{//查找逻辑较简单：从根节点开始找，找到空就是不存在//找的次数：最多"树的高度"次cout << "你要查找的值 ：" << key << endl;cout << "存在(1)|不存在(0): ";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;}void inorder(){cout << "中序遍历（递归法）： ";_inorder(_root);cout << endl;}//删除，分为四种情况（假设要删除的节点是 n）//1.n的左右孩子都为空--可以归为2，3情况来处理//2.n的左孩子为空--让n的父亲节点指向n的右孩子，直接delete n//3.n的右孩子为空--让n的父亲节点指向n的左孩子，直接delete n//4.n的左右孩子都不为空--只能用 替换法，找n左子树的最大节点（最右节点）//，或者找n的右子树的最小节点（最左节点），和n进行替换，然后delete n//删除的逻辑和查找差不多，都是先找到节点，没找到返回空bool erase(const k& key){node* parent = nullptr;//作用：为了最后连接插入节点node* cur = _root;//把root赋给cur，让key从根节点开始找while (cur){if (cur->_key > key)//往左走{parent = cur;cur = parent->_left;}else if (cur->_key < key)//往右走{parent = cur;cur = parent->_right;}else //相等，开始删除{ if (cur->_left == nullptr)//只有一个孩子或者没有孩子的情况{//这里有个小坑：就是要删除的节点是根节点就会崩，所以得提前判断一下if (parent == nullptr)//要删除根节点的情况,直接改根{_root = cur->_right;}else{//这里不知道cur是parent的左还是右有两种情况会导致结果有偏差，所以要判断一下if (parent->_left == cur) parent->_left = cur->_right;else parent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;}else{if (parent->_left == cur) parent->_left = cur->_left;else parent->_right = cur->_left;}delete cur;return true;}else//有两个孩子的情况{//这里我用的代替节点是n右子树的最左节点node* replaceparent = cur;node* replace = cur->_right;while (replace->_left){replaceparent = replace;replace = replace->_left; }//这里找到了代替节点,开始替换cur->_key = replace->_key;//这里的情况和上面一样不知道是父亲节点的 左 还是右if (replaceparent->_left == replace) replaceparent->_left = replace->_right;else replaceparent->_right = replace->_right;delete replace;return true;}}}//没找到return false;}
private:void _inorder(node* root)//中序递归{if (root==nullptr){return;}_inorder(root->_left);cout << root->_key << " ";_inorder(root->_right);}
private:node* _root = nullptr;
};
#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>
#include"bst.h"
using namespace std;int main()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };bstree<int> t;for (auto e : a){t.insert(e);}t.inorder();//cout<<t.find(3)<<endl;////cout<<t.find(122);for (auto e : a){t.erase(e);t.inorder();}return 0;
}
