In Python gibt es nur Diktate als Standardkartentyp. Dies wird in Hash als Datenstruktur implementiert. Als Datenstruktur, die eine Zuordnung von einem Schlüssel zu einem Objekt ausdrücken kann, ist eine Datenstruktur bekannt, die einen anderen Suchbaum als Hash verwendet, jedoch nicht in der Standard-Python-Bibliothek vorhanden ist (in c ++ die std :: map der Dichotomie und die Hash-Implementierung) Es gibt std :: unordered_map). Ich habe die erforderlichen Elemente als Standardkartentyp zusammengefasst und einen einfachen 2-Minuten-Suchbaum implementiert.
d [x]: obj .__ getitem__ (Schlüssel)d [x] = y hinzu:obj .__ setitem__ (Schlüssel, Element)
--for k in d: Iteriere den Schlüssel in einer Schleife:obj .__ iter__ ()
--Überprüfen Sie, ob der Schlüssel mit x in d vorhanden ist:obj .__ enthält__ (Schlüssel)del d [x]: obj .__ delitem__ (Schlüssel)
--obj.keys () ,obj.item (), obj.values Rückgabeschlüssel, Element, Schlüssel und Element-Tupel-Ansichtsobjekt (in dieser Implementierung wird der Iterator direkt zurückgegeben)len (d) zurück: obj .__ len__ ()python
import queue
class BinaryTree(object):
class Node(object):
def __init__(self, _key=None, _item=None):
self.key = _key
self.item = _item
self.left = None
self.right = None
def __repr__(self):
return str(self.key)+': '+str(self.item)
def __str__(self):
return self.__repr__()
def __init__(self, *args, **kargs):
self.size = 0
self.head = None
if len(args):
for key, item in args:
self.insert(key, item)
elif len(kargs):
for key in kargs:
self.insert(key, kargs[key])
def search(self, key):
return self._search(key, self.head, self.head)[0]
def _search(self, key, node, parent):
if not node:
return None, parent
if key == node.key :
return node, parent
elif key < node.key:
return self._search(key, node.left, node)
else:
return self._search(key, node.right, node)
def insert(self, key, item):
if not self.head:
self.head = self.Node(key, item)
self.size += 1
return
n, p = self._search(key, self.head, self.head)
if n:
n.item = item
else:
self.size += 1
if key < p.key:
p.left = self.Node(key, item)
else:
p.right = self.Node(key, item)
def delete(self, key):
n, p = self._search(key, self.head, self.head)
if n == p:
self.head = None
self.size -= 1
else:
self._delete(key, n, p)
def _delete(self, key, node, parent):
if node:
if not node.left and not node.right:
if parent.left == node:
parent.left = None
else:
parent.right = None
del node
self.size -= 1
elif node.left and node.right:
if parent.left == node:
right_min, right_min_parent = self.min_key_node(node.right, node)
node.key = right_min.key
node.item = right_min.item
self._delete(node.key, right_min, right_min_parent)
else:
left_max, left_max_parent = self.max_key_node(node.left, node)
node.key = left_max.key
node.item = left_max.item
self._delete(node.key, left_max, left_max_parent)
elif node.left:
if parent.left == node:
parent.left = node.left
else:
parent.right = node.left
del node
self.size -= 1
else:
if parent.left == node:
parent.left = node.right
else:
parent.right = node.right
del node
self.size -= 1
def min_key_node(self, node, parent):
if not node.left:
return node, parent
else:
return self.min_key_node(node.left, node)
def max_key_node(self, node, parent):
if not node.right:
return node, parent
else:
return self.max_key_node(node.right, node)
def in_order_traverse(self, use_keys=True, use_items=True):
if self.head:
yield from self._in_order_traverse(self.head, use_keys, use_items)
def _in_order_traverse(self, node, use_keys, use_items):
if node.left:
yield from self._in_order_traverse(node.left, use_keys, use_items)
if use_keys and use_items:
yield node.key, node.item
elif use_keys:
yield node.key
else:
yield node.item
if node.right:
yield from self._in_order_traverse(node.right, use_keys, use_items)
def clear(self):
while self.head:
self._delete(self.head.key)
def copy(self):
return BinaryTree(self.items())
def get(self, key, default=None):
n = self.search(key)
if n:
return n.item
else:
return default
def pop(self, key):
n = self.search(key)
if n:
i = n.item
self.delete(key)
return i
else:
self.__missing__(key)
def __getitem__(self, key):
n = self.search(key)
if n:
return n.item
else:
self.__missing__(key)
def __missing__(self, key):
raise KeyError(key)
def __setitem__(self, key, item):
return self.insert(key, item)
def __delitem__(self, key):
return self.delete(key)
def __iter__(self):
return self.in_order_traverse(use_keys=True, use_items=False)
def __reversed__(self):
return BinaryTreeIter(self.head, reverse=True)
def __contains__(self, key):
if self.search(self.head):
return True
else:
return False
def __len__(self):
return self.size
def items(self):
return self.in_order_traverse()
def keys(self):
return self.in_order_traverse(use_keys=True, use_items=False)
def values(self):
return self.in_order_traverse(use_keys=False, use_items=True)
def __repr__(self):
out = []
for key, item in self.items():
out.append(str(key)+': '+str(item))
return '{'+', '.join(out)+'}'
def __str__(self):
return self.__repr__()
>>> import random
>>> bt = BinaryTree()
>>> random_data = list(range(20))
>>> random.shuffle(random_data)
>>> for k in random_data:
bt[k] += k**2
>>> bt[10] = -1
>>> for k in bt:
print('key:', k, 'value:', bt[k], end=', ')
key: 0 value: 0, key: 1 value: 1, key: 2 value: 4, key: 3 value: 9, key: 4 value: 16, key: 5 value: 25, key: 6 value: 36, key: 7 value: 49, key: 8 value: 64, key: 9 value: 81, key: 10 value: -1, key: 11 value: 121, key: 12 value: 144, key: 13 value: 169, key: 14 value: 196, key: 15 value: 225, key: 16 value: 256, key: 17 value: 289, key: 18 value: 324, key: 19 value: 361,
>>> bt[100]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/Volumes/Macintosh_HD/Users/user/std_tree.py", line 178, in __getitem__
self.__missing__(key)
File "/Volumes/Macintosh_HD/Users/user/std_tree.py", line 181, in __missing__
raise KeyError(key)
KeyError: 100
Da es sich um einen halben Baum handelt, können die Schlüssel in der sortierten Reihenfolge zurückgegeben werden.
--`d.pop (k, [d]) Gibt "KeyError" zurück, wenn es kein "d" gibt und "k" nicht existiert, und gibt d zurück, wenn es d gibt und "k" nicht existiert. Wie soll ich dieses Verhalten implementieren? (Kein Schlüsselwortargument) -> Sie können dies tun, indem Sie das Argument mit * args empfangen und selbst verarbeiten.
Ich habe das Gefühl, ich habe es vorerst versucht. Es tut mir leid, dass ich die meisten unordentlichen Methoden nicht überprüft habe. Außerdem weiß ich nicht, was ich mit der Implementierung tun soll, daher würde ich mich freuen, wenn Sie darauf hinweisen könnten.
Recommended Posts