binary_search_tree.py

#BST implementation
from binary_tree import BinaryTreeNode

class BSTNode(BinaryTreeNode):

  def __init__(self, key, val, left = None, right = None, parent = None) -> None:
      self.key = key
      self.val = val
      self.left = left
      self.right = right
      self.parent = parent
  
  def __str__(self) -> str:
    return "[{}]{} (P={})".format(self.key, self.val, self.parent.key if self.parent is not None else "None")

  # add or update
  # this implementation does not allow duplicate keys
  def insert(self, key, val) -> None:
    if self.key == key:
      self.val = val
      return
    if self.key < key:
      if self.right is None:
        self.right = BSTNode(key, val, None, None, self)
      else:
        self.right.insert(key, val)
    else:
      if self.left is None:
        self.left = BSTNode(key, val, None, None, self)
      else:
        self.left.insert(key, val)

  def find(self, key):
    if self.key == key:
      return self.val
    next = self.left if self.key > key else self.right
    if next is not None:
      return next.find(key)
    else:
      return None

  def range_query(self, low, high, action):
    greaterThanLow = self.key >= low
    smallerThanHigh = self.key < high
    if greaterThanLow and smallerThanHigh:
      action(self)
      if self.hasRight:
        self.right.range_query(low, high, action)
      if self.hasLeft:
        self.left.range_query(low, high, action)
    elif not greaterThanLow:
      if self.hasRight:
        self.right.range_query(low, high, action)
    elif not smallerThanHigh:
      if self.hasLeft:
        self.left.range_query(low, high, action)

  def min(self):
    current = self
    while current.hasLeft:
      current = current.left
    return current

  def max(self):
    current = self
    while current.hasRight:
      current = current.right
    return current

  def delete(self, key):
    if self.key < key:
      if self.hasRight:
        self.right.delete(key)
    elif self.key > key:
      if self.hasLeft:
        self.left.delete(key)
    else:
      temp = self
      if self.isLeaf:
        if self.parent is None:
          return
        if self.parent.right == self:
          self.parent.right = None
        else:
          self.parent.left = None
        return temp
      if not self.hasLeft:
        self.key = self.right.key
        self.val = self.right.val
        self.left = self.right.left
        self.right = self.right.right
        self.left.parent = self
        self.right.parent = self
        return temp
      if not self.hasRight:
        self.key = self.left.key
        self.val = self.left.val
        self.right = self.left.right
        self.left = self.left.left
        self.left.parent = self
        self.right.parent = self
        return temp
      minValInRight = self.right.min()
      self.key = minValInRight.key
      self.val = minValInRight.val
      self.right.delete(self.key)
      return temp