Как мне получить уровень узла в очень большом двоичном дереве?

#python #algorithm #data-structures #binary-tree #nested-loops

#питон #алгоритм #структуры данных #двоичное дерево #вложенные циклы

Вопрос:

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

Шаблон генерации кортежей находится в классе узлов.

Например, решение («4», «7») вернет 4, а решение(«2», «1») вернет 1

 from itertools import product  class Node:  def __init__(self,data):  self.data = data  self.left = (self.data[0]   self.data[1], self.data[1])  self.right = (self.data[0], self.data[0]   self.data[1])   def lefts(self):  self.data = self.left   def rights(self):  self.data = self.right   def getter(self):  return self.data  def solution(x,y):  tup = (int(x),int(y))  a = ['left', 'right']  directions = list(product(a,repeat=int(max(tup))))   for direction in directions:  node = Node((1,1))  count = 0  for lor in direction:  if node.getter() == tup:  return count  if lor == 'left':  node.lefts()  node = Node(node.getter())  else:  node.rights()  node = Node(node.getter())  count  = 1    return 'impossible'

1. Каковы входные данные? Можете ли вы добавить примеры входов и соответствующих выходов?

2. Отвечаете ли вы за построение дерева или вам необходимо использовать определенный класс дерева? Также: существует ли только один запрос или несколько запросов с одним и тем же деревом?

Ответ №1:

Для этой проблемы на самом деле создавать двоичное дерево-излишество.

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

Это более интересно, так как узел имеет только одного родителя, и поэтому не нужно рассматривать никаких альтернатив. Если этот путь ведет к узлу (1, 1), то мы нашли решение. Если, однако, путь ведет к кортежу, член которого не является строго положительным, то мы можем сделать вывод, что решения нет… по-видимому, узел является членом отдельного дерева.

«Формула» для получения родительского узла (x, y) является

(x, y — x) когда y gt; x
(x — y, y) в противном случае

Основываясь на этих наблюдениях, программа довольно проста:

 def solution(x, y):  count = 0  while x gt; 1 and y gt; 1:  if x gt; y:  x -= y  else:  y -= x  count  = 1  return count   abs(x - y) if min(x, y) == 1 else "impossible"