fork download
copy 
  1. class Node:
  2.     def __init__(self, key, val):
  3.         self.key = key
  4.         self.value = val
  5.         self.left = None
  6.         self.right = None
  7.         self.count = 1
  8.  
  9. class BST:
  10.     def __init__(self):
  11.         self.__root = None
  12.  
  13.     def size(self, x=None):
  14.         if x is None:
  15.             x = self.__root
  16.         return 0 if x is None else x.count
  17.  
  18.     def put(self, key, val):
  19.         self.__root = self.__put(self.__root, key, val)
  20.  
  21.     def __put(self, x, key, val):
  22.         if x is None:
  23.             return Node(key, val)
  24.         if key < x.key:
  25.             x.left = self.__put(x.left, key, val)
  26.         elif key > x.key:
  27.             x.right = self.__put(x.right, key, val)
  28.         else:
  29.             x.value = val
  30.         x.count = 1 + self.size(x.left) + self.size(x.right)
  31.         return x
  32.  
  33.     def get(self, key):
  34.         x = self.__root
  35.         while x is not None:
  36.             if key < x.key:
  37.                 x = x.left
  38.             elif key > x.key:
  39.                 x = x.right
  40.             else:
  41.                 return x.value
  42.         return None
  43.  
  44.     def min(self, x=None):
  45.         if x is None:
  46.             x = self.__root
  47.         if x is None:
  48.             return None
  49.         while x.left is not None:
  50.             x = x.left
  51.         return x
  52.  
  53.     def delete_min(self, x=None):
  54.         if x is None:
  55.             x = self.__root
  56.             if x is None:
  57.                 return None
  58.             self.__root = self.__delete_min(x)
  59.         else:
  60.             return self.__delete_min(x)
  61.  
  62.     def __delete_min(self, x):
  63.         if x.left is None:
  64.             return x.right
  65.         x.left = self.__delete_min(x.left)
  66.         x.count = 1 + self.size(x.left) + self.size(x.right)
  67.         return x
  68.  
  69.     def delete(self, key):
  70.         self.__root = self.__delete(self.__root, key)
  71.  
  72.     def __delete(self, x, key):
  73.         if x is None:
  74.             return None
  75.         if key < x.key:
  76.             x.left = self.__delete(x.left, key)
  77.         elif key > x.key:
  78.             x.right = self.__delete(x.right, key)
  79.         else:
  80.             if x.right is None:
  81.                 return x.left
  82.             if x.left is None:
  83.                 return x.right
  84.  
  85.             t = x
  86.             x = self.min(t.right)
  87.             x.right = self.__delete_min(t.right)
  88.             x.left = t.left
  89.             x.count = self.size(x.left) + self.size(x.right) + 1
  90.             return x
  91.  
  92.         x.count = 1 + self.size(x.left) + self.size(x.right)
  93.         return x
  94.  
  95.     def inorder(self):
  96.         keys = []
  97.         self.__inorder(self.__root, keys)
  98.         return keys
  99.  
  100.     def __inorder(self, x, keys):
  101.         if x is None:
  102.             return
  103.         self.__inorder(x.left, keys)
  104.         keys.append(x.key)
  105.         self.__inorder(x.right, keys)
Success #stdin #stdout 0.12s 14136KB
comments (?)
stdin
copy 
45
stdout
copy 
Standard output is empty
https://ideone.com/wEH2pM
language:
Python 3 (python  3.12)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!