BST, находя следующий самый высокий узел

В BST, согласно программированию Интервью ExposedBST, находя следующий самый высокий узел

«Учитывая узел, вы можете даже найти следующий самый высокий узел в O (журнал (п)) время» Pg 65

Узел в BST имеет правый дочерний элемент как следующий самый высокий узел, тогда почему O (log (n))? Пожалуйста, исправьте

Первый ответ на вопрос, а затем отрицать это

источник

2014-01-08 codey modey

Что делать, если у него нет подходящего ребенка? – Dukeling

Каково значение следующего высшего узла в соответствии с вами? –

Вероятно, следующий узел большего размера. – Dukeling

«Узел в BST имеет право ребенка в качестве следующего высшего узла» (предполагается, что здесь «следующий самый высокий» означает следующее наибольшее значение) - нет, это Безразлично «т. То, что может быть в случае, если у него нет левого узла, но это не всегда так (см. Пункт 1 ниже).

Следующее наибольшее значение (используя этот термин, а не «высшей», поскольку последний может быть спутать с высоты дерева) значение происходит от одного из двух мест:

Во-первых, если текущий узел имеет правильный ребенка , перейдите к этому правильному потомку, пока вы видите левого ребенка, перейдите к нему.

Другими словами (S и D являются источником и назначения):

S 
/\ 
x x <- This is the node your simple explanation chose, 
    /\ but it's the wrong one in this case. 
    x x 
/\ 
D x 
    \ 
    x

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

x 
\ 
    D 
/\ 
x x 
\ 
    x 
/\ 
x S 
/
    x

Псевдокод для такой функции будет:

def getNextNode (node): 
    if node.right != NULL: 
     node = node.right 
     while node.left != NULL: 
      node = node.left 
     return node 

    while node.parent != NULL: 
     if node.parent.left == node: 
      return node.parent 
     node = node.parent 

    return NULL

Поскольку усилие пропорционально высоте дерева, сбалансированный дерево (например, красно-черный, 2-3-4 и AVL) будет иметь временную сложность O (log N), так как высота имеет отношение logN к количеству элементов. В книге рассказывается о сбалансированных деревьях здесь, поскольку в нем содержатся такие фрагменты, как:

Этот поиск является быстрой операцией, поскольку вы исключаете половину узлов из своего поиска на каждой итерации.
Поиск - это операция O (log (n)) в двоичном дереве поиска.
Поиск - это только O (log (n)), если вы можете гарантировать, что количество оставшихся узлов, которые будут искать, будет уменьшено на половину или почти вдвое на каждой итерации.

Таким образом, в то время как он признает, что в последней котировке, что BST может не быть сбалансирован, O (журнал N) свойство только для тех вариантов, которые являются.

Для не сбалансированных деревьев, сложность (в худшем случае) будет O (N), как вы могли бы в конечном итоге с вырожденными деревьев, как:

источник

2014-01-08 08:58:59 paxdiablo

и как это log (n)? –

@ user2901020 В сбалансированном дереве 'depth' равен O (log N). При поиске следующего узла вы переходите не более, чем к глубине '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' – JakubT

, чтобы реализовать его, как вы находите родителя данного узла, нет верного указателя справа? Короче говоря, можете ли вы дать представление о том, как это реализовано, для меня это будет выглядеть следующим образом: сначала вычислите глубину исходного узла, затем вычислите его родительский элемент, затем проверьте, является ли исходный узел правильным или левым его узлом. Я запутавшись, не могли бы вы дать мне правильное направление? –

Вот моя реализация псевдо в Java. Надеюсь, поможет.

Структура узла

public Class Node{ 

int value {get, set}; 
Node leftChild {get,set}; 
Node rightChild{get, set}; 
Node parent{get,set}; 
}

Функция, чтобы найти следующий самый высокий узел

public Node findNextBiggest(Node n){ 
    Node temp=n; 
    if(n.getRightChild()==null) 
    { 
     while(n.getParent()!=null && temp.getValue()>n.getParent().getValue()) 
     { 
      n=n.getParent(): 
     } 
     return n.getParent(); 
    } 
    else 
    { 
     n=n.getRightChild(); 
     while (n.getLeftChild()!=null && n.getLeftChild().getValue()>temp.getValue()) 
     { 
      n=n.getLeftChild(); 
     } 
    return n; 
    } 
}

источник

2014-04-11 16:20:20 Bipin

Я думаю, мы можем найти следующий самый высокий узел просто найти заказовМои Преемник узла ,

Steps -

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

источник

2017-06-06 14:56:15

BST, находя следующий самый высокий узел

ответ

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