Do you think IIT Guwahati certified course can help you in your career?
Introduction
This article will teach to solve a question where the question is related to AVL tree. The AVL Tree is a height-balanced binary search tree in which each node's balance factor is computed by subtracting the right sub-height tree's from the left sub-height. The tree's
The tree is considered to be balanced if the balance factor of each node is between -1 and 1; otherwise, the tree is imbalanced and must be balanced.
What does duplicate key in AVL tree mean?
It means inserting a key whose value (key node) already exists in the AVL tree.
When a key is duplicated, we don't make a new node for the inserted node; instead, we increase the repetition of an existing node. This procedure does not result in the creation of duplicate node memory. As a result, we'll need to change the way we insert and delete the AVL tree. Who is in charge of this duplicate key?
Understand the question
This is to add a count field to the AVL tree node, along with usual fields like key, left and right pointers.
Inserting keys 12, 10, 20, 9, 11, 10, 12, 12 into an empty Binary Search Tree results in the following.
C++ Implementation
#include <iostream>
using namespace std;
class LinkNode
{
public:
int key;
int Total_height;
int occurrence;
LinkNode *left;
LinkNode *right;
LinkNode(int key)
{
// Set node value of avl tree
this->key = key;
this->Total_height = 1;
this->occurrence = 1;
this->left = nullptr;
this->right = nullptr;
}
};
class Avl_Tree
{
public:
LinkNode *root;
Avl_Tree()
{
this->root = nullptr;
}
// Get the Total_height of given node
int getTotal_height(LinkNode *node)
{
if (node == nullptr)
{
return 0;
}
return node->Total_height;
}
// Get the max value of given two numbers
int maxTotal_height(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Perform the Right rotate operation
LinkNode *rightRotate(LinkNode *node)
{
// Get left child node
LinkNode *x = node->left;
// Get left node right subtree
LinkNode *subtree = x->right;
// Update the left and right subtree
x->right = node;
node->left = subtree;
// Change the Total_height of modified node
node->Total_height = this->maxTotal_height(
this->getTotal_height(node->left),
this->getTotal_height(node->right)
) + 1;
x->Total_height = this->maxTotal_height(
this->getTotal_height(x->left),
this->getTotal_height(x->right)
) + 1;
return x;
}
// Perform the Left Rotate operation
LinkNode *leftRotate(LinkNode *node)
{
// Get right child node
LinkNode *x = node->right;
// Get right node left subtree
LinkNode *subtree = x->left;
// Update the left and right subtree
x->left = node;
node->right = subtree;
// Change the Total_height of modified node
node->Total_height = this->maxTotal_height(
this->getTotal_height(node->left),
this->getHeight(node->right)
) + 1;
x->Total_height = this->maxTotal_height(
this->getTotal_height(x->left),
this->getTotal_height(x->right)
) + 1;
return x;
}
// Get the balance factor
int getBalanceFactor(LinkNode *node)
{
if (node == nullptr)
{
return 0;
}
return this->getTotal_height(node->left) -
this->getTotal_height(node->right);
}
// Recursively, add a node in AVL tree
// Duplicate keys (key) are allowed
LinkNode *addNode(LinkNode *node, int key)
{
if (node == nullptr)
{
// Return a new node
return new LinkNode(key);
}
if (key < node->key)
{
node->left = this->addNode(node->left, key);
}
else if (key > node->key)
{
node->right = this->addNode(node->right, key);
}
else
{
// When given key already exists
node->occurrence = node->occurrence + 1;
return node;
}
// Change the Total_height of current node
node->Total_height = 1 + this->maxTotal_height(
this->getTotal_height(node->left),
this->getTotal_height(node->right)
);
// Get balance factor of a node
int factor = this->getBalanceFactor(node);
if (factor > 1 && key < node->left->key)
{
return this->rightRotate(node);
}
if (factor < -1 && key > node->right->key)
{
return this->leftRotate(node);
}
if (factor > 1 && key > node->left->key)
{
node->left = this->leftRotate(node->left);
return this->rightRotate(node);
}
if (factor < -1 && key < node->right->key)
{
node->right = this->rightRotate(node->right);
return this->leftRotate(node);
}
return node;
}
// Print avl tree in preorder traversal
void preorder(LinkNode *node)
{
if (node != nullptr)
{
cout << " " << node->key << "("
<< node->occurrence << ")";
this->preorder(node->left);
this->preorder(node->right);
}
}
// Find the minimum node on left side
LinkNode *minKeyNode(LinkNode *node)
{
LinkNode *result = node;
while (result->left != nullptr)
{
result = result->left;
}
return result;
}
// Delete given node key(key) in AVL tree
LinkNode *deleteNode(LinkNode *node, int key)
{
if (node == nullptr)
{
return node;
}
// When deleted nodes are possible in left subtree
if (key < node->key)
{
node->left = this->deleteNode(node->left, key);
}
else if (key > node->key)
{
node->right = this->deleteNode(node->right, key);
}
else
{
if (node->occurrence > 1)
{
node->occurrence--;
return node;
}
LinkNode *temp = nullptr;
// When deleted node is current node
if ((node->left == nullptr) ||
(node->right == nullptr))
{
if (node->left != nullptr)
{
// When left subtree are exists
temp = node->left;
}
else if (node->right != nullptr)
{
// When left subtree are exists
temp = node->right;
}
if (temp == nullptr)
{
// When delete leaf node
// Get deleted node
temp = node;
// In this case set the current
// node value to zero
node = nullptr;
}
else
{
// One child case
node = temp;
}
// free the deleted node
delete temp;
temp = nullptr;
}
else
{
// When left and right both subtree exists
// Find inorder successor
temp = this->minKeyNode(node->right);
// Set new value to current node
node->key = temp->key;
// Delete smallest element in find node
// Goal to delete leaf node
node->right = this->deleteNode(node->right,
temp->key);
}
}
// If the tree had only one node then return
if (node == nullptr)
{
return node;
}
// Set Total_height of current node
node->Total_height = 1 + this->maxTotal_height(
this->getTotal_height(node->left),
this->getTotal_height(node->right)
);
// Get balance factor
int balance = this->getBalanceFactor(node);
// Transform into a balanced avl tree
// 4 possible situation
if (balance > 1 &&
this->getBalanceFactor(node->left) >= 0)
{
return this->rightRotate(node);
}
if (balance > 1 &&
this->getBalanceFactor(node->left) < 0)
{
node->left = this->leftRotate(node->left);
return this->rightRotate(node);
}
if (balance < -1 &&
this->getBalanceFactor(node->right) <= 0)
{
return this->leftRotate(node);
}
if (balance < -1 &&
this->getBalanceFactor(node->right) > 0)
{
node->right = this->rightRotate(node->right);
return this->leftRotate(node);
}
return node;
}
// Check that whether given key node is exist in given tree
bool isNodeExist(LinkNode *node, int key)
{
if (node == nullptr)
{
return false;
}
else
{
if (node->key == key)
{
// When node is exist
return true;
}
return (this->isNodeExist(node->left, key) ||
this->isNodeExist(node->right, key));
}
}
// This is handling the request of deleted node in AVL
void deleteKeyNode(int key)
{
if (this->root != nullptr &&
this->isNodeExist(this->root, key) == true)
{
cout << "\n Before Delete node "
<< key << " element" << endl;
this->preorder(this->root);
this->root = this->deleteNode(this->root, key);
cout << "\n After Delete node "
<< key << " element" << endl;
this->preorder(this->root);
}
else
{
cout << "\n Deleted node " << key << " is not found";
this->preorder(this->root);
}
}
};
int main()
{
Avl_Tree *tree = new Avl_Tree();
// Add tree node
tree->root = tree->addNode(tree->root, 12);
tree->root = tree->addNode(tree->root, 7);
tree->root = tree->addNode(tree->root, 5);
tree->root = tree->addNode(tree->root, 19);
tree->root = tree->addNode(tree->root, 17);
tree->root = tree->addNode(tree->root, 13);
tree->root = tree->addNode(tree->root, 11);
tree->root = tree->addNode(tree->root, 3);
tree->root = tree->addNode(tree->root, 2);
tree->root = tree->addNode(tree->root, 7);
/*
Resultant AVL Tree
-----------------
12
/ \
/ \
(2)7 17
/ \ / \
3 11 13 19
/ \
2 5
*/
tree->deleteKeyNode(7);
/*
After delete node 7
-----------------
12
/ \
/ \
(1)7 17
/ \ / \
3 11 13 19
/ \
2 5
*/
tree->deleteKeyNode(11);
/*
After delete node 11
- ----------------
12
/ \
/ \
7 17
/ \ / \
3 11 13 19
/ \
2 5
//remove node
12
/ \
/ \
7 17
/ / \
3 13 19
/ \
2 5
// Balance the AVL tree
12
/ \
/ \
3 17
/ \ / \
2 7 13 19
/
5
*/
return 0;
}
You can also try this code with Online C++ Compiler
Before Delete node 7 element
12(1) 7(2) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 7 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
Before Delete node 11 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 11 element
12(1) 3(1) 2(1) 7(1) 5(1) 17(1) 13(1) 19(1)
Time Complexity:
O(N) Where ‘N’ stands for length of the Linked list.
Reason: O(N) time, this is because we have to iterate from start to end. The program deletes N nodes after skipping M nodes in the linked list. Begin with the next node on the list and work your way down, eliminating N nodes at a time.
Auxiliary Space Complexity:
O(1)
Reason: Here we have used a pre-defined data structure from the collection. As a function of input attributes, the amount of memory space required to solve an instance of the computational problem is set to one.
Because they are more precisely balanced, AVL trees give faster lookups than Red Black Trees. 2. In this case, the node's colour is either Red or Black. The node has no colour in this case.
Why is it that in a doubly-linked list, deletion is faster?
In other words, if you know which cell you want to remove ahead of time, a doubly-linked list allows you to do so in time O(1), but a singly-linked list would take time O(2) (n). In both cases, it's O(n) if you don't know the cell ahead of time. I hope this information was useful.
In a binary search tree, what is the difficulty of deletion?
Time complexity is O in general (h). The deletion of element 1 necessitates a traversal of all elements to locate it (in orders 3, 2, 1). As a result, deletion in a binary tree has an O worst-case complexity (n). Time complexity is O in general (h).
Is the AVL tree or the B-tree better?
AVL trees are designed for usage in memory, where random access is inexpensive. Because they aggregate a higher number of keys into each node, B-trees are better suitable for disk-backed storage because they reduce the number of seeks required by a read or write operation.
Is the linked list ordered?
Linked Lists, like stacks and queues, are a type of sequential collection. It doesn't have to be in any particular order. A linked list is a collection of independent nodes that can hold any type of data. Each node in the link has a reference to the next node.
Conclusion
This article has gone through duplicating keys in AVL, and we have solved the following problem. Linked lists are one of the most basic and widely used Data Structure. Check out our articles in Library. You may also CheckOut our course on the tree.
34+ registered 
