-
Notifications
You must be signed in to change notification settings - Fork 2
A source code mirror of [rbtree gem](https://rubygems.org/gems/rbtree). This repository is for making it easy for me (@mame) to maintain the rbtree gem. We will not accept any feature proposal. The primary repository of rbtree gem is private, and managed by OZAWA Takuma, the original author of the gem.
License
mame/rbtree
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
= Ruby/RBTree == Description A RBTree is a sorted associative collection that is implemented with a Red-Black Tree. It maps keys to values like a Hash, but maintains its elements in ascending key order. The interface is the almost identical to that of Hash. A Red-Black Tree is a kind of binary tree that automatically balances by itself when a node is inserted or deleted. Lookup, insertion, and deletion are performed in O(log N) time in the expected and worst cases. On the other hand, the average case complexity of lookup/insertion/deletion on a Hash is constant time. A Hash is usually faster than a RBTree where ordering is unimportant. The elements of a RBTree are sorted using the <=> method of their keys or a Proc set by the readjust method. It means all keys should be comparable with each other or a Proc that takes two keys should return a negative integer, 0, or a positive integer as the first argument is less than, equal to, or greater than the second one. RBTree also provides a few additional methods to take advantage of the ordering: * lower_bound, upper_bound, bound * first, last * shift, pop * reverse_each == Example A RBTree cannot contain duplicate keys. Use MultiRBTree that is the parent class of RBTree to store duplicate keys. require "rbtree" rbtree = RBTree["c", 10, "a", 20] rbtree["b"] = 30 p rbtree["b"] # => 30 rbtree.each do |k, v| p [k, v] end # => ["a", 20] ["b", 30] ["c", 10] mrbtree = MultiRBTree["c", 10, "a", 20, "e", 30, "a", 40] p mrbtree.lower_bound("b") # => ["c", 10] mrbtree.bound("a", "d") do |k, v| p [k, v] end # => ["a", 20] ["a", 40] ["c", 10] Note: a RBTree cannot be modified during iteration. == Installation Run the following command. $ sudo gem install rbtree == Changes === 0.4.5 * Support Ruby 3.2.0-dev (development branch). === 0.4.4 * Remove the rb_safe_level warning on Ruby 2.7. === 0.4.3 * Quick bug fixes for Ruby 3. == License MIT License. Copyright (c) 2002-2013 OZAWA Takuma. dict.c and dict.h are modified copies that are originally in Kazlib 1.20 written by Kaz Kylheku. Its license is similar to the MIT license. See dict.c and dict.h for the details. The web page of Kazlib is at http://www.kylheku.com/~kaz/kazlib.html.
About
A source code mirror of [rbtree gem](https://rubygems.org/gems/rbtree). This repository is for making it easy for me (@mame) to maintain the rbtree gem. We will not accept any feature proposal. The primary repository of rbtree gem is private, and managed by OZAWA Takuma, the original author of the gem.