Еще раз, я пишу на другой структуре данных. Другие мои статьи о структурах данных были о линейных структурах данных (последовательно расположенных структурах данных) от связанных списков до стеков и очередей.
Деревья — это нелинейные данные структуры (узлы могут быть связаны с несколькими узлами). Существуют разные классификации деревьев, и чаще всего эти классификации основаны на количестве узлов, с которыми связан каждый узел в дереве. Примером может служить бинарное дерево, где каждый узел указан как связанный с двумя другими узлами.
Деревья обычно используются для отображения отношений между элементами, которые могут быть иерархическими или иными, и эффективными, когда речь идет о вставке и удалении узлов.
ТЕРМИНОЛОГИЯ СТРУКТУРЫ ДЕРЕВЯННЫХ ДАННЫХ
- Корень – первый узел дерева.
- Путь — последовательность связанных узлов.
- Родительский — Предыдущий узел
- Дочерний элемент — Подузел
- Внутренний узел — узел, связанный с родительским и дочерним узлами.
- Конечный узел — Узел без подузла.
- Поколения — все узлы на одном уровне.
- Родственные узлы — узлы с одним и тем же родителем.
- Высота — количество уровней от корневого узла до конечного узла.
КАК СТРУКТУРИРОВАНЫ ДЕРЕВЬЯ
Каждый узел дерева прямо или косвенно связан с корневым узлом (первым узлом)через путь (последовательность связанных узлов), имеет родительский узел (предыдущий узел) и дочерний узел (подузел), который может быть значением или нулевым (в случае пустоты). Узел с родителем и дочерним элементом называется внутренним узлом, а узел без дочернего узла называется конечным узлом. Поколения порождают родственные узлы (узлы, связанные одним и тем же родительским узлом), поскольку каждый узел связан с разными узлами, а количество поколений в дереве равно высоте дерева
Что касается деревьев, следует отметить следующее…
1. Никакие два узла в дереве не могут ссылаться на один и тот же узел.
2. Корневой узел (первый/головной узел) — единственный узел, на который нет ссылок в структуре данных.
РЕАЛИЗАЦИЯ ДРЕВЕСНОЙ СТРУКТУРЫ ДАННЫХ (БИНАРНОЕ ДЕРЕВО ПОИСКА)
Бинарное дерево поиска легко реализовать, его структура показана ниже.
ПИТОН3
class Tree:
def __init__(self, data):
self.data = data
self.left_node = None
self.right_node = None
def printer(self): #prints the tree
if self.left_node:
self.left_node.printer()
print(self.data)
if self.right_node:
self.right_node.printer()
Все начинается с класса Tree, а затем с конструктора. Атрибуты экземпляра left_node right_nodeявляютсяссылками (адресами) на одноуровневые узлы, а атрибут data является заполнителем для элементов.
ОПЕРАЦИИ НАД СТРУКТУРОЙ ДАННЫХ БИНАРНОГО ДЕРЕВА ПОИСКА
Несколько операций можно было бы выполнить с древовидной структурой данных, но в этой статье я рассмотрю вставку и поиск операции
Чтобы понять алгоритмы, используемые в бинарных деревьях поиска, необходимо понять концепцию бинарного дерева поиска.
Бинарное дерево поиска — это не только бинарное дерево, но и упорядоченное дерево поиска. В бинарном дереве поиска есть шаблон, в котором элементы хранятся для облегчения операций быстрого поиска.
В приведенном выше двоичном дереве поиска заметно, что в поддереве каждого узла значение левого дочернего элемента меньше значения родительского узла, а значение правого дочернего элемента больше значения родительского узла.
ВСТАВКА ЭЛЕМЕНТОВ В СТРУКТУРУ ДАННЫХ
Вставляя элементы в нашу древовидную структуру данных, мы должны создать для этого метод. Метод проверяет наличие головного (корневого) узла, если его нет, создается новый узел и устанавливается как корневой, а затем размещается новый элемент. Если есть корневой узел, то создается новый (дочерний узел) и связывается с родительским узлом как левое или правое поддерево, в зависимости от шаблона двоичного дерева.
В приведенном выше бинарном дереве поиска мы замечаем, что правое поддерево содержит значение больше, чем у родителя, и в том же духе левые поддеревья содержат значения меньше, чем у их родителя.
Если нам нужно вставить неизвестный элемент data, мы могли бы написать это.
ПИТОН 3
class Tree:
def __init__(self, data):
self.data = data
self.left_node = None
self.right_node = None
def insert(self, data):
if self.data:
if data < self.data:
if self.left_node is None:
self.left_node = Tree(data)
else:
self.left_node.insert(data)
elif data >= self.data:
if self.right_node is None:
self.right_node = Tree(data)
else:
self.right_node.insert(data)
else:
self.data = data
if self.data проверяет, существует ли головной узел, и если он существует, то мы переходим к проверке неравенства data .
Блок if data < self.data проверяет, что величина data для вставки меньше, чем у родительского узла, и вставляет слева, если это так.
Блок elif data >= self.dataзапускается, если dataдля вставки больше или равен значению родительского узла и добавляет data к правому узлу дерево.
ПОИСК ЭЛЕМЕНТА В БИНАРНОМ ДЕРЕВЕ ПОИСКА
Приведенный ниже метод ищет элемент в двоичном дереве поиска, используя шаблон дерева.
ПИТОН 3
def find(self, data):
if self.data:
if data < self.data:
if self.left_node is None:
return "Data Doesn't Exist"
return self.left_node.find(data)
elif data > self.data:
if self.right_node is None:
return "Data Doesn't Exist"
return self.right_node.find(data)
else:
return "Found it"
else:
return "Empty Tree"
if.self.dataпроверяет, содержит ли дерево хотя бы один корень.
if data < self.data сравнивает значение data с каждым левым поддеревом, возвращает «Данные не существуют» в случае исчерпания левого поддерева.
elif data > self.dataсравнивает значение data с каждым правым поддеревом, возвращает «Данные не существуют» в случае исчерпания правого поддерева.
Первый блок else запускается, когда сравнение data и значения в дереве оценивается как True.
Последний блок else возвращает «Пустое дерево» в случае отсутствия корня.
Вот оно. Вот как вставлять и искать структуру данных дерева на языке программирования Python.
В этой статье вы можете узнать об асимптотическом анализе, который проливает свет на важность оптимизации кода.
