Czy drzewa są zorganizowane według struktury „pierworodnego, następnego”? Jeśli nie, dlaczego nie?

Zwykle struktury danych drzewa są zorganizowane w taki sposób, że każdy węzeł zawiera wskaźniki dla wszystkich swoich elementów potomnych.

       +-----------------------------------------+
       |        root                             | 
       | child1            child2         child3 |
       +--+------------------+----------------+--+
          |                  |                |
+---------------+    +---------------+    +---------------+
|    node1      |    |     node2     |    |     node3     |
| child1 child2 |    | child1 child2 |    | child1 child2 |
+--+---------+--+    +--+---------+--+    +--+---------+--+
   |         |          |         |          |         |

Wydaje się to naturalne, ale wiąże się z pewnymi problemami. Na przykład, gdy liczba węzłów potomnych jest różna, potrzebujesz czegoś takiego jak tablica lub lista do zarządzania dziećmi.

Używając tylko (pierwszych) wskaźników potomnych i (następnych) rodzeństwa, otrzymujemy coś, co wygląda następująco:

       +-------------------+
       |        root       |
       | child    sibling  +--->NULL
       +--+----------------+
          |             
+----------------+    +----------------+    +----------------+
|    node1       |    |     node2      |    |     node3      |
| child  sibling +--->| child  sibling +--->| child  sibling +--->NULL
+--+-------------+    +--+-------------+    +--+-------------+
   |                     |                     |

Oczywiście tego rodzaju struktura może również reprezentować drzewa, ale ma również pewne zalety. Najważniejsze jest to, że nie musimy martwić się o liczbę węzłów potomnych. Gdy jest używany do parsowania drzewa, oferuje naturalną reprezentację terminu, takiego jak „a + b + c + d + e”, bez przekształcania się w głębokie drzewo.

Czy biblioteki kolekcji oferują takie struktury drzewiaste? Czy parsery używają takiej struktury? Jeśli nie, jakie są przyczyny?

Drzewa, podobnie jak listy, są „abstrakcyjnymi typami danych”, które można wdrażać na różne sposoby. Każdy sposób ma swoje zalety i wady.

W pierwszym przykładzie główną zaletą tej struktury jest to, że można uzyskać dostęp do dowolnego elementu podrzędnego w O (1). Wadą jest to, że dołączenie dziecka może czasem być nieco droższe, gdy trzeba rozszerzyć tablicę. Koszt ten jest jednak stosunkowo niewielki. Jest to również jedna z najprostszych implementacji.

W drugim przykładzie główną zaletą jest to, że zawsze dołączasz dziecko do O (1). Główną wadą jest to, że losowy dostęp do dziecka kosztuje O (n). Ponadto może być mniej interesujący w przypadku dużych drzew z dwóch powodów: ma narzut pamięci w postaci jednego nagłówka obiektu i dwa wskaźniki na węzeł, a węzły są losowo rozmieszczone w pamięci, co może powodować dużą zamianę między pamięcią podręczną procesora a pamięć podczas przechodzenia drzewa, dzięki czemu ta implementacja jest dla nich mniej atrakcyjna. Nie jest to jednak problem w przypadku normalnych drzew i aplikacji.

Ostatnią interesującą możliwością, o której nie wspomniano, jest przechowywanie całego drzewa w jednej tablicy. Prowadzi to do bardziej złożonego kodu, ale czasami jest bardzo korzystną implementacją w określonych przypadkach, szczególnie w przypadku dużych stałych drzew, ponieważ można zaoszczędzić na kosztach nagłówka obiektu i przydzielić ciągłą pamięć.

Prawie każdy projekt, który ma jakiś edytowalny model lub dokument, będzie miał strukturę hierarchiczną. Przydaje się zaimplementowanie „węzła hierarchicznego” jako klasy podstawowej dla różnych podmiotów. Często lista połączona (rodzeństwo dziecka, drugi model) jest naturalnym sposobem rozwoju wielu bibliotek klas, jednak dzieci mogą być różnego typu, a prawdopodobnie „ model obiektowy ” nie jest tym, co rozważamy, mówiąc ogólnie o drzewach.

