Search-tree - Open source search binary tree and bi-dimensional tree.
Search tree is an open-source binary and bi-dimensional tree gem for ruby. For more information about why and how it was done visit my article in Medium.
Table of Contents
Install and Usage
Download the gem file and use the following command to install:
gem install search_tree-[version].gem
After installing add
require 'search_tree'
in your code and you can use its methods.
Available Methods
First, you have to create a new tree using the BinaryTree class, as for example below:
t = BinaryTree.new
In the initialize method the root variable is defined as nil.
New node
new_node(node, x, *args)
This method is used to create a new node in the tree. It receives the node where the search begins, x as the search parameter and the pointer args that will receive all the other arguments added to the node.
Search
search(x, node = @root)
Returns true if, starting at the passed node, it finds a node with the search parameter x and false if it finds a nil.
Search node
search_node(x, node = @root)
Like the previus one but instead of returning true or false returns the pointer to the node with search parameter x or nil.
Edit node
edit_node(x, *args)
Locate the node with search parameter x and changer its arguments for the ones in args, if this node existis.
Delete node
delete_node(x)
Delete the node with the dearch parameter x, if exists.
Print tree
print_tree(node = @root)
Print the tree, or sub-tree starting at the passed node, in crescent search parameter order.
Number of nodes
number_nodes(node = @root)
Return the number of nodes in the tree, or sub-tree starting at the passed node.
Get depth
get_depth(node = @root, depth = 1, maxdepth = 0)
Return the depth of the tree, or sub-tree starting at the passed node. The depth and maxdepth are used as helpers inside the method.
Is balanced
is_balanced?
Return true if the number of nodes is smaller than 2 ^ (depth - 1) and bigger than 2 ^ depth and false otherwise.
Balance
balance
Balance the tree unless is_balanced? returns true.
Get nodes
get_nodes(nodes, node = @root)
Return the array nodes with all the nodes in the crescent search parameter order in the tree or sub-tree starting at the passed node. Used to balance the tree.
New balance nodes
new_balance_nodes(nodes, newroot = @root)
Used to create a new node with the array nodes received in the get_nodes method.
New node balanced
new_node_balanced(node, x, *args)
Create a new node and balance the tree.
Load file
load_file(file)
Create a tree with the data inside a file. The search parameter will always be a string.
Save file
save_file(file)
Create a file with the data in the tree.
Author and Contribution
Add me at linkedin, send me an [email][[email protected]], visit my twitter, medium and portfolio.
Feel free to contribute with pull requests but, for major changes, please open an issue first.
License
Coming soon
Future works
Already started a load file and a save file methods.
Have a big ambition to create the bi-dimensional tree. I will do it in the next days.