Data structure: implementation and full diagram of AVL tree

Article directory

• Why have AVL trees?
• What is an AVL tree
• Implementation of AVL tree
• • Insertion of elements
  • Balance factor update
  • Rotation of AVL tree
• AVL tree inspection
• Complete implementation

This article summarizes all the contents in the AVL tree, with detailed illustrations of the process.

Why there is an AVL tree

We gave a brief introduction to map/multimap/set/multiset earlier. In its documentation, we found that these containers have one thing in common: their bottom layers are based on binary search trees. Implemented, but the binary search tree has its own flaws. If the elements inserted into the tree are ordered or close to ordered, the binary search tree will degenerate into a single tree, and the time complexity will degenerate into O (N), so the underlying structure of associative containers such as map and set balances binary trees, that is, using balanced trees.

What is an AVL tree

When a binary search tree is shaped like the following scenario, the search efficiency will be quite low.

Even when it is close to a single-branch tree, the search efficiency will be equivalent to the search efficiency in the sequence table, so the Russian mathematicians G.M. Adelson-Velskii and E.M. Landis invented I came up with a solution: 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 (it needs to be updated in the tree By adjusting the nodes), you can reduce the height of the tree, thereby reducing the average search length. This is the origin of the AVL tree.

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 does not exceed 1

The height difference between the left and right subtrees is also called the balance factor. The time complexity of searching in such a tree is O(logN)

Implementation of AVL tree

Insertion of elements

First define the node. Since the AVL tree has a need to search for information upwards, when defining the node information, there must be a pointer to the parent of the node.

