class BSTNode:
def __init__(self, value):
self.value = value
self.left = self.right = None
class BSTree:
def __init__(self):
self._root = None
self._size = 0
def pre_order_traversal(self):
def pre_order(node):
if node is None: return
yield node.value
yield from pre_order(node.left)
yield from pre_order(node.right)
yield from pre_order(self._root)
def in_order_traversal(self):
def in_order(node):
if node is None: return
yield from in_order(node.left)
yield node.value
yield from in_order(node.right)
yield from in_order(self._root)
def post_order_traversal(self):
def post_order(node):
if node is None: return
yield from post_order(node.left)
yield from post_order(node.right)
yield node.value
yield from post_order(self._root)
@property
def size(self):
return self._size
def contains(self, value):
def _contains(node, value):
return (
False if node is None else
_contains(node.left, value) if value < node.value else
_contains(node.right, value) if value > node.value else
True
)
return _contains(self._root, value)
def insert(self, value):
def _insert(node, value):
if node is None:
return BSTNode(value)
elif value == node.value:
return None
elif value < node.value:
node.left = _insert(node.left, value)
elif value > node.value:
node.right = _insert(node.right, value)
return node
self._root = _insert(self._root, value)
if self._root:
self._size += 1
return self._root is not None
def remove(self, value):
def _remove(node, value):
if node.value == value:
if not (node.left and node.right):
return node.left or node.right, True
else:
# Replace the node with its next larger successor
successor, parent = node.right, node
while successor.left:
successor, parent = successor.left, successor
successor.left = node.left
if parent != node:
parent.left = successor.right
successor.right = node.right
return successor, True
elif value < node.value and node.left:
node.left, removed = _remove(node.left, value)
return node, removed
elif value > node.value and node.right:
node.right, removed = _remove(node.right, value)
return node, removed
return node, False
if self._root is None:
return False
self._root, removed = _remove(self._root, value)
self._size -= int(removed)
return removed
class BSTNode:
def __init__(self, value):
self.value = value
self.left = self.right = None
class BSTree:
def __init__(self):
self._root = None
self._size = 0
def pre_order_traversal(self):
def pre_order(node):
if node is None: return
yield node.value
yield from pre_order(node.left)
yield from pre_order(node.right)
yield from pre_order(self._root)
def in_order_traversal(self):
def in_order(node):
if node is None: return
yield from in_order(node.left)
yield node.value
yield from in_order(node.right)
yield from in_order(self._root)
def post_order_traversal(self):
def post_order(node):
if node is None: return
yield from post_order(node.left)
yield from post_order(node.right)
yield node.value
yield from post_order(self._root)
@property
def size(self):
return self._size
def contains(self, value):
def _contains(node, value):
return (
False if node is None else
_contains(node.left, value) if value < node.value else
_contains(node.right, value) if value > node.value else
True
)
return _contains(self._root, value)
def insert(self, value):
def _insert(node, value):
if node is None:
return BSTNode(value)
elif value == node.value:
return None
elif value < node.value:
node.left = _insert(node.left, value)
elif value > node.value:
node.right = _insert(node.right, value)
return node
self._root = _insert(self._root, value)
if self._root:
self._size += 1
return self._root is not None
def remove(self, value):
def _remove(node, value):
if node.value == value:
if not (node.left and node.right):
return node.left or node.right, True
else:
# Replace the node with its next larger successor
successor, parent = node.right, node
while successor.left:
successor, parent = successor.left, successor
successor.left = node.left
if parent != node:
parent.left = successor.right
successor.right = node.right
return successor, True
elif value < node.value and node.left:
node.left = _remove(node.left, value)
elif value > node.value and node.right:
node.right = _remove(node.right, value)
return node, False
if self._root is None:
return False
self._root, removed = _remove(self._root, value)
self._size -= int(removed)
return removed
class BSTNode:
def __init__(self, value):
self.value = value
self.left = self.right = None
class BSTree:
def __init__(self):
self._root = None
self._size = 0
def pre_order_traversal(self):
def pre_order(node):
if node is None: return
yield node.value
yield from pre_order(node.left)
yield from pre_order(node.right)
yield from pre_order(self._root)
def in_order_traversal(self):
def in_order(node):
if node is None: return
yield from in_order(node.left)
yield node.value
yield from in_order(node.right)
yield from in_order(self._root)
def post_order_traversal(self):
def post_order(node):
if node is None: return
yield from post_order(node.left)
yield from post_order(node.right)
yield node.value
yield from post_order(self._root)
@property
def size(self):
return self._size
def contains(self, value):
def _contains(node, value):
return (
False if node is None else
_contains(node.left, value) if value < node.value else
_contains(node.right, value) if value > node.value else
True
)
return _contains(self._root, value)
def insert(self, value):
def _insert(node, value):
if node is None:
return BSTNode(value)
elif value == node.value:
return None
elif value < node.value:
node.left = _insert(node.left, value)
elif value > node.value:
node.right = _insert(node.right, value)
return node
self._root = _insert(self._root, value)
if self._root:
self._size += 1
return self._root is not None
def remove(self, value):
def _remove(node, value):
if node.value == value:
if not (node.left and node.right):
return node.left or node.right, True
else:
# Replace the node with its next larger successor
successor, parent = node.right, node
while successor.left:
successor, parent = successor.left, successor
successor.left = node.left
if parent != node:
parent.left = successor.right
successor.right = node.right
return successor, True
elif value < node.value and node.left:
node.left, removed = _remove(node.left, value)
return node, removed
elif value > node.value and node.right:
node.right, removed = _remove(node.right, value)
return node, removed
return node, False
if self._root is None:
return False
self._root, removed = _remove(self._root, value)
self._size -= int(removed)
return removed
In __remove(), cases 1 and 2 can be condensed down to two lines. I've also renamed smallest_node to more clearly indicate that it refers to the smallestnext larger node to the right of the node being deletedin the tree.
class BSTNode:
def __init__(self, value):
self.value = value
self.left = self.right = None
class BSTree:
def __init__(self):
self._root = None
self._size = 0
def pre_order_traversal(self):
def pre_order(node):
if node is None: return
yield node.value
yield from pre_order(node.left)
yield from pre_order(node.right)
yield from pre_order(self._root)
def in_order_traversal(self):
def in_order(node):
if node is None: return
yield from in_order(node.left)
yield node.value
yield from in_order(node.right)
yield from in_order(self._root)
def post_order_traversal(self):
def post_order(node):
if node is None: return
yield from post_order(node.left)
yield from post_order(node.right)
yield node.value
yield from post_order(self._root)
@property
def size(self):
return self._size
def contains(self, value):
def _contains(node, value):
return (
False if node is None else
_contains(node.left, value) if value < node.value else
_contains(node.right, value) if value > node.value else
True
)
return _contains(self._root, value)
def insert(self, value):
def _insert(node, value):
if node is None:
return BSTNode(value)
elif value == node.value:
return None
elif value < node.value:
node.left = _insert(node.left, value)
elif value > node.value:
node.right = _insert(node.right, value)
return node
self._root = _insert(self._root, value)
if self._root:
self._size += 1
return self._root is not None
def remove(self, value):
def _remove(node, value):
if node.value == value:
if not (node.left and node.right):
return node.left or node.right, True
else:
right_smallest_node = node.right
# parentReplace =the node
with its next whilelarger right_smallest_node.left:successor
successor, parent = right_smallest_node
node.right, node
right_smallest_node =while right_smallest_nodesuccessor.left
:
if parent == node: # The right nodesuccessor, isparent the= smallestsuccessor.left, onesuccessor
right_smallest_nodesuccessor.left = node.left
else: #if Theparent smallest!= node is to the left of its right branch:
parent.left = right_smallest_nodesuccessor.right
right_smallest_node.left = node.left
right_smallest_nodesuccessor.right = node.right
return right_smallest_nodesuccessor, True
elif value < node.value and node.left:
node.left = _remove(node.left, value)
elif value > node.value and node.right:
node.right = _remove(node.right, value)
return node, False
if self._root is None:
return False
self._root, removed = _remove(self._root, value)
self._size -= int(removed)
return removed
In __remove(), cases 1 and 2 can be condensed down to two lines. I've also renamed smallest_node to more clearly indicate that it refers to the smallest node to the right of the node being deleted.
class BSTNode:
def __init__(self, value):
self.value = value
self.left = self.right = None
class BSTree:
def __init__(self):
self._root = None
self._size = 0
def pre_order_traversal(self):
def pre_order(node):
if node is None: return
yield node.value
yield from pre_order(node.left)
yield from pre_order(node.right)
yield from pre_order(self._root)
def in_order_traversal(self):
def in_order(node):
if node is None: return
yield from in_order(node.left)
yield node.value
yield from in_order(node.right)
yield from in_order(self._root)
def post_order_traversal(self):
def post_order(node):
if node is None: return
yield from post_order(node.left)
yield from post_order(node.right)
yield node.value
yield from post_order(self._root)
@property
def size(self):
return self._size
def contains(self, value):
def _contains(node, value):
return (
False if node is None else
_contains(node.left, value) if value < node.value else
_contains(node.right, value) if value > node.value else
True
)
return _contains(self._root, value)
def insert(self, value):
def _insert(node, value):
if node is None:
return BSTNode(value)
elif value == node.value:
return None
elif value < node.value:
node.left = _insert(node.left, value)
elif value > node.value:
node.right = _insert(node.right, value)
return node
self._root = _insert(self._root, value)
if self._root:
self._size += 1
return self._root is not None
def remove(self, value):
def _remove(node, value):
if node.value == value:
if not (node.left and node.right):
return node.left or node.right, True
else:
right_smallest_node = node.right
parent = node
while right_smallest_node.left:
parent = right_smallest_node
right_smallest_node = right_smallest_node.left
if parent == node: # The right node is the smallest one
right_smallest_node.left = node.left
else: # The smallest node is to the left of its right branch
parent.left = right_smallest_node.right
right_smallest_node.left = node.left
right_smallest_node.right = node.right
return right_smallest_node, True
elif value < node.value and node.left:
node.left = _remove(node.left, value)
elif value > node.value and node.right:
node.right = _remove(node.right, value)
return node, False
if self._root is None:
return False
self._root, removed = _remove(self._root, value)
self._size -= int(removed)
return removed
In __remove(), cases 1 and 2 can be condensed down to two lines. I've also renamed smallest_node to more clearly indicate that it refers to the next larger node in the tree.
class BSTNode:
def __init__(self, value):
self.value = value
self.left = self.right = None
class BSTree:
def __init__(self):
self._root = None
self._size = 0
def pre_order_traversal(self):
def pre_order(node):
if node is None: return
yield node.value
yield from pre_order(node.left)
yield from pre_order(node.right)
yield from pre_order(self._root)
def in_order_traversal(self):
def in_order(node):
if node is None: return
yield from in_order(node.left)
yield node.value
yield from in_order(node.right)
yield from in_order(self._root)
def post_order_traversal(self):
def post_order(node):
if node is None: return
yield from post_order(node.left)
yield from post_order(node.right)
yield node.value
yield from post_order(self._root)
@property
def size(self):
return self._size
def contains(self, value):
def _contains(node, value):
return (
False if node is None else
_contains(node.left, value) if value < node.value else
_contains(node.right, value) if value > node.value else
True
)
return _contains(self._root, value)
def insert(self, value):
def _insert(node, value):
if node is None:
return BSTNode(value)
elif value == node.value:
return None
elif value < node.value:
node.left = _insert(node.left, value)
elif value > node.value:
node.right = _insert(node.right, value)
return node
self._root = _insert(self._root, value)
if self._root:
self._size += 1
return self._root is not None
def remove(self, value):
def _remove(node, value):
if node.value == value:
if not (node.left and node.right):
return node.left or node.right, True
else:
# Replace the node with its next larger successor
successor, parent = node.right, node
while successor.left:
successor, parent = successor.left, successor
successor.left = node.left
if parent != node:
parent.left = successor.right
successor.right = node.right
return successor, True
elif value < node.value and node.left:
node.left = _remove(node.left, value)
elif value > node.value and node.right:
node.right = _remove(node.right, value)
return node, False
if self._root is None:
return False
self._root, removed = _remove(self._root, value)
self._size -= int(removed)
return removed
class BSTNode:
def __init__(self, value):
self.value = value
self.left = self.right = None
class BSTree:
def __init__(self):
self._root = None
self._size = 0
def pre_order_traversal(self):
def pre_order(node):
if node is None: return
yield node.value
yield from pre_order(node.left)
yield from pre_order(node.right)
yield from pre_order(self._root)
def in_order_traversal(self):
def in_order(node):
if node is None: return
yield from in_order(node.left)
yield node.value
yield from in_order(node.right)
yield from in_order(self._root)
def post_order_traversal(self):
def post_order(node):
if node is None: return
yield from post_order(node.left)
yield from post_order(node.right)
yield node.value
yield from post_order(self._root)
@property
def size(self):
return self._size
def contains(self, value):
def _contains(node, value):
return (
False if node is None else
_contains(node.left, value) if value < node.value else
_contains(node.right, value) if value > node.value else
True
)
return _contains(self._root, value)
def insert(self, value):
def _insert(node, value):
if node is None:
return BSTNode(value)
elif value == node.value:
return None
elif value < node.value:
node.left = _insert(node.left, value)
elif value > node.value:
node.right = _insert(node.right, value)
return node
self._root = _insert(self._root, value)
if self._root:
self._size += 1
return self._root is not None
def remove(self, value):
def _remove(node, value):
if node.value == value:
if not (node.left and node.right):
return node.left or node.right, True
else:
right_smallest_node = node.right
parent = node
while right_smallest_node.left:
parent = right_smallest_node
right_smallest_node = right_smallest_node.left
if parent == node: # The right node is the smallest one
right_smallest_node.left = node.left
else: # The smallest node is to the left of its right branch
parent.left = right_smallest_node.right
right_smallest_node.left = node.left
right_smallest_node.right = node.right
return right_smallest_node, True
else:
return node.left or node.right, True
elif value < node.value and node.left:
node.left = _remove(node.left, value)
elif value > node.value and node.right:
node.right = _remove(node.right, value)
return node, False
if self._root is None:
return False
self._root, removed = _remove(self._root, value)
self._size -= int(removed)
return removed
class BSTNode:
def __init__(self, value):
self.value = value
self.left = self.right = None
class BSTree:
def __init__(self):
self._root = None
self._size = 0
def pre_order_traversal(self):
def pre_order(node):
if node is None: return
yield node.value
yield from pre_order(node.left)
yield from pre_order(node.right)
yield from pre_order(self._root)
def in_order_traversal(self):
def in_order(node):
if node is None: return
yield from in_order(node.left)
yield node.value
yield from in_order(node.right)
yield from in_order(self._root)
def post_order_traversal(self):
def post_order(node):
if node is None: return
yield from post_order(node.left)
yield from post_order(node.right)
yield node.value
yield from post_order(self._root)
@property
def size(self):
return self._size
def contains(self, value):
def _contains(node, value):
return (
False if node is None else
_contains(node.left, value) if value < node.value else
_contains(node.right, value) if value > node.value else
True
)
return _contains(self._root, value)
def insert(self, value):
def _insert(node, value):
if node is None:
return BSTNode(value)
elif value == node.value:
return None
elif value < node.value:
node.left = _insert(node.left, value)
elif value > node.value:
node.right = _insert(node.right, value)
return node
self._root = _insert(self._root, value)
if self._root:
self._size += 1
return self._root is not None
def remove(self, value):
def _remove(node, value):
if node.value == value:
if node.left and node.right:
right_smallest_node = node.right
parent = node
while right_smallest_node.left:
parent = right_smallest_node
right_smallest_node = right_smallest_node.left
if parent == node: # The right node is the smallest one
right_smallest_node.left = node.left
else: # The smallest node is to the left of its right branch
parent.left = right_smallest_node.right
right_smallest_node.left = node.left
right_smallest_node.right = node.right
return right_smallest_node, True
else:
return node.left or node.right, True
elif value < node.value and node.left:
node.left = _remove(node.left, value)
elif value > node.value and node.right:
node.right = _remove(node.right, value)
return node, False
if self._root is None:
return False
self._root, removed = _remove(self._root, value)
self._size -= int(removed)
return removed
class BSTNode:
def __init__(self, value):
self.value = value
self.left = self.right = None
class BSTree:
def __init__(self):
self._root = None
self._size = 0
def pre_order_traversal(self):
def pre_order(node):
if node is None: return
yield node.value
yield from pre_order(node.left)
yield from pre_order(node.right)
yield from pre_order(self._root)
def in_order_traversal(self):
def in_order(node):
if node is None: return
yield from in_order(node.left)
yield node.value
yield from in_order(node.right)
yield from in_order(self._root)
def post_order_traversal(self):
def post_order(node):
if node is None: return
yield from post_order(node.left)
yield from post_order(node.right)
yield node.value
yield from post_order(self._root)
@property
def size(self):
return self._size
def contains(self, value):
def _contains(node, value):
return (
False if node is None else
_contains(node.left, value) if value < node.value else
_contains(node.right, value) if value > node.value else
True
)
return _contains(self._root, value)
def insert(self, value):
def _insert(node, value):
if node is None:
return BSTNode(value)
elif value == node.value:
return None
elif value < node.value:
node.left = _insert(node.left, value)
elif value > node.value:
node.right = _insert(node.right, value)
return node
self._root = _insert(self._root, value)
if self._root:
self._size += 1
return self._root is not None
def remove(self, value):
def _remove(node, value):
if node.value == value:
if not (node.left and node.right):
return node.left or node.right, True
else:
right_smallest_node = node.right
parent = node
while right_smallest_node.left:
parent = right_smallest_node
right_smallest_node = right_smallest_node.left
if parent == node: # The right node is the smallest one
right_smallest_node.left = node.left
else: # The smallest node is to the left of its right branch
parent.left = right_smallest_node.right
right_smallest_node.left = node.left
right_smallest_node.right = node.right
return right_smallest_node, True
elif value < node.value and node.left:
node.left = _remove(node.left, value)
elif value > node.value and node.right:
node.right = _remove(node.right, value)
return node, False
if self._root is None:
return False
self._root, removed = _remove(self._root, value)
self._size -= int(removed)
return removed
Loading
lang-py