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

雨点打透心脏的1/2处 2024-04-01 13:02 74阅读 0赞

#### 目录 ####

*   *  BST树概念
     *  BST树操作
     *   *  BST树的查找
         *  BST树的插入
         *  BST树的删除
     *  实现一个自己的BST树
     *   *  BSTNode类和BSTree类
         *  查找操作;
         *  插入操作:
         *  删除操作:
     *  应用：
     *  二叉搜索树性能分析

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

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

### BST树概念 ###

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

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

### BST树操作 ###

#### BST树的查找 ####

![在这里插入图片描述][8a5a8c15bfeb4b70afe0cd5ea4111096.png]

> 可以看到每步查找都能筛掉一般不符合的元素，有点类似于数组中的二分查找;
> 
> 这也是二叉搜索树名字的由来，他的查找效率很高;

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

#### BST树的插入 ####

插入的具体过程如下:

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

![在这里插入图片描述][c3798feb468f4e078de16a7b664d1745.png]

#### BST树的删除 ####

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

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

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

### 实现一个自己的BST树 ###

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

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

> 以单词集合中的每个单词作为key，构建一棵二叉搜索树,
> 
> **在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误**。

1.  **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; //数据冗余,不插入;map，set的普通版本不允许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();

![在这里插入图片描述][b8704c7c8b6840c4bbc0fa99030bd2d0.png]

### 二叉搜索树性能分析 ###

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

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

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

![在这里插入图片描述][cc5149159b0a4565a17ea4905e31ccde.png]

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

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

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

**AVL树！后面文章接着写**

[8a5a8c15bfeb4b70afe0cd5ea4111096.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/2e072fff517e4cad9ecfd8e714794e8e.png
[c3798feb468f4e078de16a7b664d1745.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/a1fb83653d05457c8d6550e400f73fdc.png
[b8704c7c8b6840c4bbc0fa99030bd2d0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/54bfee1fa24e4f81b0557edd887a4560.png
[cc5149159b0a4565a17ea4905e31ccde.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/40d59a26d3c8467f8b0ab46b15f2b9e6.png