class Tree::BST
This is implementation Binary search tree using Tree::BinaryNode
Attributes
length[R]
Public Class Methods
new()
click to toggle source
# File lib/data_struct/tree.rb, line 26 def initialize @root = nil @length, @height = 0 @state_arr = [] end
Public Instance Methods
delete(key, node = @root)
click to toggle source
# File lib/data_struct/tree.rb, line 50 def delete(key, node = @root) return @root = node if node.nil? if key < node.data node.left = delete(key, node.left) elsif key > node.data node.right = delete(key, node.right) else if node.left.nil? temp = node.right node = nil return temp elsif node.right.nil? temp = node.left node = nil return temp end temp = min(node.right) node.data = temp.data node.right = delete(temp.data, node.right) end @root = node end
empty?()
click to toggle source
# File lib/data_struct/tree.rb, line 80 def empty? @length.zero? end
find(val)
click to toggle source
# File lib/data_struct/tree.rb, line 74 def find val recur_search @root, val end
height?()
click to toggle source
# File lib/data_struct/tree.rb, line 83 def height? recur_max_depth @root end
insert(val)
click to toggle source
# File lib/data_struct/tree.rb, line 32 def insert val in_length @root = recur_insert @root, val end
max(node = @root)
click to toggle source
# File lib/data_struct/tree.rb, line 43 def max(node = @root) cur = node unless node.right.nil? cur = cur.right end cur end
min(node = @root)
click to toggle source
# File lib/data_struct/tree.rb, line 36 def min(node = @root) cur = node unless node.left.nil? cur = cur.left end cur end
to_a()
click to toggle source
# File lib/data_struct/tree.rb, line 77 def to_a recur_pre_order @root, [] end
Private Instance Methods
de_length()
click to toggle source
# File lib/data_struct/tree.rb, line 131 def de_length @length -= 1 end
in_length()
click to toggle source
# File lib/data_struct/tree.rb, line 127 def in_length @length += 1 end
recur_insert(node, val)
click to toggle source
# File lib/data_struct/tree.rb, line 88 def recur_insert node, val return BinaryNode.new(val) if node.nil? if val < node.data node.left = recur_insert(node.left, val) elsif val > node.data node.right = recur_insert(node.right, val) end node end
recur_max_depth(node)
click to toggle source
# File lib/data_struct/tree.rb, line 116 def recur_max_depth node return 0 if node.nil? left_depth = recur_max_depth(node.left) right_depth = recur_max_depth(node.right) if left_depth > right_depth return left_depth + 1 else return right_depth + 1 end end
recur_pre_order(node, state)
click to toggle source
# File lib/data_struct/tree.rb, line 109 def recur_pre_order node, state return if node.nil? state << node.data recur_pre_order(node.left, state) recur_pre_order(node.right, state) state end
recur_search(node, val)
click to toggle source
# File lib/data_struct/tree.rb, line 98 def recur_search node, val if node.nil? || node.data == val return node end if node.data < val return recur_search(node.right, val) end recur_search(node.left, val) end