二叉搜索树详解--实现插入和删除

对于普通的二叉树来说能延伸出许多好用的数据结构二叉搜索树(BST树)就是其中一个;

学习二叉搜索树将为后续的AVL树与红黑树和mapset等STL容器打下坚实的基础;

BST树概念

二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:

• 若它的左子树不为空则左子树上所有节点的值都小于根节点的值
• 若它的右子树不为空则右子树上所有节点的值都大于根节点的值
• 它的左右子树也分别为二叉搜索树

BST树操作

BST树的查找

可以看到每步查找都能筛掉一般不符合的元素有点类似于数组中的二分查找;

这也是二叉搜索树名字的由来他的查找效率很高;

注意不难发现中序遍历BST树就是一个升序的结构!;

BST树的插入

插入的具体过程如下:

按照二叉搜索树的性质找到某个val合适的插入点;

BST树的删除

首先查找元素是否在二叉搜索树中如果不存在则返回,

否则要删除的结点可能分下面四种情况

1. 要删除的结点无孩子结点 -->直接删除
2. 要删除的结点只有左孩子 -->左孩子直接与他的父亲连接(左or右)然后删掉它
3. 要删除的结点只有右孩子 -->右孩子直接与他的父亲连接(左or右)然后删掉它
4. 要删除的结点左右孩子都有;–>去它的右子树找最左节点替换它的位置 用替代法删除结点!

实现一个自己的BST树

由于一般具有k-v结构的数据结构底层是BST树那么我们这里也实现一个K-V结构的BST树;

1. K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下

以单词集合中的每个单词作为key构建一棵二叉搜索树,

在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。

2. KV模型每一个关键码key**都有与之对应的值Value**即的键值对。该种方式在现实生 活中非常常见

   比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英 文单词与其对应的中文就构成一种键值对

   再比如统计单词次数统计成功后给定 单词就可快速找到其出现的次数单词与其出现次数就是就构成一种键值对。

   <单词中文含义>为键值对构造二叉搜索树注意二叉搜索树需要比较键值对比较时只比较Key

   查询英文单词时只需给出英文单词就可快速找到与其对应的key

BSTNode类和BSTree类

基本框架:

template<class K,class V>
struct BSTNode {
    BSTNode(const K& key = K(), const V& value = V())
        : _pLeft(nullptr), _pRight(nullptr), _key(key), _Value(value)
    {}
    BSTNode<T>* _pLeft;
    BSTNode<T>* _pRight;
    K _key;
    V _value
};
template<class K, class V>
class BSTree {
    typedef BSTNode<K, V> Node;
private:
    Node* _root;
}

查找操作;

 Node* Find(const K& key) 
    {
        //根据BST树的特性来find;
        if (_root == nullptr) return nullptr;
        Node* cur = _root;
        //原则上来说 是没有重复key存在的
        while (cur) {
            if (key > cur->_key) {
                cur = cur->_pRight;
            }
            else if (key < cur->_key) {
                cur = cur->_pLeft;
            }
            else return cur;

        }
        return nullptr;
        
    }

插入操作:

 bool Insert(const K& key, const V& value)
    {
        if (_root == nullptr) {
            _root = new Node({ key,value });
            return true;
        }
        
        Node* cur = _root;
        Node* prev = _root;
        //原则上来说 是没有重复key存在的
        while (cur) {
            if (key > cur->_key) {
                prev = cur;
                cur = cur->_pRight;
            }
            else if (key < cur->_key) {
                prev = cur;
                cur = cur->_pLeft;
            }
            else return false; //数据冗余,不插入;mapset的普通版本不允许key重复
            
        }
        Node* newnode = new Node({ key,value });
        if (prev->_key < key) {
            prev->_pRight = newnode;
        }
        else {
            prev->_pLeft = newnode;
        }
        return true;
    }

删除操作:

 
bool Erase(const K& key)
{
	Node* cur = _root;
	Node* father = nullptr;
	while (cur) {
		if (key > cur->_key) {
			father = cur;
			cur = cur->_pRight;
		}
		else if (key < cur->_key) {
			father = cur;
			cur = cur->_pLeft;
		}
		else break;

	}
	if (!cur) return false;
	

	//处理下特殊情况:需要删root节点
	if (father == nullptr) {
		Node* tmp = _root;
		if (father->_pRight) {
			_root = father->_pRight;
		}
		else if (father->_pLeft) {
			_root = father->_pLeft;
		}

		delete tmp;
		return true;
	}



	//1,无孩子节点,直接删;
	if (!cur->_pLeft && !cur->_pRight) {
		if (father->_pLeft == cur){
			father->_pLeft = nullptr;
		}
		else father->_pRight = nullptr;


	}
	//2,有左孩子or右孩子;
	else if ((!cur->_pLeft && cur->_pRight) || (cur->_pLeft && !cur->_pRight)) {
		if (father->_pLeft == cur) {//cur是father的左	
			if (cur->_pLeft) father->_pLeft = cur->_pLeft;
			else father->_pLeft = cur->_pRight;
		}
		else {//cur是father的右
			if (cur->_pLeft) father->_pRight = cur->_pLeft;
			else  father->_pRight = cur->_pRight;
		}
	}
	else {
		//3.左右都有孩子;
		//替代法找右子树最左节点替换他; 及的保存parent 替换的时候树得调整
		Node* p_replace = cur;
		Node* replace = cur->right;

		while (replace->_pLeft) {
			p_replace = replace;
			replace = replace->_pLeft;
;		}

		//swap(cur, rmin);//别乱用swap 会出错;

		if (father->_pLeft == cur) { //注意 这个father是cur的father
			father->_pLeft = replace;
		}
		else {
			father->_pRight = replace;
		}
		 
		cur->_val = replace->_val;//交换要删除节点的值与替代节点的值之后把replace删了 删的时候替换的时候树得调整

		if (p_replace->_pLeft == replace) {
			p_replace->_pLeft = replace->_pLeft;
		}
		else {
			p_replace->_pRight = replace->_pRight;
		}

		cur = replace;//改变最后删的对象
	}
	delete cur;
	cur = nullptr;
	return true;
}

应用

//统计词语出现的次数
string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };
	// 统计水果出现的次
	BSTree<string, int> countTree;
	for (auto str : strs)
	{
		auto ret = countTree.Find(str);
		if (ret == NULL)
		{
			countTree.Insert(str, 1);
		}
		else
		{
			ret->_value++;
		}
	}
	countTree.InOrder();

二叉搜索树性能分析

插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的 深度的函数即结点越深则比较次数越多

但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树

最优情况下二叉搜索树为完全二叉树其平均比较次数为:log2N

最差情况下二叉搜索树退化为单支树其平均比较次数为N/2

问题如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插入关键码 都可以是二叉搜索树的性能最佳

AVL树后面文章接着写