Skip to main content

AVL tree with duplicate key

AVL trees are powerful data structures that maintain their balanced nature while enabling efficient operations such as insertion, deletion, and searching. However, in some scenarios, duplicate keys might be necessary. This article explores the concept of an AVL tree with duplicate keys, discussing its implementation, providing examples, explaining the underlying logic, and presenting the outcome of various operations.

Problem Statement and Description

The challenge at hand is to modify the conventional AVL tree structure to accommodate duplicate keys while preserving its self-balancing properties. We will delve into the process of adding nodes with duplicate keys, adjusting the tree height, performing rotations, and ensuring that the tree remains balanced after insertions and deletions.

Example

Let's consider an AVL tree with duplicate keys:

       12(1)
         /   \
      7(2)   17(1)
       / \      \
    2(1)  11(1)  19(1)
    / \
5(1)  7(1)

We will perform insertions and deletions in this tree while maintaining the AVL properties.

Idea to Solve

To implement an AVL tree with duplicate keys, we'll modify the insertion and deletion operations as follows:

  • In the insertion process, if a key already exists, we'll increment its occurrence counter instead of rejecting it.
  • In the deletion process, when we encounter a node with duplicate keys, we'll decrement its occurrence counter. If the counter reaches zero, we'll proceed with the standard AVL deletion process.

Pseudocode

class LinkNode:
    int key
    int height
    int occurrence
    LinkNode left
    LinkNode right
    
    LinkNode(key):
        this.key = key
        this.height = 1
        this.occurrence = 1
        this.left = nullptr
        this.right = nullptr

class AvlTree:
    LinkNode root
    
    AvlTree():
        this.root = nullptr
    
    int getHeight(node):
        return 0 if node is nullptr else node.height
    
    int max(a, b):
        return a if a > b else b
    
    LinkNode rightRotate(node):
        ...
    
    LinkNode leftRotate(node):
        ...
    
    int getBalanceFactor(node):
        ...
    
    LinkNode addNode(node, key):
        ...
    
    void preorder(node):
        ...
    
    LinkNode minKeyNode(node):
        ...
    
    LinkNode deleteNode(node, key):
        ...
    
    bool isNodeExist(node, key):
        ...
    
    void deleteKeyNode(key):
        ...

Algorithm Explanation

  • The algorithm is implemented using classes and methods.
  • The addNode function adds nodes with duplicate keys by incrementing occurrence counters.
  • The deleteKeyNode function handles the deletion of nodes while considering occurrence counters.
  • The remaining methods are analogous to the ones in a standard AVL tree implementation.

Code Solution

Important notes : When we are need one extra field to manage duplicate nodes.

Time Complexity

The time complexity of insertion and deletion in an AVL tree with duplicate keys remains O(log n), just like in a standard AVL tree. The balance factor adjustment and rotation operations maintain this efficiency.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment