Table of contents
2. Non-recursive implementation of binary search tree
2.3 Search for deletion of binary tree (the most important and most difficult interface)
3.(key) recursive implementation of binary search tree
4.(KV) recursive implementation of binary search tree
1. Binary search tree concept
A search binary tree, also known as a binary sorting tree, is either an empty tree or a binary tree with the following properties
- If its left subtree is not empty, the value of all nodes in the left subtree is less than the value of the root node
- If its right subtree is not empty, the value of all nodes in the right subtree is greater than the value of the root node
- Its left and right subtrees are also binary search trees (any node satisfies that the left subtree is smaller than the head node, and the right subtree is larger than the head node)
Most of the examples below are distanced by the following searchable binary tree:
2.1 The time complexity of finding a node for binary search number is O(N), which should be the worst
2. Non-recursive implementation of binary search tree
2.1 Insertion of binary search tree
Ideas:
bool Insert(const K& key)
{
//Empty tree direct insertion
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* cur = _root;
//Keep the parent node where you want to insert
Node* parent = nullptr;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
//There is no redundancy in a binary search tree, that is, there are no identical elements
return false;
}
}
cur = new Node(key);
//Determine whether it is on the left or right of the parent node
if (parent->_key > key)
{
parent->_left = cur;
return true;
}
else
{
parent->_right = cur;
return true;
}
}2.2 Search the binary tree to find
Ideas and insertions are almost unnecessary
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;
}2.3 Search for deletion of binary tree (the most important and most difficult interface)
Processing method with two nodes: replacement method, select the largest node in the left subtree of the key node or the smallest node in the right subtree, give the value to the key node, and delete the one with one node;
bool Erase(const K& key)//delete
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
//find key
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
//Find the key, if there is only one child node
if (cur->_left == nullptr)
{
if (cur=_root)
{
//No left subtree cur or head node
_root = cur->_right;
delete cur;
}
else
{
//It is not clear whether cur is parent or left or right
if (parent->_left == cur) {
parent->_left = cur->_right;
}
else {
parent->_right = cur->_right;
}
delete cur;
}
}
else if (cur->_right == nullptr)
{
//No left subtree cur or head node
if (cur = _root)
{
_root = cur->_left;
delete cur;
}
else
{
if (parent->_left == cur) {
parent->_left = cur->_left;
}
else {
parent->_right = cur->_left;
}
delete cur;
}
}
else
{
parent = cur;//save key node
Node* curparent = cur;//Save the parent node of cur
cur = cur->_right;
//The right subtree is the smallest or the left subtree is the largest
while (cur->_left != nullptr)
{
curparent = cur;
cur = cur->_left;
}
parent->_key = cur->_key;// right subtree minimal replacement
if (cur->_left == nullptr)
{
//It is not clear whether cur is parent or left or right
if (curparent->_left == cur) {
curparent->_left = cur->_right;
}
else {
curparent->_right = cur->_right;
}
}
else if (cur->_right == nullptr)
{
if (curparent->_left == cur) {
curparent->_left = cur->_left;
}
else {
curparent->_right = cur->_left;
}
}
delete cur;
}
return true;
}
}
return false;
}
2.4 All codes of binary search number
#pragma once
#include <iostream>
using namespace std;
template<class K>
struct BSTreeNode
{
BSTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
BSTree()
:_root(nullptr)
{}
bool Insert(const K& key)
{
//Empty tree direct insertion
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* cur = _root;
//Keep the parent node where you want to insert
Node* parent = nullptr;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
//There is no redundancy in a binary search tree, that is, there are no identical elements
return false;
}
}
cur = new Node(key);
//Determine whether it is on the left or right of the parent node
if (parent->_key > key)
{
parent->_left = cur;
return true;
}
else
{
parent->_right = 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)//delete
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
//find key
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
//Find the key, if there is only one child node
if (cur->_left == nullptr)
{
if (cur=_root)
{
//No left subtree cur or head node
_root = cur->_right;
delete cur;
}
else
{
//It is not clear whether cur is parent or left or right
if (parent->_left == cur) {
parent->_left = cur->_right;
}
else {
parent->_right = cur->_right;
}
delete cur;
}
}
else if (cur->_right == nullptr)
{
//No left subtree cur or head node
if (cur = _root)
{
_root = cur->_left;
delete cur;
}
else
{
if (parent->_left == cur) {
parent->_left = cur->_left;
}
else {
parent->_right = cur->_left;
}
delete cur;
}
}
//else ///2, the left and right are not empty, the replacement method deletes
//{
// Node* minRight = cur->_right;
// while (minRight->_left)
// {
// minRight = minRight->_left;
// }
// K min = minRight->_key;
// // Call yourself recursively to delete the replacement node, and it will definitely go to the case where the left is empty.
// this->Erase(min);
// cur->_key = min;
//}
else
{
parent = cur;//save key node
Node* curparent = cur;//Save the parent node of cur
cur = cur->_right;
//The right subtree is the smallest or the left subtree is the largest
while (cur->_left != nullptr)
{
curparent = cur;
cur = cur->_left;
}
parent->_key = cur->_key;// right subtree minimal replacement
if (cur->_left == nullptr)
{
//It is not clear whether cur is parent or left or right
if (curparent->_left == cur) {
curparent->_left = cur->_right;
}
else {
curparent->_right = cur->_right;
}
}
else if (cur->_right == nullptr)
{
if (curparent->_left == cur) {
curparent->_left = cur->_left;
}
else {
curparent->_right = cur->_left;
}
}
delete cur;
}
return true;
}
}
return false;
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
cout<<endl;
}
private:
Node* _root;
};3.(key) recursive implementation of binary search tree
key search scenario (applicable to the problem of absence)
- Dormitory building access control: save the student's student number in the key search binary tree to check whether the student number is
- The community garage scans the bar lift system and enters the license plate number into the system
namespace key
{
template<class K>
struct BinarySearchNode
{
BinarySearchNode(const K& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
BinarySearchNode<K>* _left;
BinarySearchNode<K>* _right;
K _key;
};
template<class K>
class BSTree
{
typedef BinarySearchNode<K> Node;
public:
BSTree()
:_root(nullptr)
{}
Node* FindR(const K& key)
{
return _FindR(_root, key);
}
bool InsertR(const K& key)
{
return _InsertR(_root, key);
}
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
~BSTree()
{
_Destory(_root);
_root = nullptr;
}
BSTree(const BSTree<K>& t)
{
_root = Copy(t._root);
}
BSTree<K>& operator=(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}
private:
Node* _FindR(Node* root, const K& key)
{
if (root == nullptr)
{
return nullptr;
}
if (root->_key < key)
{
return _FindR(root->left, key);
}
else if (root->_key > key)
{
return _FindR(root->right, key);
}
else
{
return root;
}
}
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key < key)
{
return _InsertR(root->_right, key);//Reference aliases, no need to create an additional parent node variable
}
else if (root->_key > key)
{
return _InsertR(root->_left, key);
}
else
{
return false;
}
}
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key < key)
{
return _EraseR(root->_right, key);
}
else if (root->_key > key)
{
return _EraseR(root->_left, key);
}
else
{
if (root->_left == nullptr)
{
Node* del = root;
root = root->_right;
delete del;
}
else if (root->_right == nullptr)
{
Node* del = root;
root = root->_left;
delete del;
}
else
{
Node* minRight = root->_right;
while (minRight->_left)
{
minRight = minRight->_left;
}
K min = minRight->_key;
// Convert to the right subtree of root remove min
_EraseR(root->_right, min);
root->_key = min;
}
return true;
}
}
void _Destory(Node* root)
{
if (root == nullptr)
{
return;
}
_Destory(root->_left);
_Destory(root->_right);
delete root;
}
Node* Copy(Node* root)
{
if (root == nullptr)
{
return nullptr;
}
Node* copyNode = new Node(root->_key);
copyNode->_left = Copy(root->_left);
copyNode->_right = Copy(root->_right);
return copyNode;
}
Node* _root;
};
}4.(KV) recursive implementation of binary search tree
Search scene
- Buy a ticket and enter the station, you can rely on your ID card to check your information
- A simple Chinese-English translation dictionary
3. Count the number of occurrences of a text
namespace KV
{
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;
private:
// Returns false if the key already exists in the tree
bool _InsertR(Node*& root, const K& key, const V& value)
{
if (root == NULL) // insert
{
root = new Node(key, value);
return true;
}
if (root->_key < key)
{
return _InsertR(root->_right, key, value);
}
else if (root->_key > key)
{
return _InsertR(root->_left, key, value);
}
else
{
return false;
}
}
Node* _FindR(Node* root, const K& key)
{
if (root == nullptr)
{
return nullptr;
}
if (root->_key < key)
{
return _FindR(root->_right, key);
}
else if (root->_key > key)
{
return _FindR(root->_left, key);
}
else
{
return root;
}
}
// Returns false if the key does not exist in the tree
// exists, after deletion, returns true
bool _EraseR(Node*& root, const K& key)
{
if (root == NULL)
{
return false;
}
if (root->_key < key)
{
return _EraseR(root->_right, key);
}
else if (root->_key > key)
{
return _EraseR(root->_left, key);
}
else
{
// Found, root is the node to be deleted
if (root->_left == nullptr)
{
Node* del = root;
root = root->_right;
delete del;
}
else if (root->_right == nullptr)
{
Node* del = root;
root = root->_left;
delete del;
}
else
{
Node* minRight = root->_right;
while (minRight->_left)
{
minRight = minRight->_left;
}
K kmin = minRight->_key;
V vMin = minRight->_value;
// Convert to the right subtree of root remove min
_EraseR(root->_right, kmin);
root->_key = kmin;
root->_value = vMin;
}
return true;
}
}
void _Destory(Node* root)
{
if (root == NULL)
{
return;
}
_Destory(root->_left);
_Destory(root->_right);
delete root;
}
Node* _Copy(Node* root)
{
if (root == nullptr)
{
return nullptr;
}
Node* copyNode = new Node(root->_key, root->_value);
copyNode->_left = _Copy(root->_left);
copyNode->_right = _Copy(root->_right);
return copyNode;
}
public:
BSTree()
:_root(nullptr)
{}
BSTree(const BSTree<K, V>& t)
{
_root = _Copy(t._root);
}
// t1 = t2
BSTree<K, V>& operator=(BSTree<K, V> t)
{
swap(_root, t._root);
return *this;
}
~BSTree()
{
_Destory(_root);
_root = nullptr;
}
// Involving deep and shallow copying, you need to implement copy construction operator=, etc.
bool InsertR(const K& key, const V& value)
{
return _InsertR(_root, key, value);
}
Node* FindR(const K& key)
{
return _FindR(_root, key);
}
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << ":" << root->_value << endl;
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
Node* _root;
};
}