15. 【C++】详解搜索二叉树 | KV模型

目录

1.定义

初始化

插入

查找

删除

完整代码

2.运用

k 模型和 kv 模型详解

k 模型

kv 模型

代码解释

为了更好地理解 map 和 set 的特性，和后面讲解查找效率极高的平衡搜索二叉树，和红黑树去实现模拟，所以决定在这里对搜索二叉树进行一个讲解~

1.定义

二叉搜索树（search binary tree）

每一颗子树都满足，左子树上所有节点的值都小于根节点的值，右子树都大于

所以就能得到性质：左子树的值 < 根 < 右子树的值

它也称二叉排序树或二叉查找树，最多找高度次 o（n）

二叉搜索树蜕化为单边树（或类似单边），其平均比较次数为：o（n）

搜索二叉树由于控制不了极端情况，与 o(logn) 失之交臂了，但后面讲到的平衡二叉搜索树可以做到。

初始化

template<class k>
struct bstreenode
{//全部都共有开放的，就直接定struct
	bstreenode<k>* _left;//左结构体指针
	bstreenode<k>* _right;
	k _key;

	bstreenode(const k& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};
//定义一个树
template<class k>
class batree{
   typedef bstreenode<k> node;
private:
	node* _root = nullptr;    // 这里我们构造函数都没必要写，它自己生成的就够用了
};

插入

思路：

1. 检查是否有根结点 _root，如果没有我们就 new 一个结点出来作为根结点。
2. 插入就需要找到插入位置，我们定义一个 cur 变量，从根节点开始，
   根据搜索二叉树 性质，将 cur 结点的 key 与插入的值 key 进行大小比较
3. 仅仅 new 上一个新结点给 cur 是完成不了插入操作的！需要 cur 跟上一层（cur 的父亲）相链接才行！为了能找到上一层，所以我们还需要额外定义一个 parent 变量来记录 cur 的父结点

     4.比较确定 cur 应该链接父亲的左边，还是链接父亲的右边，插入即可

//插入
	bool insert(const k& key)
	{
        //没有根节点就new一个
		if (_root == nullptr)
		{
			_root = new node(key);
			return true;
		}

		node* parent = nullptr;
		node* cur = _root;
        //循环比较
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;//小了就应该往右找
			}
			else if(cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}//不断比较，搜索找到了之后
		}
       //new了一个新节点，和parent的key比较，确定插入的左右
		cur = new node(key);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}//将新节点插入到二叉树里面啦

		return true;
	}

再写一个中序遍历来测试一下插入的效果：

void inorder(node* root) {
    if (root == nullptr) {
        return;
    }
 
    inorder(root->_left);            // 左
    cout << root->_key << " ";       // 值
    inorder(root->_right);           // 右
}

//测试
void testbstree() {
	bstree<int> t;
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto e : a) {
		t.insert(e);
	}
	t.inorder();  ❌ 没法传根
}

此时会出现一个问题，因为根是私有的，我们没办法把根传过去，我们可以采取 getroot，这里的话，我们将其设为内部函数即可

	void inorder() {
		_inorder(_root);
	}
 
private:
    // 改为内部函数
	void _inorder(node* root) {
		if (root == nullptr) {
			return;
		}
		_inorder(root->_left);
		cout << root->_key << " ";
		_inorder(root->_right);
	}
 
	node* _root = nullptr;
};

完整测试代码：

#include <iostream>
using namespace std;

template<class k>
struct bstreenode {
    bstreenode<k>* _left;
    bstreenode<k>* _right;
    k _key;

    bstreenode(const k& key)
        : _left(nullptr)
        , _right(nullptr)
        , _key(key)
    {}
};

template<class k>
class bstree {
    typedef bstreenode<k> node;

public:
    bstree() : _root(nullptr) {}

    bool insert(const k& key) {
        if (_root == nullptr) {
            _root = new node(key);
            return true;
        }

        node* parent = nullptr;
        node* cur = _root;
        //设置结构体形的cur节点，并进行初始化
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            }
            else {
                return false;  // key already exists
            }
        }
        cur = new node(key);
        if (parent->_key < key) {
            parent->_right = cur;
        }
        else {
            parent->_left = cur;
        }

        return true;
    }

    void inorder() {
        _inorder(_root);
        cout << endl;
    }

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

    node* _root;
};

// 测试函数
void testbstree() {
    bstree<int> t;
    int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
    for (auto e : a) {
        t.insert(e);
    }
    t.inorder();
}

int main() {
    testbstree();
    return 0;
}

打印：

查找

从根开始，如果要查找的值大于 cur 目前的值，则让 cur 往右走，反之往左走。

当查找得值与 cur 的值相等时则说明找到了，返回 true。

当 cur 触及到空（while 循环结束）则说明找不到，返回 false。

//查找
bool find(const k& key)
	{
		node* cur = _root;//从根开始
		while (cur)
		{//循环查找
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
                //找到啦
			}
		}
		return false;
        //为空了还没找到就退出
	}

删除

搜索二叉树删除的实现是有难度的，删除的实现就需要一些技巧了，断然删除会毁树。

我们可以以下面这棵树为例

