How to handle duplicates in Binary Search Tree? - GeeksforGeeks
Insertion of keys 12, 10, 20, 9, 11, 10, 12, 12 in an empty Binary Search Tree would create following.
This would let same key(the inorder successor) two places, later it may populate to more places.
It should replace the current node with inorder successor: copy value, and count. Then delete the inorder successor by calling deleteNode (root->right, temp->key, temp-> count);
Read full article from How to handle duplicates in Binary Search Tree? - GeeksforGeeks
In a Binary Search Tree (BST), all keys in left subtree of a key must be smaller and all keys in right subtree must be greater. So a Binary Search Tree by definition has distinct keys.
How to allow duplicates where every insertion inserts one more key with a value and every deletion deletes one occurrence?
A Simple Solution is to allow same keys on right side (we could also choose left side). For example consider insertion of keys 12, 10, 20, 9, 11, 10, 12, 12 in an empty Binary Search Tree
12
/ \
10 20
/ \ /
9 11 12
/ \
10 12
A Better Solution is to augment every tree node to store count together with regular fields like key, left and right pointers.
Insertion of keys 12, 10, 20, 9, 11, 10, 12, 12 in an empty Binary Search Tree would create following.
Insertion of keys 12, 10, 20, 9, 11, 10, 12, 12 in an empty Binary Search Tree would create following.
12(3)
/ \
10(2) 20(1)
/ \
9(1) 11(1)
Count of a key is shown in bracket
This approach has following advantages over above simple approach.
Insertion of keys 12, 10, 20, 9, 11, 10, 12, 12 in an empty Binary Search Tree would create following.
12(3)
/ \
10(2) 20(1)
/ \
9(1) 11(1)
Count of a key is shown in bracket
The delete function is not well implemented, as it would change the current node to its inorder successor, and count 1. then decrement the count of the inorder successor.This would let same key(the inorder successor) two places, later it may populate to more places.
It should replace the current node with inorder successor: copy value, and count. Then delete the inorder successor by calling deleteNode (root->right, temp->key, temp-> count);
struct node{ int key; int count; struct node *left, *right;};struct node* insert(struct node* node, int key){ /* If the tree is empty, return a new node */ if (node == NULL) return newNode(key); // If key already exists in BST, icnrement count and return if (key == node->key) { (node->count)++; return node; } /* Otherwise, recur down the tree */ if (key < node->key) node->left = insert(node->left, key); else node->right = insert(node->right, key); /* return the (unchanged) node pointer */ return node;}struct node* deleteNode(struct node* root, int key){ // base case if (root == NULL) return root; // If the key to be deleted is smaller than the // root's key, then it lies in left subtree if (key < root->key) root->left = deleteNode(root->left, key); // If the key to be deleted is greater than the root's key, // then it lies in right subtree else if (key > root->key) root->right = deleteNode(root->right, key); // if key is same as root's key else { // If key is present more than once, simply decrement // count and return if (root->count > 1) { (root->count)--; return root; } // ElSE, delete the node // node with only one child or no child if (root->left == NULL) { struct node *temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct node *temp = root->left; free(root); return temp; } // node with two children: Get the inorder successor (smallest // in the right subtree) struct node* temp = minValueNode(root->right); // Copy the inorder successor's content to this node root->key = temp->key; // root-> count is 1, then decrement temp count // Delete the inorder successor root->right = deleteNode(root->right, temp->key); } return root;}/* Given a non-empty binary search tree, return the node with minimum key value found in that tree. Note that the entire tree does not need to be searched. */struct node * minValueNode(struct node* node){ struct node* current = node; /* loop down to find the leftmost leaf */ while (current->left != NULL) current = current->left; return current;}