数据结构之二叉搜索树（Binary Search Tree）

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;
}