7 和 14 属于直接删除的场景

3，8 属于需要替换法进行删除的场景

总结：

1.该结点无左孩子

1. 若该结点为 root，直接让 root 等于它的右孩子结点。（一定要先判断）

画忘了，画成右为空了qwq，大家同理的理解一下

 // 左为空
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{//如果是根节点,parent就变为空了
						_root = cur->_right;
					}
					else

1. 判断 cur 是在父节点的左还是右支，判断后将其指向parent->right/left = cur->right ，直接将右边连过去，实现重新连接的延续
2. 最后删除 cur 结点

if (cur->_left == nullptr) {//该结点无左孩子
    /* 判断要删除的结点是否为根结点 */
    if (cur == _root) {
        _root = cur->_right;
    }
    else {
        if (cur == father->_right) {
            //判断他是上一个节点的左节点还是右节点
            father->_right = cur->_right;
        }
        else {
            father->_left = cur->_right;
        }
    }
    delete cur;
    cur = nullptr;
}

else
{
	//查找到左边的最右节点
	//右边的最左节点
	//交换
	//删除

	// 找替代节点
	node* parent = cur;
    //不能设置为nullptr，循环可能不进去了
	//之后要对父节点进行处理
	node* leftmax = cur->_left;
    //设置最大节点
	while (leftmax->_right)
	{
		parent = leftmax;
		leftmax = leftmax->_right;
        //即最右节点
	}
    //交换key
	swap(cur->_key, leftmax->_key);

删除的判断

//将parent置空处理,断联
	if (parent->_left == leftmax)
	{
		parent->_left = leftmax->_left;
	}
	else
	{
		parent->_right = leftmax->_left;
	}
//删除cur的处理
	cur = leftmax;
}

				delete cur;
				return true;
			}
		}

		return false;

完整代码

#pragma once

template<class k>
struct bstreenode
{
	bstreenode<k>* _left;
	bstreenode<k>* _right;
	k _key;

	bstreenode(const k& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};

template<class k>
class bstree
{
	typedef bstreenode<k> node;
public:
	bstree()
		:_root(nullptr)
	{}

	bool insert(const k& key)
	{
		if (_root == nullptr)
		{
			_root = new node(key);
			return true;
		}

		node* parent = nullptr;
		node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if(cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new node(key);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		return true;
	}

	bool find(const k& key)
	{
		node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}

		return false;
	}

	bool erase(const k& key)
	{
		node* parent = nullptr;
		node* cur = _root;

		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else // 找到了
			{
				 // 左为空
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}
				}// 右为空
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}					
				} // 左右都不为空 
				else
				{
					// 找替代节点
					node* parent = cur;
					node* leftmax = cur->_left;
					while (leftmax->_right)
					{
						parent = leftmax;
						leftmax = leftmax->_right;
					}

					swap(cur->_key, leftmax->_key);

					if (parent->_left == leftmax)
					{
						parent->_left = leftmax->_left;
					}
					else
					{
						parent->_right = leftmax->_left;
					}

					cur = leftmax;
				}

				delete cur;
				return true;
			}
		}

		return false;
	}

	void inorder()
	{
		_inorder(_root);
		cout << endl;
	}

	void _inorder(node* root)
	{
		if (root == null)
		{
			return;
		}
//递归实现中序遍历的打印
		_inorder(root->_left);
		cout << root->_key << " ";
		_inorder(root->_right);
	}
private:
	node* _root;
};

测试：

void testbstree1()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	bstree<int> t;
	for (auto e : a)
	{
		t.insert(e);
	}

	t.inorder();

	t.erase(4);
	t.inorder();

	t.erase(6);
	t.inorder();

	t.erase(7);
	t.inorder();

	t.erase(3);
	t.inorder();

	for (auto e : a)
	{
		t.erase(e);//插入
	}
	t.inorder();
}

运行：

2.运用

k 模型和 kv 模型详解

k 模型

k 模型指的是只有 key 作为关键码的结构，在这种结构中只存储 key。k 模型常用于需要搜索具体值的场景，比如拼写检查、数字搜索等。

示例代码：k 模型的二叉搜索树

以下是一个实现 k 模型的二叉搜索树（bst）的完整代码示例：

#include <iostream>
using namespace std;

template<class k>
struct bstreenode {
    bstreenode<k>* _left;
    bstreenode<k>* _right;
    k _key;

    bstreenode(const k& key)
        : _left(nullptr)
        , _right(nullptr)
        , _key(key)
    {}
};

template<class k>
class bstree {
    typedef bstreenode<k> node;

public:
    bstree() : _root(nullptr) {}

    bool insert(const k& key) {
        if (_root == nullptr) {
            _root = new node(key);
            return true;
        }

        node* parent = nullptr;
        node* cur = _root;
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            }
            else {
                return false;  // key already exists
            }
        }

        cur = new node(key);
        if (parent->_key < key) {
            parent->_right = cur;
        }
        else {
            parent->_left = cur;
        }

        return true;
    }

    void inorder() {
        _inorder(_root);
        cout << endl;
    }

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

    node* _root;
};

