Skip to main content

Trees

Trees — это иерархическая структура данных, состоящая из узлов, где один узел является корнем, а остальные образуют поддеревья, связаны через родительские и дочерние узлы, и часто используются для поиска, сортировки, хранения и представления иерархий (например, бинарные деревья, деревья поиска и деревья сегментов)

📄️ Поиск в глубину - DFS

В глубоком обходе (Depth-first search - DFS) мы отдаем приоритет глубине, проходя как можно дальше вниз по дереву в одном направлении (до достижения листового узла), прежде чем рассматривать другое направление. Например, если мы выбираем левое направление в качестве приоритетного, то будем двигаться исключительно по node.left, пока левое поддерево не будет полностью исследовано. Затем мы исследуем правое поддерево.

📄️ Поиск в ширину - BFS

В глубинном поиске (DFS) мы уделяли приоритет глубине. В поиске в ширину (breadth-first search - BFS) мы уделяем приоритет ширине. Напомним, что глубина узла — это его расстояние от корня. В DFS мы старались углубиться настолько, насколько это возможно, увеличивая глубину текущего узла, пока не достигали листа. Если вы выполнили DFS на большом дереве, глубина узлов, которые вы бы обошли, может выглядеть как: 0, 1, 2, 3, 4, 5, 6, ...