diff options
Diffstat (limited to 'devel/ruby-rbtree/DESCR')
-rw-r--r-- | devel/ruby-rbtree/DESCR | 14 |
1 files changed, 14 insertions, 0 deletions
diff --git a/devel/ruby-rbtree/DESCR b/devel/ruby-rbtree/DESCR new file mode 100644 index 00000000000..a9ce6762e0a --- /dev/null +++ b/devel/ruby-rbtree/DESCR @@ -0,0 +1,14 @@ +RBTree is a sorted associative collection using Red-Black Tree as +the internal data structure. The elements of RBTree are ordered +and the interface is the almost same as Hash, so simply you can +consider RBTree sorted Hash. + +Red-Black Tree is a kind of binary tree that automatically balances +by itself when a node is inserted or deleted. Thus the complexity +for insert, search and delete is O(log N) in expected and worst +case. On the other hand the complexity of Hash is O(1). Because +Hash is unordered the data structure is more effective than Red-Black +Tree as an associative collection. + +The interface of RBTree is the almost same as Hash although there +are some limitations. |