SEARCHTREE

Classes:

• vorlib::balanced_search_tree (template)
• vorlib::search_tree (template)
• vorlib::tree_e (exception)
• vorlib::knot_c (used internally)
• vorlib::balanced_knot_c (used internally)

Files:

• searchtree.h (header)
• searchtree.cpp (source)

The use of theese two template classes (balanced_search_tree, search_tree) is indexing. You can store there data named by ids (can not repeat). It looks like this:
(balanced_)search_tree< type_of_index, type_of_stored_data > name_of_variable Both, index and storad data, can be of any class type, int, bool... However, if you use pointers, they are't freed, it's your task.

The difference about them is just little. It is used exactly the same way, you may notice that balanced_search_tree inherits from search_tree, the only point is in internal data storing. That balanced balances the nodes there, and therefore is in most situationes faster than the unbalanced. The only time the it is better to use the unbalanced one is when you once put data in and one takes them out and that data don't come sorted. The balanced's time difficulty is n * log(n), the unbalanced can sometimes slow down to n * n.

Interface

• (balanced_)search_tree

  This is constructor and it is called automatically, when you do the "new" call, or create the tree statically

• ~(balanced_)search_tree

  The destructor. It is also called automatically, when you type "delete", or the lifetime of the static variable ends. It will clear all inodes and dynamically allocated memory.

• get & operator[]

  This function takes index-parameter and returns data of that index. Use: data = tree.get(index), or data = tree[index]. See the tree_e part to know, what happens, if it is not there.

• try_get

  This is just another version of that above. It returns pointer to the data, or NULL if the item is not there.

• clear

  This one just deletes all items from inside. Use: tree.clear.

• contains & operator%

  It returns true when an item with given index is inside. Use: if (tree.contaions(index)), or if (tree % index).

• operator=

  It is called automatically when you write tree2 = tree1.

• get_indexes

  This returns vector (std::vector< type_of_index >) of all indexes inside this tree, sorted.

• get_data

  This returns vector (std::vector< type_of_data >) of all data inside this tree, sorted by their index. So, if you get indexes and data by this and above function, you will have them ,index and coresponding data, at the same place in their vector.

• reindex

  This changes index of item specified by first index to the second, like tree.reindex(first_index, new_index)

• remove

  Removes item specified by index from the tree. It does nothing, if given index is not there. Looks like this: tree.remove(index)

• add

  Adds new item into tree. Looks this way: tree.add(add, data)

• empty

  returns, weather the tree is empty or not.

• check

  Check, weather the tree is internally OK. I used this for debugging, it should not be needed any more, however, I didn't delete it.

• depthtest

  This is anodther test, only for balanced one.

Error handling

The error handlig is like in whole vorlib. See exception for details. Exception class is tree_e, codes are below:

• 1: Given index is not inside the tree.