Moja ulubiona implementacja drzewa (węzła) twojego pierwszego modelu to jednowierszowa (w C #):

public class node : List<node> { /* props go here */ }

Dziedzicz z ogólnej listy własnego typu (lub dziedzicz z dowolnej innej ogólnej kolekcji własnego typu). Chodzenie jest możliwe w jednym kierunku: uformuj korzeń w dół (przedmioty nie znają swoich rodziców).

Rodzic tylko drzewa

Innym modelem, o którym nie wspomniałeś, jest ten, w którym każde dziecko ma odniesienie do swojego rodzica:

               null
                 |
       +---------+---------------------------------+
       |       parent                              |
       | root                                      |
       +-------------------------------------------+
          |                   |                |
+---------+------+    +-------+--------+    +--+-------------+
|     parent     |    |     parent     |    |     parent     |
|     node 1     |    |     node 2     |    |     node 3     |
+----------------+    +----------------+    +----------------+

Zwiedzanie tego drzewa jest możliwe tylko na odwrót, zwykle wszystkie te węzły będą przechowywane w kolekcji (tablica, tablica mieszająca, słownik itp.), A węzeł zostanie zlokalizowany poprzez przeszukanie kolekcji według kryteriów innych niż pozycja hierarchiczna w drzewo, które zwykle nie miałoby podstawowego znaczenia.

Te drzewa tylko dla rodziców są zwykle widoczne w aplikacjach bazodanowych. Łatwo jest znaleźć dzieci węzła za pomocą instrukcji „SELECT * WHERE ParentId = x”. Jednak rzadko zdarza się, że są one przekształcane w obiekty klasy węzłów drzewnych jako takie. W aplikacjach stanowych (stacjonarnych) mogą być zawinięte w istniejące kontrolki węzłów drzewa. W aplikacjach bezstanowych (internetowych) nawet to może być mało prawdopodobne. Widziałem narzędzia do generowania klas mapujące ORM generujące błędy przepełnienia stosu podczas generowania klas dla tabel, które mają relację ze sobą (chichot), więc może te drzewa nie są wcale takie powszechne.

dwukierunkowe drzewa żeglowne

Jednak w większości praktycznych przypadków wygodnie jest mieć to, co najlepsze z obu światów. Węzły, które mają listę dzieci, a ponadto znają swojego rodzica: dwukierunkowe drzewa nawigacyjne.

                          null
                            |
       +--------------------+--------------------+
       |                  parent                 |
       |        root                             | 
       | child1            child2         child3 |
       +--+------------------+----------------+--+
          |                  |                |
+---------+-----+    +-------+-------+    +---+-----------+
|      parent   |    |     parent    |    |  parent       |
|    node1      |    |     node2     |    |     node3     |
| child1 child2 |    | child1 child2 |    | child1 child2 |
+--+---------+--+    +--+---------+--+    +--+---------+--+
   |         |          |         |          |         |

Przynosi to wiele innych aspektów do rozważenia:

• Gdzie wdrożyć łączenie i rozłączanie rodzica?
  • pozwól zająć się logiką biznesową i pozostaw aspekt poza węzłem (zapomną!)
  • węzły mają metody tworzenia potomków (nie zezwalają na zmianę kolejności) (wybór Microsoftu w ich implementacji DOM System.Xml.XmlDocument, co prawie doprowadziło mnie do szału, gdy pierwszy raz go spotkałem)
  • Węzły przyjmują element nadrzędny w swoim konstruktorze (nie zezwala na zmianę kolejności)
  • we wszystkich metodach add (), insert () i remove () oraz ich przeciążeniach węzłów (zazwyczaj mój wybór)
• Wytrwałość
  • Jak chodzić po drzewie podczas utrwalania (pomiń na przykład linki rodzica)
  • Jak odbudować dwukierunkowe połączenie po usunięciu serializacji (ponowne ustawienie wszystkich rodziców jako działanie po deserializacji)
• Powiadomienia
  • Mechanizmy statyczne (flaga IsDirty), obsługują rekurencyjnie we właściwościach?
  • Zdarzenia, bańka w górę przez rodziców, w dół przez dzieci lub w obie strony (na przykład pompa komunikatów systemu Windows).

Teraz, aby odpowiedzieć na pytanie , dwukierunkowe drzewa żeglowne są (w mojej dotychczasowej karierze i dziedzinie) najczęściej używane. Przykładami są implementacja Microsofts System.Windows.Forms.Control lub System.Web.UI.Control w .NET, ale także każda implementacja DOM (Document Object Model) będzie miała węzły, które znają ich element nadrzędny, a także wyliczenie ich dzieci. Powód: łatwość użycia zamiast łatwości implementacji. Są to zwykle klasy podstawowe dla bardziej szczegółowych klas (XmlNode może być podstawą klas Tag, Attribute i Text), a te klasy podstawowe są naturalnymi miejscami do umieszczenia ogólnej architektury serializacji i obsługi zdarzeń.

Tree leży w sercu wielu architektur, a swobodne poruszanie się oznacza szybsze wdrażanie rozwiązań.

Nie znam żadnej biblioteki kontenerów, która bezpośrednio obsługuje twój drugi przypadek, ale większość bibliotek kontenerów może z łatwością obsługiwać ten scenariusz. Na przykład w C ++ możesz mieć:

class Node;  // forward reference to satisfy the compiler
typedef std::list<Node*> NodeList;
class Node : public NodeList { /* . . . */ };  // a node is also a list

Node* n = new Node;
n->push_back(new Node);
Node* tree = new Node;
tree->push_back(new Node);
tree->push_back(n);

Parsery prawdopodobnie używają podobnej struktury, ponieważ skutecznie obsługują węzły o zmiennej liczbie elementów i elementów podrzędnych. Nie wiem na pewno, ponieważ zwykle nie czytam ich kodu źródłowego.

Jednym z przypadków, w których posiadanie szeregu dzieci jest lepsze, jest potrzeba losowego dostępu do dzieci. I zwykle dzieje się tak, gdy dzieci są sortowane. Na przykład drzewo hierarchii podobne do pliku może to wykorzystać do szybszego wyszukiwania ścieżki. Lub drzewo znaczników DOM, gdy dostęp do indeksu jest bardzo naturalny

Innym przykładem jest posiadanie „wskaźników” dla wszystkich dzieci, co pozwala na wygodniejsze korzystanie z nich. Na przykład oba opisane typy mogą być używane podczas implementowania relacji drzewa z relacyjną bazą danych. Ale ten pierwszy (w tym przypadku główny szczegół od rodzica do dziecka) pozwoli na zapytanie z ogólnym SQL o przydatne dane, podczas gdy ten drugi znacznie cię ograniczy.