文章目录
- 二叉搜索树的概念
- 二叉搜索树基本操作
-
- 二叉搜索树的实现
- 二叉搜索树key和key/value
二叉搜索树的概念
- 左子树上所有节点的值都小于等于根节点的值,
右子树上所有节点的值都大于等于根节点的值 - 左右子树也分别为二叉树
- 二叉搜索树中可以插入相等的值也可以插入不相等的值,具体看使用场景定义
二叉搜索树基本操作
1. 插入节点
- 新节点和根节点进行比较
- 如果要插入的值小于当前节点的值,则移动到左子节点
如果要插入的值大于当前节点的值,则移动到右子节点 - 重复上述过程,直到找到一个空位置,然后在该位置插入新节点
2. 查找节点
- 从根节点开始比较要查找的值和当前值
- 如果要查找的值小于当前节点的值,则移动到当前节点的左子节点
如果要查找的值大于当前节点的值,则移动到当前节点的右子节点 - 重复上述过程, 如果要查找的值等于当前节点的值,则返回当前节点,查找成功
3. 删除节点
- 删除的节点是叶子节点:直接删除该节点
- 删除的节点只有一个子节点:将其子节点替换到当前该节点
- 删除的节点有两个子节点:找到该节点右子树中的最小节点(或左子树中的最大节点),将其值替换到该节点的位置,然后删除该最小节点
二叉搜索树的实现
emplate<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
{using Node = BSTNode<K>;
public:bool Insert(const K& key){if (_root == nullptr) {_root = new Node(key);return true;}Node* parent = nullptr; Node* cur = _root; while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}elsereturn false;}cur = new Node(key);if (key < parent->_key){parent->_left = cur;}else{parent->_right = cur;}return true;}bool Find(const K& key){Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}elsereturn true;}return false;}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur) {if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else {if (cur->_left == nullptr) {if (cur == _root) {_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if(cur->_right == nullptr){if (cur == _root) {_root = cur->_left;}else{if (parent->_left = cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else {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;elsereplaceparent->_right = replace->_right; delete replace;}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 << " ";_InOrder(root->_right);}Node* _root = nullptr;
};
二叉搜索树key和key/value
namespace key_value
{template<class K, class V>struct BSTNode{K _key;V _value;BSTNode<K, V>* _left;BSTNode<K, V>* _right;BSTNode(const K& key, const V& value):_key(key), _value(value), _left(nullptr), _right(nullptr){}};template<class K, class V>class BSTree{using Node = BSTNode<K, V>;public:BSTree() = default;BSTree(const BSTree& t){_root = Copy(t._root);}BSTree& operator=(BSTree tmp){swap(_root, tmp._root);return *this;}~BSTree(){Destroy(_root);_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{return false;}}cur = new Node(key, value);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}Node* 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 cur;}}return nullptr;}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->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{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;elsereplaceParent->_right = replace->_right;delete replace;}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 << endl;_InOrder(root->_right);}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}private:Node* _root = nullptr;};
}