Table of Contents
Preface
1. Concept
2. Definition
Three, insert
1. Insertion situation
Situation one:
Situation two:
Situation three:
2. Rotation method
Method One: Left Single Rotation Method
Method 2: Right single rotation method
Method three: first left and then right double rotation method
Method 4: First right and then left double rotation method
Test (determine whether a tree is an AVL tree)
code show as below:
3. Random value case
Four, delete
Foreword
The two containers map and set have one thing in common:
The bottom layer is implemented according to the binary search tree, but the binary search tree has its own shortcomings. If the elements inserted into the tree are ordered or nearly ordered, the binary search tree will It will degenerate into a single tree, and the time complexity will degenerate into O(N). Therefore, the underlying structure of associative containers such as map and set balances binary trees, that is, using balanced trees.
Searching Binary Trees Please check this blog post: [C++] Searching the underlying implementation of binary trees_Huaguoshan~Programmer’s Blog-CSDN Blog
One, concept
Although the binary search tree can shorten the search efficiency, it
If the data is ordered or close to ordered, the binary search tree will degenerate into a single branch tree, and finding elements is equivalent to searching for elements in a sequence table, which is inefficient. Therefore, two Russian mathematicians, G.M. Adelson-Velskii and E.M. Landis, invented a method to solve the above problem in 1962:
When inserting a new node into the binary search tree, if it can be ensured that the absolute value of the difference between the heights of the left and right subtrees of each node does not exceed 1 (the nodes in the tree need to be adjusted), you can reduce the height of the tree, thereby reducing the average search length.
An AVL tree is either an empty tree or a binary search tree with the following properties:
1. Its left and right subtrees are both AVL trees
2. The absolute value of the difference between the heights of the left and right subtrees (referred to as the balance factor) does not exceed 1 (-1/0/1) (AVL trees are not necessarily implemented with balance factors)
If a binary search tree is highly balanced, it is an AVL tree. If it has n nodes, its height can be maintained at O(log_2 n), and the search time complexity is O(log_2 n).
Two, definition
To facilitate step-by-step learning, only the initial tree node definitions are shown here.
template <class K, class V>
classAVL_Data
{
public:
pair<K, V> _kv;
AVL_Data<K, V>* left = nullptr;
AVL_Data<K, V>* right = nullptr;
AVL_Data<K, V>* parent = nullptr;
int _bf = 0; // ballance factor
AVL_Data(const pair<K, V> & amp; p)
:_kv(p)
{}
};
The above definition will be improved and modified later.
三，insert
Based on the previous experience of searching binary trees, we can quickly write the insertion function, but the AVL tree is a special search binary tree, and we need to adjust the height of the tree. Then we will encounter three situations when inserting:
1. Insertion situation
Case 1:
Case 2:
Case 3:
The code is implemented as follows:
template <class K, class V>
classAVL_Tree
{
typedef AVL_Data<K, V> AVL_Data;
AVL_Data* root = nullptr;
public:
bool insert(const pair<K, V> & amp; p)
{
AVL_Data* new_a_d = new AVL_Data(p);
if (!root)
{
root = new_a_d;
}
else
{
AVL_Data* cur = root;
AVL_Data* parent = nullptr;
while (cur)
{
if (p.first < cur->_kv.first)
{
parent = cur;
cur = cur->left;
}
else if (p.first > cur->_kv.first)
{
parent = cur;
cur = cur->right;
}
else
{
delete(new_a_d); // Insertion failed, delete the new node
return false;
}
}
if (p.first < parent->_kv.first)
{
parent->left = new_a_d;
}
else
{
parent->right = new_a_d;
}
new_a_d->parent = parent;
cur = new_a_d;
//Complete insertion and balance
while (parent)
{ // Insert and modify parent balance factor
if (cur == parent->right)
{
parent->_bf + + ;
}
else
{
parent->_bf--;
}
// Determine whether the parent balance factor is 0. If it is not 0, you need to update the balance factor to the ancestor.
if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = parent->parent;
}
else if (parent->_bf == 0)
{
break;
}
else if(parent->_bf == 2 || parent->_bf == -2)
{
// When the absolute value is greater than 1, the purpose of the following code is to record the unmodified balance factor.
// Rotation processing is required, we will talk about this below
cur = parent;
parent = parent->parent;
}
else
{
// In other cases, the AVL tree itself is an abnormal AVL tree during insertion.
assert(false);
}
}
return true;
}
\t\t
}
};
2. Rotation method
Method 1: Single left rotation method
We take the following figure as an example. a, b, and c represent subtrees.
h represents the height of the subtree.
Please see the following scene:
h = 3, 4… There will be more combinations. It is meaningless to draw a picture here. The question is how do we solve the problem of losing balance? ?
Solved by the following methods:
Summarize:
1. If the right side is higher, rotate to the left.
2. Insertion occurs in the C-tree, the balance factor changes, and then rotation occurs.
void RotateL(AVL_Data* parent)
{
assert(parent->right);
AVL_Data* par = parent;
AVL_Data* par_R = par->right;
AVL_Data* par_RL = par->right->left;
AVL_Data* ppnode = par->parent;
par->right = par_RL;
if(par_RL)
par_RL->parent = par;
par_R->left = par;
par->parent = par_R;
par_R->parent = ppnode;
if (!ppnode)
{
root = par_R;
}
else if (ppnode->left == par)
{
ppnode->left = par_R;
}
else
{
ppnode->right = par_R;
}
\t\t
par->_bf = 0;
par_R->_bf = 0;
}
//Experimental example
AVL_Tree<int, string> tree;
tree.insert(make_pair(30, "李思"));
tree.insert(make_pair(20, "二马子"));
tree.insert(make_pair(60, "Zhang San"));
tree.insert(make_pair(45, "王五"));
tree.insert(make_pair(75, "王五"));
tree.insert(make_pair(65, "王五"));
Method 2: Right-handed single-rotation method
The idea is similar to the left-handed method, but the image is the opposite. Here we only give the scene solution template:
Scenarios where h = 0, 1, 2:
After learning method one, you will naturally understand method two:
void RotateR(AVL_Data* parent)
{
assert(parent->left);
AVL_Data* par = parent;
AVL_Data* par_L = par->left;
AVL_Data* par_LR = par->left->right;
AVL_Data* ppnode = par->parent;
par->left = par_LR;
if(par_LR)
par_LR->parent = par;
par_L->right = par;
par->parent = par_L;
par_L->parent = ppnode;
if (!ppnode)
{
root = par_L;
}
else if (ppnode->left == par)
{
ppnode->left = par_L;
}
else
{
ppnode->right = par_L;
}
par->_bf = 0;
par_L->_bf = 0;
}
Method 3: Double spin left and then right
Like single rotation, we first show the scenario where left and right double rotation processing is required when h = 0, 1, 2.
The process of changing the steps of the double spin method is as follows:
Judging from the results, the position of 60 is pushed up and placed at the “root”.
code show as below:
void RotateLR(AVL_Data* parent)
{
assert(parent->left);
AVL_Data* par = parent;
AVL_Data* par_L = par->left;
AVL_Data* par_LR = par->left->right;
AVL_Data* ppnode = par->parent;
int par_LR_bf = par_LR->_bf;
RotateL(par_L);
RotateR(par);
if (par_LR_bf == -1)
{
par->_bf = 1;
par_L->_bf = 0;
}
else if (par_LR_bf == 1)
{
par->_bf = 0;
par_L->_bf = -1;
}
else if (par_LR_bf == 0)
{
par->_bf = 0;
par_L->_bf = 0;
}
else
{
assert(false);
}
par_LR->_bf = 0;
}
// Test Case
void Test_insert_L()
{
AVL_Tree<int, string> tree;
tree.insert(make_pair(90, "李思"));
tree.insert(make_pair(30, "二马子"));
tree.insert(make_pair(100, "Zhang San"));
tree.insert(make_pair(25, "王五"));
tree.insert(make_pair(60, "王五"));
tree.insert(make_pair(50, "王五"));
}
Method 4: First right and then left double rotation method
After we learn the third method, we can just follow the gourd and draw the scoop.
Each scene:
Code:
void RotateRL(AVL_Data* parent)
{
assert(parent->right);
AVL_Data* par = parent;
AVL_Data* par_R = par->right;
AVL_Data* par_RL = par->right->left;
AVL_Data* ppnode = par->parent;
int par_RL_bf = par_RL->_bf;
RotateR(par_R);
RotateL(par);
if (par_RL_bf == -1)
{
par->_bf = 0;
par_R->_bf = 1;
}
else if (par_RL_bf == 1)
{
par->_bf = -1;
par_R->_bf = 0;
}
else if (par_RL_bf == 0)
{
par->_bf = 0;
par_R->_bf = 0;
}
else
{
assert(false);
}
par_RL->_bf = 0;
}
// Test Case
void Test_insert_L()
{
AVL_Tree<int, string> tree;
tree.insert(make_pair(30, "李思"));
tree.insert(make_pair(20, "二马子"));
tree.insert(make_pair(90, "Zhang San"));
tree.insert(make_pair(15, "王五"));
tree.insert(make_pair(60, "王五"));
tree.insert(make_pair(100, "王五"));
tree.insert(make_pair(55, "王五"));
tree.insert(make_pair(67, "王五"));
tree.insert(make_pair(95, "王五"));
tree.insert(make_pair(50, "王五"));
}
Test (to determine whether a tree is an AVL tree)
Idea:
1. Check the height (every subtree in AVL is an AVL tree).
2. Check whether the balance factor is correct.
The code is as follows:
int Hight(const AVL_Data* root)
{
if (root == nullptr)
return 0;
int left_H = Hight(root->left);
int left_R = Hight(root->right);
return left_H >= left_R ? left_H + 1 : left_R + 1;
}
bool B_balance()
{
return _B_balance(root);
}
\t
bool _B_balance(const AVL_Data* root)
{
if (root == nullptr)
return true;
int left_root = Hight(root->left);
int right_root = Hight(root->right);
if ((right_root - left_root) != root->_bf) // Use Hight to judge the balance factor
return false;
return abs(left_root - right_root) < 2 & amp; & amp; _B_balance(root->left) & amp; & amp; _B_balance(root->right);
}
3. Random value case
If you run this code a few times, you can almost traverse all environments.
void Random_Test()
{
srand(time(0));
const size_t N = 10000000;
AVL_Tree<int, int> t;
for (size_t i = 0; i < N; i + + )
{
size_t x = rand();
t.insert(make_pair(x, x));
}
cout << t.B_balance() << endl;
}
Come and test your own code
insert full code
bool insert(const pair<K, V> & amp; p)
{
AVL_Data* new_a_d = new AVL_Data(p);
if (!root)
{
root = new_a_d;
}
else
{
AVL_Data* cur = root;
AVL_Data* parent = nullptr;
while (cur)
{
if (p.first < cur->_kv.first)
{
parent = cur;
cur = cur->left;
}
else if (p.first > cur->_kv.first)
{
parent = cur;
cur = cur->right;
}
else
{
delete(new_a_d); // Insertion failed, delete the new node
return false;
}
}
if (p.first < parent->_kv.first)
{
parent->left = new_a_d;
}
else
{
parent->right = new_a_d;
}
new_a_d->parent = parent;
cur = new_a_d;
//Complete insertion and balance
while (parent)
{ // Insert and modify parent balance factor
if (cur == parent->right)
{
parent->_bf + + ;
}
else
{
parent->_bf--;
}
// Determine whether the parent balance factor is 0. If it is not 0, you need to update the balance factor to the ancestor.
if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = parent->parent;
}
else if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == -2 || parent->_bf == 2)
{
if (parent->_bf == 2 & amp; & amp; cur->_bf == 1)
{
RotateL(parent);
// cout << "RotateL" << endl;
}
else if (parent->_bf == -2 & amp; & amp; cur->_bf == -1)
{
RotateR(parent);
// cout << "RotateR" << endl;
}
else if (parent->_bf == -2 & amp; & amp; cur->_bf == 1)
{
RotateLR(parent);
// cout << "RotateLR" << endl;
}
else if (parent->_bf == 2 & amp; & amp; cur->_bf == -1)
{
RotateRL(parent);
// cout << "RotateRL" << endl;
}
else
{
// In other cases, the AVL tree itself is an abnormal AVL tree during insertion.
//The problem occurs in the rotation method
assert(false);
}
break;
}
else
{
assert(false);
}
}
return true;
}
}
Four, delete
Because the AVL tree is also a binary search tree, you can delete the node according to the binary search tree method, and then update the balance factor. However, if it is different from the deletion, the balance factor will be updated after the node is deleted. In the worst case, it will always need to be adjusted. to the location of the root node. For specific implementation, students can refer to “Introduction to Algorithms” or “Data Structure – Description Using Object-Oriented Methods and C++” Yin Renkun edition.
Next issue preview: Red and black trees! ! !
Conclusion
That’s it for this section. Thank you for browsing. If you have any suggestions, please leave them in the comment area. If you bring something to your friends, please leave a like.Your likes and attention will be It will become a motivation for bloggers to create.
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57034 people are learning the system