armcburney/ruby-ds
Common algorithms and data structures written in Ruby.
Purpose
This repository provides the implementation of various algorithms in Ruby. The purpose of this repository is to re-acquaint myself with various algorithms used in computer science, as well as their spacial and time complexities.
Data Structures
Binary Tree
insert
Recursively inserts a new node into the tree. Time complexity: O(n) worst case O(log(n)) average case @param [Algorithms::Node] node @param [Algorithms::Node] curr
delete
Recursively deletes a node if it exists in the tree. Time complexity: O(n) worst case O(log(n)) average case @param [Algorithms::Node] node
find_node
Finds and returns a node with the value in a subtree. Time complexity: O(n) worst case O(log(n)) average case @param [Integer] val @param [Algorithms::Node] node @return [Algorithms::Node]
height
Returns the height of the tree. Time complexity: O(n) worst case O(log(n)) average case @param [Algorithms::Node] node @param [Integer] h @return [Integer]
find_min
Finds and returns the minimum element in a subtree. Time complexity: O(n) worst case O(log(n)) average case @param [Algorithms::Node] node @return [Algorithms::Node]
find_max
Finds and returns the maximum element in a subtree. Time complexity: O(n) worst case O(log(n)) average case @param [Algorithms::Node] node @return [Algorithms::Node]
next_highest_node
Finds and returns the next highest node in a subtree. Time complexity: O(n) worst case O(log(n)) average case @param [Algorithms::Node] node @return [Algorithms::Node]
count_nodes
Returns the number of nodes beneath a given node. Time complexity: O(n) worst case O(n) average case @param [Algorithms::Node] node @return [Integer]
exists?
Returns `true` if the value exists in the binary subtree. Time complexity: O(n) worst case O(log(n)) average case @param [Algorithms::Node] node
valid?
Returns `true` if the binary subtree is valid. Time complexity: O(n) worst case O(n) average case @param [Algorithms::Node] node @return [Boolean]
pre_order_traversal
Prints the tree node values pre-order. Time complexity: O(n) worst case O(n) average case @param [Algorithms::Node] node
in_order_traversal
Prints the tree node values in-order. Time complexity: O(n) worst case O(n) average case @param [Algorithms::Node] node
post_order_traversal
Prints the tree node values post-order. Time complexity: O(n) worst case O(n) average case @param [Algorithms::Node] node
Min Heap
insert
Inserts an element into the heap. Time complexity: O(log(n)) worst case O(log(n)) best case @param [Integer] val
delete_min
Deletes the minimum element from the heap. Time complexity: O(log(n)) worst case O(log(n)) best case @return [Integer]
min
Returns the minimum element of the heap. Time complexity: O(1) worst case O(1) best case @return [Integer]
size
Returns the size of the heap. Time complexity: O(1) worst case O(1) best case @return [Integer]
height
Returns the height of the heap. Time complexity: O(1) worst case O(1) best case @return [Integer]
empty?
Returns `true` if the heap is empty. Time complexity: O(1) worst case O(1) best case @return [Boolean]
self.decreasing_order_sort
Sorts an array using heap sort, in decreasing order. Time complexity: O(n * log(n)) worst case O(n * log(n)) average case O(n) best case @param [Array[Integer]] arr @return [Array[Integer]]