135 lines
3.6 KiB
Python
135 lines
3.6 KiB
Python
class Node:
|
|
def __init__(self, value):
|
|
self.value = value
|
|
self.parent = None
|
|
self.right = None
|
|
self.left = None
|
|
|
|
def min_tree(self):
|
|
return self.min_value(self)
|
|
|
|
def successor(self):
|
|
node = self
|
|
if self.right is not None:
|
|
return self.min_value(self.right)
|
|
parent = self.parent
|
|
while parent is not None and node == parent.right:
|
|
node = parent
|
|
parent = parent.parent
|
|
return parent
|
|
|
|
def min_value(self, node):
|
|
current = node
|
|
while current.left is not None:
|
|
current = current.left
|
|
return current
|
|
|
|
def free(self):
|
|
self.right = None
|
|
self.left = None
|
|
self.parent = None
|
|
|
|
def __str__(self):
|
|
return str(self.value)
|
|
|
|
|
|
class Bstree:
|
|
|
|
def search_recursive(self, key):
|
|
return self.recursive_search(key, self.root)
|
|
|
|
def recursive_search(self, key, node):
|
|
if node is None or node.value == key:
|
|
return node
|
|
if key < node.value:
|
|
return self.recursive_search(key, node.left)
|
|
return self.recursive_search(key, node.right)
|
|
|
|
def search_iterative(self, key):
|
|
node = self.root
|
|
while node is not None and node.value != key:
|
|
if key < node.value:
|
|
node = node.left
|
|
else:
|
|
node = node.right
|
|
return node
|
|
|
|
def __init__(self, root):
|
|
self.toPrint = []
|
|
self.root = root
|
|
|
|
def insert_after(self, node, parent):
|
|
if node.value < parent.value:
|
|
if parent.left is not None:
|
|
self.insert_after(node, parent.left)
|
|
else:
|
|
parent.left = node
|
|
node.parent = parent
|
|
|
|
if node.value > parent.value:
|
|
if parent.right is not None:
|
|
self.insert_after(node, parent.right)
|
|
else:
|
|
parent.right = node
|
|
node.parent = parent
|
|
|
|
def insert(self, node):
|
|
self.insert_after(node, self.root)
|
|
|
|
def write(self):
|
|
self.print_node(self.root, 0)
|
|
|
|
def print_node(self, node, level):
|
|
if node.right is not None:
|
|
self.print_node(node.right, level + 1)
|
|
print("\t" * level + str(node.value))
|
|
if node.left is not None:
|
|
self.print_node(node.left, level + 1)
|
|
|
|
def transplant(self, node1, node2):
|
|
node1.parent = node2.parent
|
|
if node2.parent.left == node2:
|
|
node2.parent.left = node1
|
|
else:
|
|
node2.parent.right = node1
|
|
node2.free()
|
|
|
|
def delete(self, node):
|
|
if node.left is None and node.right is None:
|
|
if node.parent.left == node:
|
|
node.parent.left = None
|
|
else:
|
|
node.parent.right = None
|
|
|
|
if node.left is None and node.right is not None:
|
|
self.transplant(node.right, node)
|
|
|
|
if node.left is not None and node.right is None:
|
|
self.transplant(node.left, node)
|
|
|
|
if node.left is not None and node.right is not None:
|
|
temp = node.min_value(node.right)
|
|
node.value = temp.value
|
|
if temp.left:
|
|
node = temp.left
|
|
else:
|
|
node = temp.right
|
|
if node:
|
|
node.parent = temp.parent
|
|
if temp.parent is None:
|
|
self.root = node
|
|
if temp == temp.parent.left:
|
|
temp.parent.left = node
|
|
else:
|
|
temp.parent.right = node
|
|
|
|
|
|
def main():
|
|
for i in range(1, 20):
|
|
print(i % 2)
|
|
|
|
return 0
|
|
|
|
|
|
if __name__ == '__main__':
|
|
main() |