Как я могу эффективно обрабатывать все случаи удаления узлов в двоичном дереве поиска (BST) в Java? ⇐ JAVA

[Anonymous]

Я работаю над реализацией двоичного дерева поиска (BST) в Java, и мне нужно правильно обрабатывать все случаи удаления узлов. Мне нужно обработать следующие случаи:
Узел без дочерних элементов (листовой узел)
Узел с одним дочерним элементом
Узел с двумя дочерними элементами
Я изо всех сил пытается эффективно реализовать метод удаления, обеспечивая при этом сохранение свойств BST. Кроме того, я хотел бы убедиться, что решение имеет хорошие характеристики производительности.
Вот структура, которая у меня есть на данный момент:

Код: Выделить всё

class TreeNode {
int val;
TreeNode left, right;

TreeNode(int val) {
this.val = val;
this.left = this.right = null;
}
}

public class BinarySearchTree {
private TreeNode root;
public void insert(int key) {
root = insertRec(root, key);
}

private TreeNode insertRec(TreeNode root, int key) {
if (root == null) {
root = new TreeNode(key);
return root;
}
if (key < root.val) {
root.left = insertRec(root.left, key);
} else if (key > root.val) {
root.right = insertRec(root.right, key);
}
return root;
}

// Method to delete a node from the BST
public void delete(int key) {
root = deleteRec(root, key);
}

private TreeNode deleteRec(TreeNode root, int key) {
if (root == null) {
return root;
}

if (key < root.val) {
root.left = deleteRec(root.left, key);
} else if (key > root.val) {
root.right = deleteRec(root.right, key);
} else {
// Node with only one child or no child
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
}

// Node with two children: Get the inorder successor (smallest in the right subtree)
root.val = minValue(root.right);

// Delete the inorder successor
root.right = deleteRec(root.right, root.val);
}

return root;
}

private int minValue(TreeNode root) {
int minVal = root.val;
while (root.left != null) {
minVal = root.left.val;
root = root.left;
}
return minVal;
}

// Method to perform in-order traversal of the BST
public void inOrder() {
inOrderRec(root);
}

private void inOrderRec(TreeNode root) {
if (root != null) {
inOrderRec(root.left);
System.out.print(root.val + " ");
inOrderRec(root.right);
}
}

public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();

// Insert nodes
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);

System.out.println("Inorder traversal of the given tree:");
tree.inOrder();

System.out.println("\n\nDelete 20:");
tree.delete(20);
tree.inOrder();

System.out.println("\n\nDelete 30:");
tree.delete(30);
tree.inOrder();

System.out.println("\n\nDelete 50:");
tree.delete(50);
tree.inOrder();

Правильен ли этот код?
Как я могу эффективно обрабатывать все случаи удаления узлов в двоичном дереве поиска (BST) в Java?

Подробнее здесь: https://stackoverflow.com/questions/786 ... earch-tree