Red-Black Trees¶
Red-Black trees are balanced search binary trees.
They are named because nodes can be classified as either red or black. The code we include is based on "Introduction to Algorithms", second edition, by Cormen, Leiserson, Rivest and Stein. The library includes routines to insert, lookup and delete elements in the tree.
A Red black tree is represented as a term t(Nil, Tree), where Nil is the Nil-node, a node shared for each nil-node in the tree. Any node has the form colour(Left, Key, Value, Right), where colour is one of =red= or =black=.
author:
Vitor Santos Costa, Jan Wielemaker
- rb_lookupall/4
- rb_rewrite/8
- rb_rewrite/5
- rb_update/6
- rb_previous/8
- rb_lookup/4
- prolog::is_rbtree/1
- prolog::rb_size/2
- prolog::ord_list_to_rbtree/2
- prolog::list_to_rbtree/2
- prolog::ord_keys_to_rbtree/2
- prolog::keys_to_rbtree/2
- prolog::rb_keys/3
- prolog::rb_keys/2
- prolog::rb_partial_map/4
- prolog::rb_clone/4
- prolog::rb_key_fold/4
- prolog::rb_fold/4
- prolog::rb_map/2
- prolog::rb_map/3
- prolog::rb_visit/3
- prolog::rb_visit/2
- prolog::rb_del_max/4
- prolog::rb_del_min/4
- prolog::rb_delete/4
- prolog::rb_delete/3
- prolog::rb_insert_new/4
- prolog::rb_insert/4
- prolog::rb_lookupall/3
- prolog::rb_in/3
- prolog::rb_apply/4
- prolog::rb_rewrite/3
- prolog::rb_rewrite/4
- prolog::rb_update/4
- prolog::rb_update/5
- prolog::rb_previous/4
- prolog::rb_next/4
- prolog::rb_max/3
- prolog::rb_min/3
- prolog::rb_lookup/3
- prolog::rb_empty/1
- prolog::rb_new/1
Functions:¶
1. *** prolog::rb_previous(+T,+Key, -Previous, -Value) is semidet.%% Previous is the previous element after Key in T*: