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

2024-07-21 1097阅读

1.定义

初始化

插入

查找

删除

完整代码

2.运用

K 模型和 KV 模型详解

K 模型

KV 模型

代码解释

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

1.定义

二叉搜索树（Search Binary Tree）

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

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

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

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

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

初始化

template
struct BSTreeNode
{//全部都共有开放的，就直接定struct
	BSTreeNode* _left;//左结构体指针
	BSTreeNode* _right;
	K _key;
	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};
//定义一个树
template
class BATree{
   typedef BSTreeNode Node;
private:
	Node* _root = nullptr;    // 这里我们构造函数都没必要写，它自己生成的就够用了
};

插入

思路：

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

在我们更换 cur 结点时记录父结点的位置 parent=cur 即可。

parent 意义：确认位置，实现插入

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

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

void InOrder(Node* root) {
    if (root == nullptr) {
        return;
    }
 
    InOrder(root->_left);            // 左
    cout _key _right);           // 右
}
//测试
void TestBSTree() {
	BSTree 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 _key _right);
	}
 
	Node* _root = nullptr;
};

完整测试代码：

#include 
using namespace std;
template
struct BSTreeNode {
    BSTreeNode* _left;
    BSTreeNode* _right;
    K _key;
    BSTreeNode(const K& key)
        : _left(nullptr)
        , _right(nullptr)
        , _key(key)
    {}
};
template
class BSTree {
    typedef BSTreeNode 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 _right;
            }
            else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            }
            else {
                return false;  // Key already exists
            }
        }
        cur = new Node(key);
        if (parent->_key _right = cur;
        }
        else {
            parent->_left = cur;
        }
        return true;
    }
    void InOrder() {
        _InOrder(_root);
        cout _left);
        cout _key _right);
    }
    Node* _root;
};
// 测试函数
void TestBSTree() {
    BSTree 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 _right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
                //找到啦
			}
		}
		return false;
        //为空了还没找到就退出
	}

删除

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

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

分别一次删除 7，14，3，8

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

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

总结：

没有孩子，或者一个孩子都好删（直接删，托孤即可）

两个孩子以上就要采取替换法（左子树的最大节点，或者右子树的最小节点）

1.该结点无左孩子

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

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

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

判断 cur 是在父节点的左还是右支，判断后将其指向parent->right/left = cur->right ，直接将右边连过去，实现重新连接的延续
最后删除 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
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;
	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};
template
class BSTree
{
	typedef BSTreeNode 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 _right;
			}
			else if(cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(key);
		if (parent->_key _right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}
	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key _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 _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 _left);
		cout _key _right);
	}
private:
	Node* _root;
};

测试：

void TestBSTree1()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree 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 
using namespace std;
template
struct BSTreeNode {
    BSTreeNode* _left;
    BSTreeNode* _right;
    K _key;
    BSTreeNode(const K& key)
        : _left(nullptr)
        , _right(nullptr)
        , _key(key)
    {}
};
template
class BSTree {
    typedef BSTreeNode 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 _right;
            }
            else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            }
            else {
                return false;  // Key already exists
            }
        }
        cur = new Node(key);
        if (parent->_key _right = cur;
        }
        else {
            parent->_left = cur;
        }
        return true;
    }
    void InOrder() {
        _InOrder(_root);
        cout _left);
        cout _key _right);
    }
    Node* _root;
};
// 测试函数
void TestBSTree() {
    BSTree 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)，即的键值对。这种结构常用于字典、映射、统计等场景。

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

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

#include 
#include 
using namespace std;
template
struct BSTreeNode {
    BSTreeNode* _left;
    BSTreeNode* _right;
    K _key;
    V _value;
    BSTreeNode(const K& key, const V& value)
        : _left(nullptr)
        , _right(nullptr)
        , _key(key)
        , _value(value)
    {}
};
template
class BSTree {
    typedef BSTreeNode 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 _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 _right = cur;
        }
        else {
            parent->_left = cur;
        }
        return true;
    }
    bool Find(const K& key, V& value) {
        Node* cur = _root;
        while (cur) {
            if (cur->_key _right;
            }
            else if (cur->_key > key) {
                cur = cur->_left;
            }
            else {
                value = cur->_value;
                return true;
            }
        }
        return false;
    }
    void InOrder() {
        _InOrder(_root);
        cout _left);
        cout  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 _right = cur;
    }
    else {
        parent->_left = cur;
    }
    return true;
}

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

查找方法：

bool Find(const K& key, V& value) {
    Node* cur = _root;
    while (cur) {
        if (cur->_key _right;
        }
        else if (cur->_key > key) {
            cur = cur->_left;
        }
        else {
            value = cur->_value;
            return true;
        }
    }
    return false;
}

- 查找方法用于查找指定键的值。如果找到该键，则返回对应的值。
1. 中序遍历方法：
```
void InOrder() {
    _InOrder(_root);
    cout _left);
    cout 
```

VPS购买请点击我

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

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

1.定义

初始化

插入

查找

删除

完整代码

2.运用

K 模型和 KV 模型详解

K 模型

KV 模型

相关阅读

怎么把织梦的模板替换?

dedecms怎么调用特定的栏目文档?

怎么抓包一个网页?

wap怎么封装app?

目录[+]