fork download
copy 
  1. class BSTNode
  2.     attr_accessor :key, :value, :left, :right, :size
  3.     def initialize(k = nil, v = nil, s = 1)
  4.         @key = k
  5.         @value = v
  6.         @size = s
  7.         @left = nil
  8.         @right = nil
  9.     end
  10. end
  11. class BST
  12.     attr_accessor :root
  13.     def initialize
  14.         @root = nil
  15.     end
  16.  
  17.     def insert(k, v)
  18.         if @root
  19.             @root = BST.insert_helper!(@root, k, v)
  20.         else
  21.             @root = BSTNode.new(k, v, 1)
  22.         end
  23.     end
  24.  
  25.     def delete(k)
  26.         if k
  27.             root = BST.delete_helper!(@root, k)
  28.         end
  29.     end
  30.  
  31.     def get(k)
  32.         if k
  33.             BST.get_helper!(@root, k)
  34.         end
  35.     end
  36.  
  37.     def inorder
  38.         BST.inorder!(@root)
  39.     end
  40.  
  41.     private
  42.     def self.delete_min!(x)
  43.         return x.right if x.left == nil
  44.         x.left = delete_min!(x.left)
  45.         x.size = size(x.left) + size(x.right) + 1
  46.     end
  47.  
  48.     def self.min!(x)
  49.         return x if x.left == nil
  50.         min(x.left)
  51.     end
  52.  
  53.  
  54.     def self.inorder!(x)
  55.         if x == nil
  56.            return 
  57.         end
  58.  
  59.         inorder!(x.left)
  60.         puts "Key: #{x.key}, Value: #{x.value}"
  61.         inorder!(x.right)
  62.     end
  63.  
  64.     def self.get_helper!(x, k)
  65.         if x == nil
  66.             nil
  67.         elsif k > x.key
  68.             get_helper!(x.right, k)
  69.         elsif k < x.key
  70.             get_helper!(x.left, k)
  71.         else
  72.             x.value
  73.         end
  74.     end
  75.  
  76.     def self.delete_helper!(x, k)
  77.         if x == nil
  78.             nil
  79.         elsif k < x.key
  80.             x.left = delete_helper!(x.left, k)
  81.         elsif k > x.key
  82.             x.right = delete_helper!(x.right, k)
  83.         else
  84.             # Handles case of one children or no children
  85.             return x.left if x.right == nil
  86.             return x.right if x.left == nil
  87.  
  88.             # Handle case 3 of two children
  89.             # Find successor of x called succ, which should be in right subtree
  90.             # succ replaces x in tree, delete succ from tree and replace x
  91.             # x right subtree becomes succ right subtree
  92.             # x left subtree becomes succ left subtree
  93.             # if succ is x right child, then replace x with succ and leave succ right child
  94.             # if succ is not x right child but in right subtree
  95.                 # replace succ with its own right child
  96.             temp = x
  97.             x = min!(temp.right)
  98.             x.left = temp.left # does order matter?
  99.             x.right = delete_min!(temp)
  100.         end
  101.         x = size!(x.left) + size!(x.right) + 1
  102.         x
  103.     end
  104.  
  105.     def self.size!(x)
  106.         if x == nil
  107.             0
  108.         else
  109.             x.size
  110.         end
  111.     end
  112.  
  113.     def self.insert_helper!(x, k, v)
  114.         if x == nil
  115.             return BSTNode.new(k, v, 1)
  116.         elsif k < x.key
  117.             x.left = insert_helper!(x.left, k, v)
  118.         elsif k > x.key
  119.             x.right = insert_helper!(x.right, k, v)
  120.         else
  121.             x.value = v
  122.         end
  123.         x.size = size!(x.left) + size!(x.right) + 1
  124.         x
  125.     end
  126. end
  127.  
  128. b = BST.new
  129. b.insert(5, "c")
  130. b.insert(4, "b")
  131. b.insert(6, "d")
  132. b.insert(3, "a")
  133. b.insert(7, "e")
  134. b.inorder
  135. p b.get(3)
  136. b.delete(6)
  137. b.inorder
  138.  
  139.  
  140. def mirrored?(left, right)
  141.     return (left == nil && right == nil) if right == nil || left == nil
  142.     left.value == right.value && mirrored?(left.left, right.right) && mirrored(left.right, right.left)
  143. end
  144.  
  145.  
  146. # This code can be used to make BST into balanced BST
  147. a = [5,7,12,15,18,20]
  148. # Nondecreasing array to balanced BST
  149. def arrtobst(a, bst)
  150.     if a.length == 1
  151.         p a[0]
  152.         bst.insert(a[0], "temp")
  153.     elsif a.length > 1
  154.         mid_idx = a.length/2
  155.         p a[mid_idx]
  156.         bst.insert(a[mid_idx], "temp")
  157.         arrtobst(a.take(mid_idx), bst)
  158.         arrtobst(a.drop(mid_idx + 1), bst)
  159.     end
  160. end
  161. a2 = [1,2,3,4,5]
  162. p "Array to BST"
  163. bstree = BST.new
  164. arrtobst(a, bstree)
  165. bstree.inorder
  166. btt = BST.new
  167. btt = arrtobst(a2, btt)
  168. btt.inorder
Runtime error #stdin #stdout #stderr 0s 28688KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Key: 3, Value: a
Key: 4, Value: b
Key: 5, Value: c
Key: 6, Value: d
Key: 7, Value: e
"a"
Key: 3, Value: a
Key: 4, Value: b
Key: 5, Value: c
Key: 7, Value: e
"Array to BST"
15
7
5
12
20
18
Key: 5, Value: temp
Key: 7, Value: temp
Key: 12, Value: temp
Key: 15, Value: temp
Key: 18, Value: temp
Key: 20, Value: temp
3
2
1
5
4
stderr
copy 
prog.rb:168:in `<main>': undefined method `inorder' for nil:NilClass (NoMethodError)
https://ideone.com/Bm7YMy
language:
Ruby (ruby 2.5.5)
created:
7 years 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!