Just refreshing my memory
, correct me if I am wrong .
One of the properties of binary search tree is that the left node value < parent node , right node value > parent node . So if the following input sequence is given
4 9 10 15 34
the tree will become , (4)-> (9) -> ( 10) -> (15 ) -> ( 34)->nill , i have shown only the right nodes , not the left nodes as they are nill . This is similar to a linked list where when there are n elements , the search time is rougly factor of n , worst case time for the search of a binary search tree . The search function is usually written recursively as follows
Code: Select all
int search(TREE *t ,int elment)
{
// not found
if( *t == NULL )
{
return INT_MIN;
}
// found!
if( (*t) -> value == elment)
{
return 1;
}
else
{
//if less proceed recusively towards left node
if( (*t)-> value < elment)
{
return search((*t)->lchild,elment);
}
else
{
// towards the right node
return search((*t)->rchild,elment);
}
}
}
So balacing the tree is required so that the search time remains a factor of log n . If you see the function above , it develops like a geometric progression and complexity can be easily derived by using the series summation. There are two kinds of balanced trees which i am aware of they are AVL trees and Red Black trees .
The AVL tree node has an extra field in the node called the balance factor , it is recursively defined as the height of the right subtree - the height of the left subtree. In an AVL tree the balance factor of each node should be either 1 , 0 or -1 . To perform the balancing act we need to perform rotations. There are basically two kinds of rotations . i left rotation and right rotation . The easiest way to understand rotations is as follows.
left rotation - swap right child and parent node , make sure that properties of binary search tree is maintained
right rotation - swap left chid and parent node , make sure the properties of binary search tree is maintained .While insertion is performed balance factor is checked and if its 1,0,-1 then do nothing . If more than 1 ie 2 , then right subtree is more than the left subtree , then left rotation needs to be performed and balance factor needs to be calculated again and recusilvely peform the balancing and so on ... its symmetric
Red Black trees are similar to AVL trees except that they they maintain additions value called color which can be either RED or BLACK . The Red black trees show the following properties :
1) Root node is black
2) Leaves are black
3) every path from a node to leaves have equal number of black nodes
4) if a node is red , the its children are black .
These properties make sure that the tree remains balanced . I forgot the insertion and deletion algorithms . need to refer them again
.... My memory failed .
B-Trees are just fine for creating tiny datbase sort of utilites , they are an extension to the the 2-3 tree concept.They were specifically created with disk access in mind . ie A B- tree of order M has ,atmost M pointers (children) and at least M /2 pointers , m-1 data elements if non leaf node and the values are arranged in a similar way as in binary search tree . Additon , Deletion etc are similar excepet that we need to be careful in maintaining the tree structure .
This link might be useful :http://www.codeproject.com/KB/database/btreedbclass.aspx
Regards
Shrek
