当前位置:网站首页>The concept, implementation and analysis of binary search tree (BST)
The concept, implementation and analysis of binary search tree (BST)
2022-07-07 11:06:00 【Exy-】
Catalog
BST The deletion of ( important )
Binary search tree
Concept
Binary search tree is also called binary sort tree , It could be an empty tree , Or a binary tree with the following properties :
- If its left subtree is not empty , Then the values of all nodes on the left subtree are smaller than the values of the root nodes
- If its right subtree is not empty , Then the value of all nodes on the right subtree is greater than the value of the root node
- Its left and right subtrees are also binary search trees
int ar[]={5,3,2,4,8,9,1};
BST Insertion of trees
- If the tree is empty, it will be inserted directly ;
- If it's not empty , Then insert according to the rules of binary search tree .
bool Insert(const K& key, const V& value)
{
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
Node* cur = _root;
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
{
return false;
}
}
cur = new Node(key, value);
if (cur->_key > parent->_key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
BST Tree search
If the root node _root->_key== You're looking for key Return the found node
If the root node _root->_key> You're looking for key Look on its left sub tree
If the root node _root->_key< You're looking for key Look on its right subtree
If the root node does not exist , Return null pointer
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;
}
BST The deletion of ( important )
First of all, according to the key Find nodes , No return found false;
There are three cases of deletion
1. The left subtree of the node to be deleted is empty
- The root node to delete , Let the root be equal to the right child node
- The left child node that is an ordinary node and its parent node to be deleted is parent->_left = cur->_right
- The right child node that is an ordinary node and its parent node to be deleted is parent->_right= cur->_right
2. The right subtree of the node to be deleted is empty
- The root node to delete , Let the root be equal to the left child node
- The left child node that is an ordinary node and its parent node to be deleted is parent->_left = cur->_left;
- The left child node that is an ordinary node and its parent node to be deleted is parent->_right = cur->_left;
3. The left and right child nodes of the deleted node are not empty :
We use the substitution method here
Find the largest node of the left subtree ( The most right ) Or the smallest node of the right subtree
The code is as follows :
bool Erase(const K& key)
{
//1. Looking for nodes
Node* cur = _root;
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
{
if (cur->_left == nullptr)
{
if (parent == nullptr)// The root node to delete
{
_root = cur->_right;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (parent == nullptr)
{
_root = cur->_left;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
{
// The substitution method deletes The largest node of the left tree ( The rightmost node ) Or the smallest node of the right tree ( Leftmost node )
Node* Parent = cur; // Be careful not to initialize null
Node* minNode = cur->_right;
while (minNode->_left)
{
Parent = minNode;
minNode = minNode->_left;
}
swap(cur->_key, minNode->_key);
// Convert to delete minNode
// because minNode As an empty node , You can delete
if (Parent->_right == minNode)
Parent->_right = minNode->_right;
else
Parent->_left = minNode->_right;
delete minNode;
}
return true;
}
}
return false;
}
application
according to BST We can realize the characteristics of trees
Performance analysis
边栏推荐
- Those confusing concepts (3): function and class
- VR development optimization
- [untitled]
- The sixth training assignment
- July 10, 2022 "five heart public welfare" activity notice + registration entry (two-dimensional code)
- Operation method of Orange Pie orangepi 4 lts development board connecting SATA hard disk through mini PCIe
- 软考中级有用吗??
- Unity websocket server
- I plan to take part in security work. How about information security engineers and how to prepare for the soft exam?
- POJ1821 Fence 题解报告
猜你喜欢
[untitled]
2021-05-21
[machine learning 03] Lagrange multiplier method
CSAPP bomb lab parsing
Transaction rolled back because it has been marked as rollback only
[installation system] U disk installation system tutorial, using UltraISO to make U disk startup disk
【推薦系統 01】Rechub
Network engineer test questions and answers in May of the first half of 2022
seata 1.3.0 四种模式解决分布式事务(AT、TCC、SAGA、XA)
[actual combat] transformer architecture of the major medical segmentation challenges on the list --nnformer
随机推荐
The sixth training assignment
How to prepare for the advanced soft test (network planning designer)?
Basic introduction of yarn and job submission process
Simple and easy to modify spring frame components
软考中级,软件设计师考试那些内容,考试大纲什么的?
Mendeley -- a free document management tool that automatically inserts references into papers
[recommendation system 01] rechub
How much review time does it usually take to take the intermediate soft exam?
BUUCTF---Reverse---reverse1
中级软件评测师考什么
JS implementation chain call
2022.7.3DAY595
简单易修改的弹框组件
[untitled]
Operation method of Orange Pie orangepi 4 lts development board connecting SATA hard disk through mini PCIe
When do you usually get grades in the soft exam? Online pedaling?
Project ERROR: Unknown module(s) in QT: core gui
Unity determines whether the mouse clicks on the UI
2022年上半年5月网络工程师试题及答案
Deconstruction and assignment of variables