Как найти первый узел дерева в dict?

Question

У меня есть большая проблема, в функции для начала работы мне нужно найти первый узел в дереве, вот пример:

              "hi"
            /     \
           /       \
          "ok"     "no"
          /
         /
       "lol"

проблема в том, что я не знаю, как извлечь это из диктата, потому что входные данные такие:

{ "ok":["lol"] , "no":[] , "hi": ["ok","no"] , "lol" : [] }

так что в этом случае "hi" является первым, потому что никто не имеет "hi" в dict.values ​​(), проблема в том, как сказать, что и самое важное, что dict имеет 50000 узлов, поэтому, если я проверяю один за другим, он идет в сверхурочное время.,

я написал это:

    d = { "ok":["lol"] , "no":[] , "hi": ["ok","no"] , "lol" : [] }
    x = d.values()
    x = str(x)
    for y in d.keys():
        if not y in x :
            first_node = y
            break

но проблема в том, что это может быть слово типа "привет" и "ключ", например "ад", так что "ад" находится в "hellow", но не "hellow":(

Answer 1

Вот способ сделать это с помощью set.difference,

from itertools import chain

d = { "ok":["lol"] , "no":[] , "hi": ["ok","no"] , "lol" : [] }
roots = set(d).difference(chain.from_iterable(d.values()))

дает нам

{'hi'}

Answer 2

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

d = { "ok":["lol"] , "no":[] , "hi": ["ok","no"] , "lol" : []}

node = list(d.keys())[0]
found = False
while not found:
    found = True
    for key, value in d.items():
        if node in value:
            node = key
            found = False

print(node)

---

Оказывается, что мое решение лучше всего работает в тестовой среде:

**10 nodes**
0.0000020000017 s - my solution
0.0000043555594 s - using set.diffrence by Patrick Haugh
0.0001111112098 s - list comprehension by Ajax1234

**1000 nodes**
0.0007560006720 s - my solution
0.0015977791980 s - using set.diffrence by Patrick Haugh
0.3337478522203 s - list comprehension by Ajax1234

**10000 nodes**
0.0077213401967 s - my solution
0.0138804567826 s - using set.diffrence by Patrick Haugh
35.264710457520 s - list comprehension by Ajax1234

Answer 3

Вы можете использовать понимание списка:

d = { "ok":["lol"] , "no":[] , "hi":["ok","no"] , "lol" : [] }
root = [a for a, b in d.items() if all(a not in d for c, d in d.items())][0]

Выход:

'hi'