I am working on optimizing the Delete-Max operation in an unbalanced Binary Search Tree (BST) where frequent max deletions occur.
Here the i faced issues-
The BST loses balance
Search operations degrade
Need a strategy that prevents tree degeneration into a linked list.
Here is my current implementation of Delete-Max:
public class Node
{
public int Value;
public Node Left, Right;
public Node(int value)
{
Value = value;
Left = Right = null;
}
}
public class BinarySearchTree
{
public Node Root;
public Node DeleteMax(Node root)
{
if (root == null)
return null;
if (root.Right == null)
{
return root.Left;
}
root.Right = DeleteMax(root.Right);
return root;
}
}