Самый удаленный узел для каждого узла

Question

Есть ли способ найти самый удаленный узел для каждого узла в двоичном дереве. Я знаю о проблеме диаметров дерева, но это вопрос о каждом узле. Я бы хотел, чтобы алгоритм работал в O(nlogn) для дерева n-node.

Answer 1

В два этапа:

• Рассчитайте самый дальний ребенка и его расстояние для каждого узла. Это можно сделать, пройдя постобработку дерева (O (n)).

• Для каждого узла: проверьте самый отдаленный ребенок для этого узла и каждого его родителя (добавив одно дополнительное расстояние, когда вы идете к корню). Выберите самый большой. O (n logn).

Модификация: Если вы храните самый дальний ребенка и дистанцию ​​как для левых и правых поддерев, вы можете перемещаться по дереву предварительного заказу и получить все результаты в O (N).

Примера (без маркировки , который узла является самым отдаленной .. реализация детали):

 3.2  root 
    / \ 
    1*2 0.1 
    /\ \ 
    0.0 1.1 0.0 
    /\ 
    0.0 0.0 

Начиная от корня - наибольшее расстояние через родитель 0.

• Наибольшее расстояние max (0,2,3) = 3.
• Рекурсия влево: прохождение max (0,2) +1 как наибольшее расстояние через родителя.
• Рекурсия вправо: прохождение max (0,3) +1 как самое длинное расстояние через родителя.

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

Answer 2

Для тех, кто заинтересован в реализации питона вдохновил на Karolys гуманного:

Шаг 1: Нисходящая только поиск

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

код питон:

def getFarGrandChild(node, tree, grandChildren): 
    winner = None # {'node' : node, 'distance' : 0} 
    second = None 
    for child in tree.childrenOf(node): 
     grandChild = getFarGrandChild(child, tree, grandChildren) 
     if winner == None or grandChild['distance'] > winner['distance']: 
      second = winner 
      winner = grandChild 
     elif second == None or grandChild['distance'] > second['distance']: 
      second = grandChild 

    grandChildren[node] = (winner, second) 
    if winner == None: 
     return {'child' : node, 
       'grandChild' : node, 
       'distance' : 1} 
    else: 
     return {'child' : node, 
       'grandChild' : winner['grandChild'], 
       'distance' : winner['distance'] + 1} 

Шаг 2: Поиск по всем направлениям

А подсоединенные к своим детям и внукам, но и его родителям и бабушкам и дедушкам и другим их потомкам.Мы называем эти племянниц

• Для корня выберите в самый дальний узел: самый дальний ребенок.
• Для каждого из своих детей выберите самого отдаленного ребенка или самую далекую племянницу. Самая дальняя племянница - самый далекий ребенок от корня из другой ветви.
• Прогресс downwar, проходящий как самая далекая племянница, теперь может происходить от другого ребенка или выше.

питон код:

def getFarRelative(node, tree, grandChildren, farNodes, niece = None):  
    winner, second = grandChildren[node] 

    if niece != None: 
     if winner == None or niece['distance'] > winner['distance']: 
      second = winner 
      winner = niece 
     elif second == None or niece['distance'] > second['distance']: 
      second = niece 
    farNodes[node] = winner 

    for child in tree.childrenOf(node): 
     if child != winner['child']: 
      getFarRelative(child, tree, grandChildren, farNodes, 
       niece = {'child' :node, 
         'grandChild' : winner['grandChild'], 
         'distance' : winner['distance'] + 1}) 
     elif second != None: 
      getFarRelative(child, tree, grandChildren, farNodes, 
       niece = {'child' : node, 
         'grandChild' : second['grandChild'], 
         'distance' : second['distance'] + 1}) 

Я создал дерево

, используя приведенный ниже код через from graph import *

# A set of data structures to represent graphs 
# 

class Node(object): 
    def __init__(self, name): 
     self.name = str(name) 
    def getName(self): 
     return self.name 
    def __str__(self): 
     return self.name 
    def __repr__(self): 
     return self.name 
    def __eq__(self, other): 
     return self.name == other.name 
    def __ne__(self, other): 
     return not self.__eq__(other) 
    def __hash__(self): 
     # Override the default hash method 
     # Think: Why would we want to do this? 
     return self.name.__hash__() 

class Edge(object): 
    def __init__(self, src, dest): 
     self.src = src 
     self.dest = dest 
    def getSource(self): 
     return self.src 
    def getDestination(self): 
     return self.dest 
    def __str__(self): 
     return '{0}->{1}'.format(self.src, self.dest) 

class Digraph(object): 
    """ 
    A directed graph 
    """ 
    def __init__(self): 
     # A Python Set is basically a list that doesn't allow duplicates. 
     # Entries into a set must be hashable (where have we seen this before?) 
     # Because it is backed by a hashtable, lookups are O(1) as opposed to the O(n) of a list (nifty!) 
     # See http://docs.python.org/2/library/stdtypes.html#set-types-set-frozenset 
     self.nodes = set([]) 
     self.edges = {} 
    def addNode(self, node): 
     if node in self.nodes: 
      # Even though self.nodes is a Set, we want to do this to make sure we 
      # don't add a duplicate entry for the same node in the self.edges list. 
      raise ValueError('Duplicate node') 
     else: 
      self.nodes.add(node) 
      self.edges[node] = [] 
    def addEdge(self, edge): 
     src = edge.getSource() 
     dest = edge.getDestination() 
     if not(src in self.nodes and dest in self.nodes): 
      raise ValueError('Node not in graph') 
     self.edges[src].append(dest) 

    def childrenOf(self, node): 
     return self.edges[node] 

    def hasNode(self, node): 
     return node in self.nodes 
    def __str__(self): 
     res = '' 
     for k in self.edges: 
      for d in self.edges[str(k)]: 
      #for d in self.edges[k]: 
       res = '{0}{1}->{2}\n'.format(res, k, d) 
     return res[:-1] 

и протестирована на этом дереве

if __name__ == '__main__': 
    # Create a tree : 
    #   root 
    #   /\ 
    #   l r 
    #  /\ 
    #  ll lr 
    # /  \ 
    # lll  lrr 
    # /   
    # llll   

    myTree = Digraph() 
    myTree.addNode(Node(str('root')))   
    myTree.addNode(Node(str('l'))) # for left 
    myTree.addEdge(Edge(Node(str('root')), Node(str('l')))) 
    myTree.addNode(Node(str('ll'))) # for left, left 
    myTree.addEdge(Edge(Node(str('l')), Node(str('ll'))))   
    myTree.addNode(Node(str('lll'))) 
    myTree.addEdge(Edge(Node(str('ll')), Node(str('lll'))))   
    myTree.addNode(Node(str('llll'))) 
    myTree.addEdge(Edge(Node(str('lll')), Node(str('llll'))))   
    myTree.addNode(Node(str('lr'))) # for left, right 
    myTree.addEdge(Edge(Node(str('l')), Node(str('lr'))))   
    myTree.addNode(Node(str('lrr'))) 
    myTree.addEdge(Edge(Node(str('lr')), Node(str('lrr'))))   
    myTree.addNode(Node(str('r'))) 
    myTree.addEdge(Edge(Node(str('root')), Node(str('r')))) 

С этими заявлениями

grandChildren = {} 
    getFarGrandChild(Node('root'), myTree, grandChildren) 
    for key in grandChildren: 
     print key, grandChildren[key] 
    print '\n' 

    farNodes = {} 
    getFarRelative(Node('root'), myTree, grandChildren, farNodes) 
    print '\n' 
    for key in farNodes: 
     print key, farNodes[key]