Задание
Реализовать операцию удаления элемента из дерева поиска. Для упрощения решения (и отладки) к заданию прилагается минимальная реализация дерева поиска. В качестве решения можно добавить реализацию удаления элемента в прилагаемый пример, а можно самостоятельно реализовать дерево поиска с операцией удаления элемента. (Я старался сделать реализацию как можно более простой и минималистичной, чтобы из самого кода было понятно, что и как – в частности, я принёс комментарии в жертву минималистичности).
Пример реализации дерева
1 class Tree(object):
2
3 def __init__(self, items=()):
4 self.top = None
5 for item in items:
6 self.add(item)
7
8 def add(self, value):
9 if self.top is None:
10 self.top = Node(value)
11 else:
12 self.top.add(value)
13
14 def find(self, value):
15 return self.top.find(value)
16
17 def __str__(self):
18 if self.top is None:
19 return "<Tree>"
20 else:
21 return "<Tree {0}>".format(str(self.top))
22
23 class Node(object):
24
25 def __init__(self, value, left=None, right=None):
26 self.value = value
27 self.children = [left, right]
28
29 def add(self, value):
30 if value >= self.value:
31 child = 1
32 else:
33 child = 0
34 if self.children[child] is None:
35 self.children[child] = Node(value)
36 else:
37 self.children[child].add(value)
38
39 def find(self, value):
40 if self.value == value:
41 return self
42 elif value < self.value:
43 return self.children[0].find(value)
44 else:
45 return self.children[1].find(value)
46
47 def __str__(self):
48 result = repr(self.value)
49 if self.children[0]:
50 result = str(self.children[0]) + " < " + result
51 if self.children[1]:
52 result = result + " <= " + str(self.children[1])
53 return "({0})".format(result)
54
55 if __name__ == "__main__":
56
57 tree = Tree("hello, world")
58 print tree
59 print tree.find('o')