// Define the nodes of the AVL tree
template<class K, class V>
structAVLTreeNode
{<!-- -->
AVLTreeNode(const pair<K, V> & amp; kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(val)
, bf(0)
{<!-- -->}
// Left subtree pointer, right subtree pointer, parent node pointer, node value, balance factor
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
pair<K, V> _kv;
int bf;
};

The following defines the insertion of AVL tree. The insertion of AVL tree is mainly inserted into a binary search tree first, and then the binary search tree is balanced, so it must be inserted first to binary search tree

bool Insert(const pair<K, V> kv)
{<!-- -->
Node* newnode = new Node(kv);

if (_root == nullptr)
{<!-- -->
_root = newnode;
return true;
}

Node* cur = _root;
Node* parent = nullptr;

while (cur)
{<!-- -->
if (newnode->_kv.first > cur->_kv.first)
{<!-- -->
parent = cur;
cur = cur->_left;
}
else if (newnode->_kv.first < cur->_kv.first)
{<!-- -->
parent = cur;
cur = cur->_right;
}
else
{<!-- -->
return false;
}
}
if (newnode->_kv.first > parent->_kv.first)
{<!-- -->
parent->_right = newnode;
cur->_parent = parent;
}
else
{<!-- -->
parent->_left = newnode;
cur->_parent = parent;
}
}

The above is the basic part of the binary search tree. Next is the AVL tree balancing problem.

Update of balance factors

After a new node is inserted, the balance of the AVL tree may be destroyed. This is the significance of introducing the balance factor. Therefore, the first step after the insertion is to update the balance factor to see if it has been damaged. to damage, the adjustment of the balance factor has the following situations:

1. If inserted to the left side of the node, the balance factor is -1
2. If inserted to the right of the node, the balance factor + 1 is enough

There will be new problems after the node is inserted. See the following scenario.

Based on this principle, code can be written to update the balance factor

 // Insertion of nodes
// The logic of node insertion is basically the same as that of the search tree, except that it needs to be rotated if it does not meet the requirements.
bool Insert(const pair<K, V> kv)
{<!-- -->
Node* newnode = new Node(kv);

if (_root == nullptr)
{<!-- -->
_root = newnode;
return true;
}

Node* cur = _root;
Node* parent = nullptr;

while (cur)
{<!-- -->
if (newnode->_kv.first > cur->_kv.first)
{<!-- -->
parent = cur;
cur = cur->_left;
}
else if (newnode->_kv.first < cur->_kv.first)
{<!-- -->
parent = cur;
cur = cur->_right;
}
else
{<!-- -->
return false;
}
}
if (newnode->_kv.first > parent->_kv.first)
{<!-- -->
parent->_right = newnode;
cur->_parent = parent;
}
else
{<!-- -->
parent->_left = newnode;
cur->_parent = parent;
}

//The above is the basic part of the binary search tree, and the balance factor is updated below.
while (parent)
{<!-- -->
// If cur is the left node of parent, the balance factor is -1, if it is the right node, the balance factor + 1
if (cur == parent->_left)
{<!-- -->
parent->_bf--;
}
else
{<!-- -->
parent->_bf + + ;
}

// Determine the absolute value of the parent node's balance factor:
// 1. If it is 0, it proves that no upward update is needed
// 2. If it is 1, it needs to be updated upwards
// 3. If it is 2, rotation is required
if (parent->_bf == 0)
{<!-- -->
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{<!-- -->
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{<!-- -->
// Start rotating
}
else
{<!-- -->
// If the absolute value is greater than 2, it means that the balance factor is wrong and the end is forced.
assert(false);
}
}
}

AVL tree rotation

When the above situation has occurred, how should the AVL tree be balanced? This introduces the concept of rotation

In the AVL tree, when the balance of the AVL tree is destroyed, there are a total of four rotations that will be caused

1. The new node is inserted to the left side of the higher left subtree, causing a right single rotation

Therefore, the following code implementation implements right-handed rotation:

 // Right single rotation
void RotateR(Node* parent)
{<!-- -->
Node* subL = parent->_left;
Node* subLR = subL->_right;

parent->_left = subLR;
if(subLR)
subLR->_parent = parent;

Node* parentParent = parent->_parent;

subL->_right = parent;
parent->_parent = subL;

if (_root == parent)
{<!-- -->
_root = subL;
subL->_parent = nullptr;
}
else
{<!-- -->
if (parentParent->_left == parent)
{<!-- -->
parentParent->_left = subL;
}
else
{<!-- -->
parentParent->_right = subL;
}

subL->_parent = parentParent;
}

subL->_bf = parent->_bf = 0;
}

2. The new node is inserted on the right side of the higher right subtree, causing a single left rotation

 // Single left rotation
void RotateL(Node* parent)
{<!-- -->
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;

//Update node
parent->_right = subRL;
parent->_parent = subR;

subR->_left = parent;
subR->_parent = parentParent;
if(subRL)
subRL->_parent = parent;

// update parentParent
if (_root == parent)
{<!-- -->
_root = subR;
}
else
{<!-- -->
if (parentParent->_left == parent)
{<!-- -->
parentParent->_left = subR;
}
else
{<!-- -->
parentParent->_right = subR;
}
}

parent->_bf = subR->_bf = 0;
}

3. The new node is inserted to the left side of the higher right subtree, causing a right single rotation and then a left single rotation

For this situation, there are a total of the following two situations:

There is also an idea for code implementation. First rotate left and then rotate right, and finally modify the value of the balance factor. To modify the value of the balance factor, you can use bf of subRL Values can be used to judge different situations, and different values can be modified according to different situations.

 // First rotate right and then rotate left
void RotateRL(Node* parent)
{<!-- -->
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;

RotateR(subR);
RotateL(parent);

if (bf == 0)
{<!-- -->
// Itself is the newly added node
parent->_bf = subR->_bf = 0;
}
else if (bf == -1)
{<!-- -->
// Insertion in left subtree
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else if (bf == 1)
{<!-- -->
// Insertion in right subtree
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = -1;
}
else
{<!-- -->
assert(false);
}
}

4. The new node is inserted to the right of the higher left subtree, causing a single left rotation and then a single right rotation

The analysis method is similar to the previous one

 // First perform left single rotation, then perform right single rotation
void RotateLR(Node* parent)
{<!-- -->
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;

RotateL(subL);
RotateR(parent);

// Replace the balance factor
if (bf == 0)
{<!-- -->
subL->_bf = subLR->_bf = 0;
}
else if (bf == 1)
{<!-- -->
//Insert in the right subtree
subL->_bf = -1;
subLR->_bf = 0;
parent->_bf = 0;
}
else if (bf == -1)
{<!-- -->
//Insert in left subtree
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{<!-- -->
assert(false);
}
}

AVL tree inspection

Based on the above implementation, the AVL tree can be basically realized. How to verify whether the AVL tree is correct? In fact, the verification is also very simple. You only need to check whether the balance factor of each node is equal to the value of the corresponding right subtree minus the left subtree.

 // Used to check the height of the tree
int TreeHeight(Node* root)
{<!-- -->
if (root == nullptr)
return 0;

int leftheight = TreeHeight(root->_left);
int rightheight = TreeHeight(root->_right);

return max(leftheight, rightheight) + 1;
}

// Keep the tree encapsulated and check the AVL tree
boolIsBalance()
{<!-- -->
return _IsBalance(root);
}

// Check the AVL tree
bool _IsBalance(Node* root)
{<!-- -->
if (root == nullptr)
return true;

int leftheight = TreeHeight(root->_left);
int rightheight = TreeHeight(root->_right);

if (rightheight - leftheight != root->_bf)
return false;

return abs(rightheight-leftheight)<2 & amp; & amp; _IsBalance(root->_left) & amp; & amp; _IsBalance(root->_right);
}

This completes the test of the AVL tree

Complete implementation

#include <iostream>
#include <assert.h>
using namespace std;

// Define the nodes of the AVL tree
template<class K, class V>
structAVLTreeNode
{<!-- -->
AVLTreeNode(const pair<K, V> & amp; kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{<!-- -->}
// Left subtree pointer, right subtree pointer, parent node pointer, node value, balance factor
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
pair<K, V> _kv;
int _bf;
};

//Define AVL tree
template<class K, class V>
classAVLTree
{<!-- -->
typedef AVLTreeNode<K, V> Node;
public:
AVLTree()
:_root(nullptr)
{<!-- -->}

// Insertion of nodes
// The logic of node insertion is basically the same as that of the search tree, except that it needs to be rotated if it does not meet the requirements.
bool Insert(const pair<K, V> kv)
{<!-- -->
if (_root == nullptr)
{<!-- -->
_root = new Node(kv);
return true;
}

Node* cur = _root;
Node* parent = nullptr;

while (cur)
{<!-- -->
if (kv.first > cur->_kv.first)
{<!-- -->
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_kv.first)
{<!-- -->
parent = cur;
cur = cur->_left;
}
else
{<!-- -->
return false;
}
}
cur = new Node(kv);
if (kv.first > parent->_kv.first)
{<!-- -->
parent->_right = cur;
cur->_parent = parent;
}
else
{<!-- -->
parent->_left = cur;
cur->_parent = parent;
}

//The above is the basic part of the binary search tree, and the balance factor is updated below.
while (parent)
{<!-- -->
// If cur is the left node of parent, the balance factor is -1, if it is the right node, the balance factor + 1
if (cur == parent->_left)
{<!-- -->
parent->_bf--;
}
else
{<!-- -->
parent->_bf + + ;
}

// Determine the absolute value of the parent node's balance factor:
// 1. If it is 0, it proves that no upward update is needed
// 2. If it is 1, it needs to be updated upwards
// 3. If it is 2, rotation is required
if (parent->_bf == 0)
{<!-- -->
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{<!-- -->
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{<!-- -->
// Start rotating
if (parent->_bf == 2 & amp; & amp; cur->_bf == 1)
{<!-- -->
RotateL(parent);
}
else if (parent->_bf == -2 & amp; & amp; cur->_bf == -1)
{<!-- -->
RotateR(parent);
}
else if (parent->_bf == 2 & amp; & amp; cur->_bf == -1)
{<!-- -->
RotateRL(parent);
}
else if (parent->_bf == -2 & amp; & amp; cur->_bf == 1)
{<!-- -->
RotateLR(parent);
}

break;
}
else
{<!-- -->
// If the absolute value is greater than 2, it means that the balance factor is wrong and the end is forced.
assert(false);
}
}
return true;
}

// right single rotation
void RotateR(Node* parent)
{<!-- -->
Node* subL = parent->_left;
Node* subLR = subL->_right;

parent->_left = subLR;
if(subLR)
subLR->_parent = parent;

Node* parentParent = parent->_parent;

subL->_right = parent;
parent->_parent = subL;

if (_root == parent)
{<!-- -->
_root = subL;
subL->_parent = nullptr;
}
else
{<!-- -->
if (parentParent->_left == parent)
{<!-- -->
parentParent->_left = subL;
}
else
{<!-- -->
parentParent->_right = subL;
}

subL->_parent = parentParent;
}

subL->_bf = parent->_bf = 0;
}

// left single rotation
void RotateL(Node* parent)
{<!-- -->
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;

//Update node
parent->_right = subRL;
parent->_parent = subR;

subR->_left = parent;
subR->_parent = parentParent;
if(subRL)
subRL->_parent = parent;

// update parentParent
if (_root == parent)
{<!-- -->
_root = subR;
}
else
{<!-- -->
if (parentParent->_left == parent)
{<!-- -->
parentParent->_left = subR;
}
else
{<!-- -->
parentParent->_right = subR;
}
}

parent->_bf = subR->_bf = 0;
}

// First rotate right and then rotate left
void RotateRL(Node* parent)
{<!-- -->
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;

RotateR(subR);
RotateL(parent);

if (bf == 0)
{<!-- -->
// Itself is the newly added node
parent->_bf = subR->_bf = 0;
}
else if (bf == -1)
{<!-- -->
// Insertion in left subtree
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else if (bf == 1)
{<!-- -->
// Insertion in right subtree
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = -1;
}
else
{<!-- -->
assert(false);
}
}

// First perform left single rotation, then perform right single rotation
void RotateLR(Node* parent)
{<!-- -->
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;

RotateL(subL);
RotateR(parent);

// Replace the balance factor
if (bf == 0)
{<!-- -->
subL->_bf = subLR->_bf = 0;
}
else if (bf == 1)
{<!-- -->
//Insert in the right subtree
subL->_bf = -1;
subLR->_bf = 0;
parent->_bf = 0;
}
else if (bf == -1)
{<!-- -->
//Insert in left subtree
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{<!-- -->
assert(false);
}
}

// Used to check the height of the tree
int TreeHeight(Node* root)
{<!-- -->
if (root == nullptr)
return 0;

int leftheight = TreeHeight(root->_left);
int rightheight = TreeHeight(root->_right);

return max(leftheight, rightheight) + 1;
}

// Keep the tree encapsulated and check the AVL tree
boolIsBalance()
{<!-- -->
return _IsBalance(root);
}

// Check the AVL tree
bool _IsBalance(Node* root)
{<!-- -->
if (root == nullptr)
return true;

int leftheight = TreeHeight(root->_left);
int rightheight = TreeHeight(root->_right);

if (rightheight - leftheight != root->_bf)
return false;

return abs(rightheight-leftheight)<2 & amp; & amp; _IsBalance(root->_left) & amp; & amp; _IsBalance(root->_right);
}

private:
Node* _root;
};