Двоичный поиск дерева удалить сложность узла

-1

Я пытаюсь рассчитать сложность удаления узла двоичного дерева. Я хочу рассчитать сложность во всех трех случаях (худшая, средняя сложность и наилучшая) более подробно. Как выбрать математическую формулу ? T (n) =?Двоичный поиск дерева удалить сложность узла

Nod* delete(Nod*& rad, const int& c) 
{ 
    //Nod has:c(information:int),nextSt(left:pointer to Nod),nextDr(right pointer to Nod) 
    Nod* aux; 
    if (rad == NULL) 
     return NULL; 
    else 
     if (c< rad->c && c != rad->c) { 
      rad->nextSt() = delete(rad->nextSt(), c); 
      return rad; 
     } 
     else 
      if (c > rad->c) { 
       rad->nextDr() = delete(rad->nextDr(), c); 
       return rad; 
      } 
      else 
       if (rad->nextSt() != NULL && rad->nextDr() != NULL) { 
        aux = minim(rad->nextDr()); 
        rad->setElem(aux->element()); 
        rad->nextDr() = delete(rad->nextDr(), rad->c); 
        return rad; 
       } 
       else { 
        aux = rad; 
        Nod* repl; 
        if (rad->nextSt() == NULL) 
         repl = rad->nextDr(); 
        else 
         repl = rad->nextSt(); 
        delete rad; 
        return repl; 
       } 

}

источник

2016-06-23 paulc

Это зависит от того, ваш узел является сбалансированным. Удаление узла - это O (глубина) в бинарных деревьях. O (глубина) = O (n) для несбалансированных деревьев (n - количество узлов), тогда как для сбалансированных деревьев это просто O (log (n)). Другими словами, покажите нам ваш алгоритм вставки :). – lorro

Удалить операцию на двоичном дереве поиска всегда занимает время O (h). Где h - высота дерева.

Так что, если ваше дерево хорошо сбалансировано, высота равна log (N). И операция удаления также будет принимать O (log (N)). Это лучший случай.

Худший случай появляется, когда все ваши узлы используют правый/левый дочерний элемент в качестве следующего узла. Этот случай может возникнуть, если вы вставляете отсортированные элементы (например, 1,2,3,4,5) в дерево. Таким образом, высота этого дерева равна N, а операция удаления займет время O (N). В этом случае двоичное дерево поиска не является лучшим связанным списком.

Так средняя сложность между лога (N) и N

Для получения дополнительной информации о бинарном дереве поиска и теории сложности см Введение CORMEN на алгоритм

источник

2016-06-23 07:26:04 caco3

Двоичный поиск дерева удалить сложность узла

ответ

Смежные вопросы