Big News: Socket raises $60M Series C at a $1B valuation to secure software supply chains for AI-driven development.Announcement →
Sign In

binary_search_tree

Package Overview
Dependencies
Maintainers
1
Versions
16
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

binary_search_tree - rubygems Package Compare versions

Comparing version
1.21
 to
2.0
+7
-5
lib/binary_search_tree_hash.rb

@@ -43,3 +43,3 @@ class BinarySearchTreeHash

def values
map{ |node| node.second }
map{ |node| node.second }
end

@@ -60,3 +60,3 @@

def max
[@bst.max.key, @bst.max.value]
[@bst.max.key, @bst.max.value]
end

@@ -98,3 +98,3 @@

end
changed ? nodes.compact.map{ |node| [node.key, node.value] } : nil
changed ? nodes.compact.map{ |node| [node.key, node.value] } : nil
end

@@ -135,3 +135,3 @@

def has_value? value
@bst.find_value(value).present?
@bst.find_value(value).present?
end

@@ -192,2 +192,4 @@

end
end
end
+139
-97
lib/binary_search_tree.rb

@@ -0,1 +1,2 @@

require 'active_support/core_ext/object/blank'
class BinaryNode

@@ -137,3 +138,5 @@ attr_accessor :height, :parent, :left, :right, :key, :value

def put element, value, leaf, parent, link_type=nil
#once you reach a point where you can place a new node
if leaf.nil?
#create that new node
leaf = BinaryNode.new element, value, parent

@@ -152,4 +155,7 @@ @size += 1

if parent.present? && parent.height.zero?
#if it has a parent but it is balanced, move up
node = parent
node_to_rebalance = nil
#continue moving up until you git the root
while node.present?

@@ -163,2 +169,3 @@ node.height = node.max_children_height + 1

end
#if at any point you reach an unbalanced node, rebalance it
rebalance node_to_rebalance if node_to_rebalance.present?

@@ -209,2 +216,116 @@ end

def rrc_rebalance a, f
#puts "performing rrc rebalance"
b = a.right
c = b.right
assert a.present? && b.present? && c.present?
a.right = b.left
if a.right.present?
a.right.parent = a
end
b.left = a
a.parent = b
if f.nil?
@root = b
@root.parent = nil
else
if f.right == a
f.right = b
else
f.left = b
end
b.parent = f
end
recompute_heights a
recompute_heights b.parent
end
def rlc_rebalance a, f
#puts "performing rlc rebalance"
b = a.right
c = b.left
assert a.present? && b.present? && c.present?
b.left = c.right
if b.left.present?
b.left.parent = b
end
a.right = c.left
if a.right.present?
a.right.parent = a
end
c.right = b
b.parent = c
c.left = a
a.parent = c
if f.nil?
@root = c
@root.parent = nil
else
if f.right == a
f.right = c
else
f.left = c
end
c.parent = f
end
recompute_heights a
recompute_heights b
end
def llc_rebalance a, b, c, f
#puts "performing llc rebalance"
assert a.present? && b.present? && c.present?
a.left = b.right
if a.left
a.left.parent = a
end
b.right = a
a.parent = b
if f.nil?
@root = b
@root.parent = nil
else
if f.right == a
f.right = b
else
f.left = b
end
b.parent = f
end
recompute_heights a
recompute_heights b.parent
end
def lrc_rebalance a, b, c, f
#puts "performing lrc rebalance"
assert a.present? && b.present? && c.present?
a.left = c.right
if a.left.present?
a.left.parent = a
end
b.right = c.left
if b.right.present?
b.right.parent = b
end
c.left = b
b.parent = c
c.right = a
a.parent = c
if f.nil?
@root = c
@root.parent = nil
else
if f.right == a
f.right = c
else
f.left = c
end
c.parent = f
end
recompute_heights a
recompute_heights b
end
def rebalance node_to_rebalance

@@ -216,54 +337,6 @@ a = node_to_rebalance

# """Rebalance, case RRC """
b = a.right
c = b.right
assert a.present? && b.present? && c.present?
a.right = b.left
if a.right.present?
a.right.parent = a
end
b.left = a
a.parent = b
if f.nil?
@root = b
@root.parent = nil
else
if f.right == a
f.right = b
else
f.left = b
end
b.parent = f
end
recompute_heights a
recompute_heights b.parent
rrc_rebalance a, f
else
rlc_rebalance a, f
# """Rebalance, case RLC """
b = a.right
c = b.left
assert a.present? && b.present? && c.present?
b.left = c.right
if b.left.present?
b.left.parent = b
end
a.right = c.left
if a.right.present?
a.right.parent = a
end
c.right = b
b.parent = c
c.left = a
a.parent = c
if f.nil?
@root = c
@root.parent = nil
else
if f.right == a
f.right = c
else
f.left = c
end
c.parent = f
end
recompute_heights a
recompute_heights b
end

@@ -276,22 +349,3 @@ else

# """Rebalance, case LLC """
assert a.present? && b.present? && c.present?
a.left = b.right
if a.left
a.left.parent = a
end
b.right = a
a.parent = b
if f.nil?
@root = b
@root.parent = nil
else
if f.right == a
f.right = b
else
f.left = b
end
b.parent = f
end
recompute_heights a
recompute_heights b.parent
llc_rebalance a, b, c, f
else

@@ -301,28 +355,3 @@ b = a.left

# """Rebalance, case LRC """
assert a.present? && b.present? && c.present?
a.left = c.right
if a.left.present?
a.left.parent = a
end
b.right = c.left
if b.right.present?
b.right.parent = b
end
c.left = b
b.parent = c
c.right = a
a.parent = c
if f.nil?
@root = c
@root.parent = nil
else
if f.right == a
f.right = c
else
f.left = c
end
c.parent = f
end
recompute_heights a
recompute_heights b
lrc_rebalance a, b, c, f
end

@@ -487,2 +516,15 @@ end

require 'binary_search_tree_hash.rb'
# #require 'binary_search_tree_hash.rb'
# tree = BinarySearchTree.new
# puts "inserting 9"
# tree.insert(9, "nine")
# puts "inserting 5"
# tree.insert(5, "five")
# puts "inserting 10"
# tree.insert(10, "ten")
# puts "inserting 1"
# tree.insert(1, "ten")
# puts "inserting 3"
# tree.insert(3, "ten")
# puts "inserting 7"
# tree.insert(7, "ten")