Python Implementation of Binary Lookup Tree Sample Code

2-fork lookup tree

All key smaller than V are stored in the left subtree of V All key larger than V are stored in the right subtree of V

Node of BST

class BSTNode(object):
  def __init__(self, key, value, left=None, right=None):
    self.key, self.value, self.left, self.right = key, value, left, right

2-tree lookup

How to find a specified node? According to the definition, we know that the key of the left subtree of each internal node is smaller than it, and the key of the right subtree is larger than it. Therefore, for the node search_key with search, start from the root node. If search_key is larger than the current key, go to the right subtree to find, otherwise go to the left subtree to find

NODE_LIST = [
  {'key': 60, 'left': 12, 'right': 90, 'is_root': True},
  {'key': 12, 'left': 4, 'right': 41, 'is_root': False},
  {'key': 4, 'left': 1, 'right': None, 'is_root': False},
  {'key': 1, 'left': None, 'right': None, 'is_root': False},
  {'key': 41, 'left': 29, 'right': None, 'is_root': False},
  {'key': 29, 'left': 23, 'right': 37, 'is_root': False},
  {'key': 23, 'left': None, 'right': None, 'is_root': False},
  {'key': 37, 'left': None, 'right': None, 'is_root': False},
  {'key': 90, 'left': 71, 'right': 100, 'is_root': False},
  {'key': 71, 'left': None, 'right': 84, 'is_root': False},
  {'key': 100, 'left': None, 'right': None, 'is_root': False},
  {'key': 84, 'left': None, 'right': None, 'is_root': False},
]


class BSTNode(object):
  def __init__(self, key, value, left=None, right=None):
    self.key, self.value, self.left, self.right = key, value, left, right


class BST(object):
  def __init__(self, root=None):
    self.root = root

  @classmethod
  def build_from(cls, node_list):
    cls.size = 0
    key_to_node_dict = {}
    for node_dict in node_list:
      key = node_dict['key']
      key_to_node_dict[key] = BSTNode(key, value=key)  #  The value here is the same as key1 Like 

    for node_dict in node_list:
      key = node_dict['key']
      node = key_to_node_dict[key]
      if node_dict['is_root']:
        root = node
      node.left = key_to_node_dict.get(node_dict['left'])
      node.right = key_to_node_dict.get(node_dict['right'])
      cls.size += 1
    return cls(root)

  def _bst_search(self, subtree, key):
    """
    subtree.key Less than key Go to the right subtree to find it   Because   Left subtree <subtree.key< Right subtree 
    subtree.key Greater than key Then go to the left subtree to find it   Because   Left subtree <subtree.key< Right subtree 
    :param subtree:
    :param key:
    :return:
    """
    if subtree is None:
      return None
    elif subtree.key < key:
      self._bst_search(subtree.right, key)
    elif subtree.key > key:
      self._bst_search(subtree.left, key)
    else:
      return subtree

  def get(self, key, default=None):
    """
     Search tree 
    :param key:
    :param default:
    :return:
    """
    node = self._bst_search(self.root, key)
    if node is None:
      return default
    else:
      return node.value

  def _bst_min_node(self, subtree):
    """
     Find the tree with the minimum value 
    :param subtree:
    :return:
    """
    if subtree is None:
      return None
    elif subtree.left is None:
      #  Find the head of the left subtree 
      return subtree
    else:
      return self._bst_min_node(subtree.left)

  def bst_min(self):
    """
     Object of the smallest tree value
    :return:
    """
    node = self._bst_min_node(self.root)
    if node is None:
      return None
    else:
      return node.value

  def _bst_max_node(self, subtree):
    """
     Find the tree with the maximum value 
    :param subtree:
    :return:
    """
    if subtree is None:
      return None
    elif subtree.right is None:
      #  Find the head of the right subtree 
      return subtree
    else:
      return self._bst_min_node(subtree.right)

  def bst_max(self):
    """
     Object of the largest tree value
    :return:
    """
    node = self._bst_max_node(self.root)
    if node is None:
      return None
    else:
      return node.value

  def _bst_insert(self, subtree, key, value):
    """
    2 Cross lookup tree insertion 
    :param subtree:
    :param key:
    :param value:
    :return:
    """
    #  Inserted node 1 Is the root node, including  root  Case where it is empty 
    if subtree is None:
      subtree = BSTNode(key, value)
    elif subtree.key > key:
      subtree.left = self._bst_insert(subtree.left, key, value)
    elif subtree.key < key:
      subtree.right = self._bst_insert(subtree.right, key, value)
    return subtree

  def add(self, key, value):
    #  Check first 1 See if the node already exists 
    node = self._bst_search(self.root, key)
    if node is not None:
      #  Update the existing  key
      node.value = value
      return False
    else:
      self.root = self._bst_insert(self.root, key, value)
      self.size += 1

  def _bst_remove(self, subtree, key):
    """
     Delete and return the root node 
    :param subtree:
    :param key:
    :return:
    """
    if subtree is None:
      return None
    elif subtree.key > key:
      subtree.right = self._bst_remove(subtree.right, key)
      return subtree
    elif subtree.key < key:
      subtree.left = self._bst_remove(subtree.left, key)
      return subtree
    else:
      #  Nodes to be deleted were found 
      #  The node to delete is a leaf node   Return  None  Set his father's pointer to it to  None
      if subtree.left is None and subtree.right is None:
        return None
      #  The nodes to delete are 1 A child 
      elif subtree.left is None or subtree.right is None:
        #  Return its child and let its father point to the past 
        if subtree.left is not None:
          return subtree.left
        else:
          return subtree.right
      else:
        #  Have two children, look for successor nodes to replace, and delete successor nodes from the right subtree of the point to be abridged 
        #  The successor node is the smallest node after the right child of the node to be deleted 
        #  Medium ( Root ) The order gets is 1 A arranged list   The successor node is after the node to be deleted 
        successor_node = self._bst_min_node(subtree.right)
        #  Replace the node to be deleted with a successor node to keep it 2 Characteristics of cross lookup tree   Left < Root < Right 
        subtree.key, subtree.value = successor_node.key, successor_node.value
        #  Delete the successor node from the right subtree of the node to be deleted, and update its right subtree after deleting the successor node 
        subtree.right = self._bst_remove(subtree.right, successor_node.key)
        return subtree

  def remove(self, key):
    assert key in self
    self.size -= 1
    return self._bst_remove(self.root, key)

The above is the Python implementation of 2-fork lookup tree example code details, more about Python implementation of 2-fork lookup tree information please pay attention to other related articles on this site!