Problem with a BST (binary search tree) !!!

[pirlo89]

Hi,

The Problem : I need to access elements of a BST (binary search tree) by their rank. However, the nodes of the tree do not contain the field rank. For example ...

// a structure to a BST without a rank-number
struct T1
{
	T1 * l_child;
	T1 * r_child;
	int data;
};

The Solution (or at least part of it) : i have managed to come up with this (you only need to look at the search_rank() function) ...

#include <iostream>
#include <stdlib.h>
using namespace std;

bool found = false;

// a structure to a BST without a rank-number
struct T1
{
	T1 * l_child;
	T1 * r_child;
	int data;
};

// a structure to a BST with a rank-number
struct T2
{
	T2 * l_child;
	T2 * r_child;
	int data;
	int rank;
};


// swaps two integers
void swap (int &a, int &b)
{
	int temp=a;
	a=b;
	b=temp;
}


// puts random unique numbers in arr[]
void randomize (int arr[], int size)
{
	for (int i=1; i<=size; i++)
		arr[i-1] = i;
	
	swap(arr[0], arr[size/2]);		/* so that the first element of the array is the first one (to optimize the tree) */
	
	// shuffling the elements of the array
	for (int i=1; i<(size/2); i+=2)
		swap(arr[i], arr[size-i]);
}


// searches the tree for a position to insert a node
template <class type>
type* insert_position (type * root, int element)
{
	while (root!=NULL)
	{
		if (element < root->data) 
			if (root->l_child == NULL)
				return root;
			else
				root = root->l_child;
		else
			if (root->r_child == NULL)
				return root;
			else
				root = root->r_child;
	}
	
	return root;
}


// insert an element into a BST
template <class type>
void insert (type* & root, int element)
{	
	// creating a new node
	type * new_element = new (type);
	new_element->l_child = NULL;
	new_element->r_child = NULL;
	new_element->data = element;

	// insert the node at the begining if the tree is empty
	if ( root == NULL)
		root = new_element;
	else
	{
		type * temp = insert_position(root, element);
		
		if (element < temp->data)
			temp->l_child = new_element;
		else
			temp->r_child = new_element;
	
	}
	
}


// an example of calling the function is : search_rank(root, 1, rank_of_the_element_needed)
void search_rank (T1 * ptr, int x,const int number)
{
	static int k = x;
	if (!found && ptr != NULL)
	{
		search_rank(ptr->l_child, k, number);
		if (k == number)
		{
			k += number;
			cout<<ptr->data<<' ';
			found = true;
			return;
		}
		k++;
		search_rank(ptr->r_child, k+1, number);
	}
}


// displays the contents of a T1 tree that falls in the given range
void T1_display (T1* root, int arr[], int size, int i, int j)
{	
	if (i==j)
	{
		cout<<"The "<<i<<"-th element is : ";
		found = false;
		search_rank(root, 1, i);
	}
	else if (i<j)
	{
		cout<<"The elements of the tree are (in an ascending order) : { ";
		for (int k=i; k<=j; k++)
		{
			found = false;
			search_rank(root, 1, k);
		}
		cout<<'}';
	}
	else
	{
		cout<<"The elements of the tree are (in a descending order) : { ";
		for (int k=i; k>=j; k--)
		{
			found = false;
			search_rank(root, 1, k);
		}
		cout<<'}';
	}
	
}


int main()
{
	int n;
	cout<<"Enter the total number of unique elements (n) : ";
	cin>>n;
	int * arr = new (int[n]);
	
	// initializing and shuffling the elements of the array
	randomize(arr, n);
	
	T1* tree1 = NULL;
	
	// inserting the elements into T1
	for (int i=0; i<n; i++)
	{
		insert(tree1, arr[i]);
	}
	
	int i=0, j=0, range=0;
	cout<<"Enter i : ";
	cin>>i;
	cout<<"Enter j : ";
	cin>>j;
	range = abs(i-j)+1;
	
	if (n<1)
	{
		cout<<"\n\nThere are no elements in the tree.";
		return 0;
	}
	
	if (i>n || j>n)
	{
		cout<<"\n\nThe elements requested are not in the range.";
		return 0;
	}
	else
	{
		// displaying the contents of the tree
		cout<<"\n\nT1 tree :";
		cout<<"\n-----------\n";
		T1_display(tree1, arr, range, i, j);
	}
	
	return 0;
}

Which gets me only the first element in the wanted range. But it doesn't give me the rest of the elements. What am i doing wrong ?!
(i have a sense that its the "static int k").

Note : the search_rank() function is similar to in-order-traversal (Left-Visit-right) method.

[ne555]

what is the rank?

(you only need to look at the search_rank() function)

Then you only need to post that

[pirlo89]

the rank is the order of the element as if the elements were sorted in an ascending order.

(you only need to look at the search_rank() function)
Then you only need to post that

sorry about that, but the function uses a global variable "found".

[ne555]

Then you need a counter passed by reference that will tell you the rank of the cell.

T1 * search_rank (T1 * cell, int rank, int &counter){
  if( cell == NULL ) return NULL;
  //in-order traversal
  //when visit a valid cell, counter++
  //if counter reach rank, founded
}

[pirlo89]

here is my trial. doesn't really work though.

// put a rank number for the nodes of a T2 tree
T1* search_rank (T1 * ptr, int k, int & counter)
{
	if (!ptr)
		return NULL;
	else
	{
		search_rank(ptr->l_child, k, counter);
		counter++;
		if (counter == k)
			return ptr;
		search_rank(ptr->r_child, k, counter);
	}
}

[ne555]

You need to use the results of the recursive calls

		left = search_rank(ptr->l_child, k, counter);
		if( left ) return left; //already founded 
		counter++;
		if (counter == k)
			return ptr;
		right = search_rank(ptr->r_child, k, counter);
		if( right ) return right;

You could avoid one parameter if you decrement the counter, when it reaches 0 you are in your destination

[pirlo89]

im sorry, but i dont get it. and it doesn't work.

i dont know why i cant solve this problem. it looks so easy. i feel like im about to explode !!!

anyway, here is my last attempt ...

// search for the element with the specific rank
void search_rank (T1 * ptr, int i, int &counter)
{
	if (ptr==NULL || counter>i)
		return;
	else
	{
		search_rank(ptr->l_child, i, counter);
		counter++;
		if (counter == i)
		{
			counter += i;
			cout<<(ptr->data)<<' ';
			return;
		}
		search_rank(ptr->r_child, i, counter+=1);
	}
}

[ne555]

void search_rank (T1 * ptr, int i, int &counter)
{
	if (ptr==NULL || counter>i) //leaf or the element was already found
		return;
	else
	{
		search_rank(ptr->l_child, i, counter);
		counter++; //visit
		if (counter == i)
		{
			counter += i; //unnecessary
			cout<<(ptr->data)<<' ';
			return;
		}
//		search_rank(ptr->r_child, i, counter+=1);//why incrementing again?
		search_rank(ptr->r_child, i, counter);
	}
}

[pirlo89]

thank you very much :)

i cant believe i didn't see why that i shouldn't increment
search_rank(ptr->r_child, i, counter+=1)

i was so stuck on a function that i wrote earlier that does almost the same thing, but the counter in it wasn't passed by reference !!!

Again thank you very much for all your help.