Búsqueda binaria Árbol en Python que no trabaja
-
28-09-2019 - |
Pregunta
class Node:
'''represents a new node in the BST'''
def __init__(self,key):
self.key=key
self.disconnect()
def disconnect(self):
self.left=None;
self.right=None;
self.parent=None;
def __str__(self):
return 'node with kay %s'%self.key
class BST:
def __init__(self):
self.root=None
def insert(self,t):
'''inserts a new element into the tree'''
self.find_place(self.root,t)
def find_place(self,node,key):
"""finds the right place of the element recursively"""
if node is None:
node=Node(key)
print node
else:
if node.key > key:
find_place(node.left,key)
else:
find_place(node.right,key)
def test():
'''function to test if the BST is working correctly'''
i escribió el código anterior para implementar un árbol binario de búsqueda, pero no funciona como se espera el método de inserción, que no puede agregar incluso el elemento raíz. No puedo undestand la causa.
Solución
Usted no es en realidad la adición de todos los nodos en el árbol!
Su más fácil de gestionar la adición del nodo raíz de forma explícita, como se ve a continuación lo hice en el insert
.
Función find_place
Una sería, presumiblemente, a partir del nombre, devolver el nodo padre y también si se trata de la ranura de la izquierda o derecha de la tecla? He hecho una función _do_insert
explícita a continuación que tanto paseos y hace el inserto.
A partir de entonces, tiene que recorrer el árbol, cada vez ver si Recurse un sarmiento o si usted ha alcanzado una ranura vacía, donde se agrega el nuevo nodo.
Puede ser que sea natural para refactorizar el código para poner la responsabilidad de recorrer el árbol (y haciendo añade, elimina y tal) en la clase Node
.
En el código siguiente, no hago caso de la adición de una clave que ya está en el árbol, que acaba de salir en silencio:
def insert(self,t):
'''inserts a new element into the tree'''
if self.root is None:
self.root = Node(t)
else:
self._do_insert(self.root,t)
def _do_insert(self,parent,t):
if t > parent.key:
if parent.left is None:
parent.left = Node(t)
else:
self._do_insert(parent.left,t)
elif t < parent.key:
if parent.right is None:
parent.right = Node(t)
else:
self._do_insert(parent.right,t)
else:
# raise a KeyError or something appropriate?
pass
Otros consejos
Aquí hay otro BST con Python, utilizando una clave de clasificación
izquierda = 0 Derecha = 1 VALUE = 2 SORT_KEY = -1
clase BinarySearchTree (objeto):
def __init__(self, sort_key=None):
self._root = []
self._sort_key = sort_key
self._len = 0
def insertar (self, val): si es self._sort_key Ninguno: sort_key val = // si no hay tecla de clasificación, clave de ordenación es el valor más: sort_key = self._sort_key (val)
node = self._root
while node:
if sort_key < node[_SORT_KEY]:
node = node[LEFT]
else:
node = node[RIGHT]
if sort_key is val:
node[:] = [[], [], val]
else:
node[:] = [[], [], val, sort_key]
self._len += 1
def minimum(self):
return self._extreme_node(LEFT)[VALUE]
def maximum(self):
return self._extreme_node(RIGHT)[VALUE]
def find(self, sort_key):
return self._find(sort_key)[VALUE]
def _extreme_node(self, side):
if not self._root:
raise IndexError('Empty')
node = self._root
while node[side]:
node = node[side]
return node
def _find(self, sort_key):
node = self._root
while node:
node_key = node[SORT_KEY]
if sort_key < node_key:
node = node[LEFT]
elif sort_key > node_key:
node = node[RIGHT]
else:
return node
raise KeyError("%r not found" % sort_key)
tecla de clasificación se sustituye por el valor de su caso.