Я знаю, что много хороших решений уже опубликовано, но у меня обычно есть другой подход для бинарных деревьев: переход с некоторым классом Node и его непосредственная реализация более читабельны, но когда у вас много узлов, это может стать очень жадным в отношении памяти поэтому я предлагаю добавить один уровень сложности и сохранить узлы в списке Python, а затем моделировать поведение дерева, используя только список.
Вы все еще можете определить класс Node для окончательного представления узлов в дереве, когда это необходимо, но при сохранении их в простой форме [значение, слева, справа] в списке будет использоваться половина памяти или меньше!
Вот краткий пример класса дерева двоичного поиска, хранящего узлы в массиве. Он обеспечивает основные функции, такие как добавить, удалить, найти ...
"""
Basic Binary Search Tree class without recursion...
"""
__author__ = "@fbparis"
class Node(object):
__slots__ = "value", "parent", "left", "right"
def __init__(self, value, parent=None, left=None, right=None):
self.value = value
self.parent = parent
self.left = left
self.right = right
def __repr__(self):
return "<%s object at %s: parent=%s, left=%s, right=%s, value=%s>" % (self.__class__.__name__, hex(id(self)), self.parent, self.left, self.right, self.value)
class BinarySearchTree(object):
__slots__ = "_tree"
def __init__(self, *args):
self._tree = []
if args:
for x in args[0]:
self.add(x)
def __len__(self):
return len(self._tree)
def __repr__(self):
return "<%s object at %s with %d nodes>" % (self.__class__.__name__, hex(id(self)), len(self))
def __str__(self, nodes=None, level=0):
ret = ""
if nodes is None:
if len(self):
nodes = [0]
else:
nodes = []
for node in nodes:
if node is None:
continue
ret += "-" * level + " %s\n" % self._tree[node][0]
ret += self.__str__(self._tree[node][2:4], level + 1)
if level == 0:
ret = ret.strip()
return ret
def __contains__(self, value):
if len(self):
node_index = 0
while self._tree[node_index][0] != value:
if value < self._tree[node_index][0]:
node_index = self._tree[node_index][2]
else:
node_index = self._tree[node_index][3]
if node_index is None:
return False
return True
return False
def __eq__(self, other):
return self._tree == other._tree
def add(self, value):
if len(self):
node_index = 0
while self._tree[node_index][0] != value:
if value < self._tree[node_index][0]:
b = self._tree[node_index][2]
k = 2
else:
b = self._tree[node_index][3]
k = 3
if b is None:
self._tree[node_index][k] = len(self)
self._tree.append([value, node_index, None, None])
break
node_index = b
else:
self._tree.append([value, None, None, None])
def remove(self, value):
if len(self):
node_index = 0
while self._tree[node_index][0] != value:
if value < self._tree[node_index][0]:
node_index = self._tree[node_index][2]
else:
node_index = self._tree[node_index][3]
if node_index is None:
raise KeyError
if self._tree[node_index][2] is not None:
b, d = 2, 3
elif self._tree[node_index][3] is not None:
b, d = 3, 2
else:
i = node_index
b = None
if b is not None:
i = self._tree[node_index][b]
while self._tree[i][d] is not None:
i = self._tree[i][d]
p = self._tree[i][1]
b = self._tree[i][b]
if p == node_index:
self._tree[p][5-d] = b
else:
self._tree[p][d] = b
if b is not None:
self._tree[b][1] = p
self._tree[node_index][0] = self._tree[i][0]
else:
p = self._tree[i][1]
if p is not None:
if self._tree[p][2] == i:
self._tree[p][2] = None
else:
self._tree[p][3] = None
last = self._tree.pop()
n = len(self)
if i < n:
self._tree[i] = last[:]
if last[2] is not None:
self._tree[last[2]][1] = i
if last[3] is not None:
self._tree[last[3]][1] = i
if self._tree[last[1]][2] == n:
self._tree[last[1]][2] = i
else:
self._tree[last[1]][3] = i
else:
raise KeyError
def find(self, value):
if len(self):
node_index = 0
while self._tree[node_index][0] != value:
if value < self._tree[node_index][0]:
node_index = self._tree[node_index][2]
else:
node_index = self._tree[node_index][3]
if node_index is None:
return None
return Node(*self._tree[node_index])
return None
Я добавил родительский атрибут, чтобы вы могли удалить любой узел и поддерживать структуру BST.
Извините за удобочитаемость, особенно за функцию «удалить». По сути, когда узел удаляется, мы выталкиваем массив дерева и заменяем его последним элементом (кроме случаев, когда мы хотим удалить последний узел). Чтобы поддерживать структуру BST, удаленный узел заменяется максимальным количеством его левых дочерних элементов или минимумом его правых дочерних элементов, и необходимо выполнить некоторые операции, чтобы индексы были действительными, но это достаточно быстро.
Я использовал эту технику для более продвинутых вещей, чтобы создать словари больших слов с внутренним трихом, и я смог разделить потребление памяти на 7-8 (вы можете увидеть пример здесь: https://gist.github.com/fbparis/b3ddd5673b603b42c880974b23db7cda)