Different Node Deletion/Insertion in a Binary Search Tree

• mooncrater
In summary, if we had a pointer that pointed to the node's successor instead of the node's parent, then the methods of insertion and deletion would change.
mooncrater
What happens, if instead of having any pointer pointing to a node's parent, we had pointer pointing to the node's successor? We know, that Searching would remain the same. But in my opinion Insertion and Deletion would change. This would happen, because in insertion, we would be needed to find the successor and predecessor of the inserted node, and changing information accordingly. And in Deletion, we would be needed to re-align the successor value of the predecessor of the deleted element.
This shows the dependency of both the modified methods on finding the predecessor of the inserted/deleted element. My pseudocode for finding the predecessor is:
Code:
Predecessor(T,x)
1. y= T.root
2. while y.left_child ! = NULL
3.            y = y.left_child
4. while y.succ ! = x
5.           y = y.succ
6.return y
Here, lines 2-3 find the least element of the tree, and lines 4-5 find the element whose successor is ##x##(where ##x## is the pointer to the desired node.)
As we can see, that lines 4-5 take ##O(n)## time, (where ##n## is the total number of elements) instead of ##O(h)## time.(where ##h## is the height of the tree) .
This being said, leads to a conclusion that both the methods INSERT and DELETE would take atleast ##\Omega (n)## time. But according to a question in cormen(12.3-5) [https://github.com/yaoshengzhe/notes/blob/master/clrs/12_binary_search_trees.md] , it should be ##O(h)##.
So where am I wrong?
Any help is appreciated with a lot of thankfulness. :P
Moon.

Last edited by a moderator:
Doesn't Knuth. Volume 3, discuss this?

mooncrater
The github link didn't work for me, but the description sounds like a 'threaded binary search tree'.

mooncrater
@anorlunda - Yup - Knuth does cover that. So does Cormen, so does Sedgewick in Algorithms in C Parts 1 - 4. All of which are wonderful resources!

mooncrater
Thanks for you people replying out there. I just got the answer, and well, it's simple ( and a little embarrassing too!). My predecessor method isn't optimal. It can be made in ##O(h)##. So We can get INSERT and DELETE to work in ##O(h)##.
Thanks.
Moon.

This might suffice.

What is a Binary Search Tree?

A Binary Search Tree is a data structure that organizes data in a tree-like structure, where each node has at most two child nodes. The left child node contains data smaller than the parent node, while the right child node contains data larger than the parent node. This structure allows for efficient searching, insertion, and deletion of data.

What is Node Deletion in a Binary Search Tree?

Node Deletion in a Binary Search Tree refers to the process of removing a node from the tree. This can be done in two ways: deleting a leaf node (a node with no child nodes) or deleting a node with one child node. When deleting a node with one child, the child node takes the place of the deleted node in the tree.

What is Node Insertion in a Binary Search Tree?

Node Insertion in a Binary Search Tree refers to the process of adding a new node to the tree. This can be done by finding the correct position for the new node based on its value in relation to the existing nodes in the tree. The new node is then added as a leaf node or as a child node of an existing node.

What is the difference between Node Deletion and Node Insertion in a Binary Search Tree?

The main difference between Node Deletion and Node Insertion in a Binary Search Tree is that Node Deletion removes a node from the tree, while Node Insertion adds a new node to the tree. Both processes involve finding the correct position for the node based on its value, but the end result is different - one results in a smaller tree, while the other results in a larger tree.

What are the possible issues that can arise during Node Deletion/Insertion in a Binary Search Tree?

There are a few potential issues that can arise during Node Deletion/Insertion in a Binary Search Tree. These include deleting or inserting a node that does not exist in the tree, causing the tree to become unbalanced, or violating the Binary Search Tree property where the left child node is smaller than the parent node and the right child node is larger.

Similar threads

• Programming and Computer Science
Replies
13
Views
4K
• Programming and Computer Science
Replies
3
Views
2K
• Programming and Computer Science
Replies
1
Views
2K
• Programming and Computer Science
Replies
2
Views
1K
• Programming and Computer Science
Replies
1
Views
1K
• General Math
Replies
3
Views
2K
• Programming and Computer Science
Replies
10
Views
3K
• Programming and Computer Science
Replies
14
Views
3K
• Programming and Computer Science
Replies
11
Views
3K
• Programming and Computer Science
Replies
5
Views
2K