En Python, il n'y a que dict comme type de carte standard. Ceci est implémenté dans le hachage en tant que structure de données. En tant que structure de données pouvant exprimer une carte d'une clé à un objet, une structure de données utilisant un arbre de recherche autre que le hachage est connue, mais elle n'existe pas dans la bibliothèque Python standard (en c ++, le std :: map de la dichotomie et l'implémentation du hachage Il y a std :: unordered_map). J'ai résumé les éléments nécessaires sous forme de type de carte standard et implémenté un simple arbre de recherche de 2 minutes.
--Accès avec d [x]: ʻobj .__ getitem __ (clé) --Ajouter un élément avecd [x] = y: ʻobj .__ setitem__ (clé, élément)
--for k in d: Itérer la clé dans une boucle: ʻobj .__ iter__ () --Vérifiez si la clé existe avecx dans d: ʻobj .__ contient__ (clé)
--Supprimer la clé x avec del d [x]: ʻobj .__ del item __ (clé) --ʻObj.keys (), ʻobj.item (), ʻobj.values return key, element, key et element tuple view object respectivement (dans cette implémentation, l'itérateur est retourné directement)
--L'objet de vue doit prendre en charge len (view_object), ʻiter (view_object) , x in view_object --Retournez le nombre d'éléments aveclen (d): ʻ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
Puisqu'il s'agit d'un demi-arbre, les clés peuvent être retournées dans l'ordre trié.
--d.pop (k, [d]) Renvoie KeyErrorquand il n'y a pas ded et k n'existe pas, et renvoie d quand il y a d et k n'existe pas. Comment dois-je implémenter ce comportement? (Pas un argument de mot-clé) -> Vous pouvez le faire en recevant l'argument avec * args et en le traitant vous-même.
J'ai l'impression de l'essayer pour le moment. Je suis désolé de ne pas avoir vérifié la plupart des méthodes désordonnées. De plus, je ne sais pas quoi faire à propos de la mise en œuvre, alors j'apprécierais que vous le précisiez.