Pythoner
Фотография
🌴BST - это древовидная структура данных, в которой каждый узел имеет максимум два потомка. Основное свойство BST заключается в том, что каждый узел на большее значение, чем все узлы в его левом поддереве и на меньшее значение, чем все узлы в его правом поддереве. Этот уникальный атрибут делает BST идеальным для быстрого поиска данных.
➡️Пример BST на Python:
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def insert(root, key):
if root is None:
return Node(key)
else:
if root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root
def inorder(root):
if root:
inorder(root.left)
print(root.val),
inorder(root.right)
r = Node(50)
r = insert(r, 30)
r = insert(r, 20)
r = insert(r, 40)
r = insert(r, 70)
r = insert(r, 60)
r = insert(r, 80)
inorder(r)
⬆️В этом примере мы создаем BST с помощью Python. Мы определяем класс Node, который представляет узел в BST. Затем мы определяем функции для вставки нового узла и для обхода BST.
➡️Преимущества и недостатки BST
BST имеют множество преимуществ, благодаря которым они широко используются. Они позволяют быстро осуществлять поиск, вставку и удаление данных. Однако BST также имеют некоторые недостатки. Например, если дерево не сбалансировано, время поиска может увеличиться.
То есть, по сути, это сортированное дерево, поиск в котором легко выполнить, из-за того, что оно упорядочено.
🐍 Pythoner
18 · 1.7K ·