Java, метод удаления двоичного дерева

Question

Я пытаюсь написать функцию remove(node cRoot, Object o) для сортированного двоичного дерева.

Вот то, что я до сих пор:

private boolean remove(Node cRoot, Object o) { 
    if (cRoot == null) { 
    return false; 
    } 
    else if (cRoot.item.equals(o)) { 
    //erase node fix tree 
    return true; 
    } 
    else if (((Comparable)item).compareTo(cRoot.item)<=0){ 
    return remove(cRoot.lChild, o); 
    } 
    else { 
    return remove(cRoot.rChild,o); 
    } 
} 

Это не работает правильно. Чтобы удалить узел, вы должны восстановить дерево, чтобы исправить отверстие. Как это сделать?

Answer 1

Основной псевдо-код для стирания узла из отсортированного дерева довольно просто:

1. стереть значение узла
2. находкой дочерний узел с максимальным значением
3. сделать его корневой узел
4. , если у него были дети - goto 2 рекурсивно

В основном, что вы делаете, это пузырящиеся узлы по дереву, каждый раз максимум дочернего узла в каждом узле, так что в конце вы остаетесь с отсортированным деревом, и только один узел отсутствует в конце полного пути, по которому вы пошли.

Также - см. wikipedia on the subject, у них также есть пример кода на C.

Answer 2

Существуют два способа выполнения удалить на дереве:

Первый метод:

Удалить узел, а затем заменить его либо с ребенком. Затем прибегайте к дереву, перебирая parent-child, пока дерево не будет отсортировано.

Второй метод:

Траверс дерева, чтобы найти следующий (высокий или низкий) значение, которое принадлежит как корень *, если это листовой узел, поменять местами, что с корнем, а затем обрезать значение вы хотите удалить. Если это внутренний узел, вам придется рекурсивно вызывать удаление на этом узле. Повторяйте до удаления листового узла.

* Что я имею в виду, если вы преобразуете свой BST в отсортированный список, то вам нужно выбрать либо значение слева, либо справа от корня в качестве нового корня. То есть крайний левый дочерний элемент правого поддерева или правое большинство дочерних элементов левого поддерева.

Answer 3

В простом Вопрос 3 вы можете использовать следующий алгоритм:

if(removed node had left child) 
{ 
    place left child instead of removed node; 
    most_right = most right leaf in the left subtree; 
    move right child of removed node as right child of most_right; 
} 
else 
{ 
    place right child instead of removed node 
} 

В более сложном случае, возможно, потребуется, чтобы сбалансировать свое дерево (см AVL деревья, http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html, например, C++)

Answer 4

1. листо- удалить узел
2. 1-child Продвинуть поддеревье
3. 2-детский корпус заменяет узел
4. в преемнику заказа или предшественника
5. оставил большую часть правого поддерева или
6. прямо большую часть левого поддерева

Answer 5

Я нашел этот код на Habrahabr. Я только что добавил комментарии.

public void remove (T1 k){ 
    Node<T1,T2> x = root, y = null; 
    // from while to if(x == null) - searching for key 
    while(x != null){ 
     int cmp = k.compareTo(x.key); 
     if(cmp == 0){ 
      break; // quit cycle if key element is found 
     } else { 
      y = x; 
      if(cmp < 0){ 
       x = x.left; 
      } else { 
       x = x.right; 
      } 
     } 
    } 
    if(x == null) return; // if key is not found or tree is empty 
    if(x.right == null){ // if element found has not right child 
     if(y == null){  // if element found is root & has not right child 
      root = x.left; 
     } else {   // if element found is not root & has not right child   
      if(x == y.left) y.left = x.left;  
      else y.right = x.left;    
     } 
    } else {   // element found has right child, so search for most left of rights 
     Node<T1,T2> mostLeft = x.right; 
     y = null; 
     while(mostLeft.left != null) { 
      y = mostLeft; 
      mostLeft = mostLeft.left; 
     } 
     if(y == null){ // if right child of element found has not left child 
      x.right = mostLeft.right; 
     } else {  // if right child of element found has left child 
      y.left = mostLeft.right; 
     } 
     x.key = mostLeft.key;  
     x.value = mostLeft.value; 
    } 
}