// 测试函数
void testbstree() {
    bstree<int> t;
    int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
    for (auto e : a) {
        t.insert(e);
    }
    t.inorder();
}

int main() {
    testbstree();
    return 0;
}

kv 模型

kv 模型表示每一个关键码 (key) 都有与之对应的值 (value)，即 <key, value> 的键值对。这种结构常用于字典、映射、统计等场景。

示例代码：kv 模型的二叉搜索树

以下是一个实现 kv 模型的二叉搜索树的完整代码示例：

#include <iostream>
#include <string>
using namespace std;

template<class k, class v>
struct bstreenode {
    bstreenode<k, v>* _left;
    bstreenode<k, v>* _right;
    k _key;
    v _value;

    bstreenode(const k& key, const v& value)
        : _left(nullptr)
        , _right(nullptr)
        , _key(key)
        , _value(value)
    {}
};

template<class k, class v>
class bstree {
    typedef bstreenode<k, v> node;

public:
    bstree() : _root(nullptr) {}

    bool insert(const k& key, const v& value) {
        if (_root == nullptr) {
            _root = new node(key, value);
            return true;
        }

        node* parent = nullptr;
        node* cur = _root;
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            }
            else {
                cur->_value = value;  // update value if key already exists
                return true;
            }
        }

        cur = new node(key, value);
        if (parent->_key < key) {
            parent->_right = cur;
        }
        else {
            parent->_left = cur;
        }

        return true;
    }

    bool find(const k& key, v& value) {
        node* cur = _root;
        while (cur) {
            if (cur->_key < key) {
                cur = cur->_right;
            }
            else if (cur->_key > key) {
                cur = cur->_left;
            }
            else {
                value = cur->_value;
                return true;
            }
        }
        return false;
    }

    void inorder() {
        _inorder(_root);
        cout << endl;
    }

private:
    void _inorder(node* root) {
        if (root == nullptr) {
            return;
        }
        _inorder(root->_left);
        cout << "<" << root->_key << ", " << root->_value << "> ";
        _inorder(root->_right);
    }

    node* _root;
};

// 测试函数
void testkvtree() {
    bstree<string, string> dict;
    dict.insert("apple", "苹果");
    dict.insert("banana", "香蕉");
    dict.insert("cherry", "樱桃");

    string value;
    if (dict.find("banana", value)) {
        cout << "banana: " << value << endl;
    }

    dict.inorder();
}

int main() {
    testkvtree();
    return 0;
}

代码解释

1. 节点结构定义：

template<class k, class v>
struct bstreenode {
    bstreenode<k, v>* _left;
    bstreenode<k, v>* _right;
    k _key;
    v _value;

    bstreenode(const k& key, const v& value)
        : _left(nullptr)
        , _right(nullptr)
        , _key(key)
        , _value(value)
    {}
};

• • 这是一个模板结构，表示二叉搜索树的节点。每个节点包含一个键值对 (key, value) 以及指向左子节点和右子节点的指针。

1. 二叉搜索树类定义：

template<class k, class v>
class bstree {
    typedef bstreenode<k, v> node;

public:
    bstree() : _root(nullptr) {}

• • 这是一个模板类，表示二叉搜索树。包含根节点指针 _root 以及插入、查找和中序遍历的方法。

1. 插入方法：

bool insert(const k& key, const v& value) {
    if (_root == nullptr) {
        _root = new node(key, value);
        return true;
    }

    node* parent = nullptr;
    node* cur = _root;
    while (cur) {
        if (cur->_key < key) {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_key > key) {
            parent = cur;
            cur = cur->_left;
        }
        else {
            cur->_value = value;  // update value if key already exists
            return true;
        }
    }

    cur = new node(key, value);
    if (parent->_key < key) {
        parent->_right = cur;
    }
    else {
        parent->_left = cur;
    }

    return true;
}

• • 插入方法用于将新的键值对插入到树中。通过比较键值确定新节点应该插入的位置。如果键已存在，则更新其对应的值。

1. 查找方法：

bool find(const k& key, v& value) {
    node* cur = _root;
    while (cur) {
        if (cur->_key < key) {
            cur = cur->_right;
        }
        else if (cur->_key > key) {
            cur = cur->_left;
        }
        else {
            value = cur->_value;
            return true;
        }
    }
    return false;
}

• • 查找方法用于查找指定键的值。如果找到该键，则返回对应的值。

1. 中序遍历方法：

void inorder() {
    _inorder(_root);
    cout << endl;
}

private:
void _inorder(node* root) {
    if (root == nullptr) {
        return;
    }
    _inorder(root->_left);
    cout << "<" << root->_key << ", " << root->_value << "> ";
    _inorder(root->_right);
}

• • 中序遍历方法用于遍历树并输出键值对。递归地遍历左子树、访问根节点、然后遍历右子树。

1. 测试函数：

void testkvtree() {
    bstree<string, string> dict;
    dict.insert("apple", "苹果");
    dict.insert("banana", "香蕉");
    dict.insert("cherry", "樱桃");

    string value;
    if (dict.find("banana", value)) {
        cout << "banana: " << value << endl;
    }

    dict.inorder();
}

int main() {
    testkvtree();
    return