LinuxQuestions.org
Share your knowledge at the LQ Wiki.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 04-25-2006, 09:24 AM   #1
adnanm
Member
 
Registered: Dec 2004
Location: Bosnia and Herzegowina
Distribution: Centos, FreeBSD
Posts: 49

Rep: Reputation: 15
How to implement balancing mechanism for binary tree in C++ ?


Which mechanism has the fastest execution time, red-black, AVL or splay tree ?
 
Old 04-25-2006, 10:42 AM   #2
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 10,610
Blog Entries: 4

Rep: Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905
I hope this isn't a homework assignment ...

The speed and efficiency of any such algorithm depends entirely upon the workload to which it is subjected ... inserts vs. deletes and so-on. All of them are very likely to be quite satisfactory in practice.

Remember that the biggest time constraint on any computer program's execution is not the speed of the CPU, but the speed of (and necessity for) input/output. Both CPU-time and memory are typically plentiful these days.
 
Old 04-25-2006, 11:37 AM   #3
aluser
Member
 
Registered: Mar 2004
Location: Massachusetts
Distribution: Debian
Posts: 557

Rep: Reputation: 43
Of the professors at my college who seem to know what they're talking about, the consensus on speed comparisons seems to be that A. you have to benchmark it and B. for cpu-bound programs, the number of cache misses is more important than almost anything else. So, the particular implementation of your algorithm is likely to make more difference than the algorithm choice itself, at least for either small input sizes or similar complexity algorithms.

In other words, the chance of getting a usable answer to your question is near zero :P
 
Old 04-25-2006, 12:19 PM   #4
adnanm
Member
 
Registered: Dec 2004
Location: Bosnia and Herzegowina
Distribution: Centos, FreeBSD
Posts: 49

Original Poster
Rep: Reputation: 15
Thank you all for posting, I have unbalanced working binary three working and everything now all I need is balancing mechanism for it either AVL or Red-Black, but I cannot figure out how to implement it, so if I paste my code here will any1 be able to help me with balancing my tree, I can do some favor for helping folks, thanks once again for posting !
 
Old 04-25-2006, 01:09 PM   #5
adnanm
Member
 
Registered: Dec 2004
Location: Bosnia and Herzegowina
Distribution: Centos, FreeBSD
Posts: 49

Original Poster
Rep: Reputation: 15
My tree should do like this table below. When you see new element in tree it prints out -1 and puts it on the begining, else count distinct steps when you seen your element last time and write its position. You can get more out of it by looking at the table:

i 0 1 2 3 4 5 6 7 8 9 -> index
ai A B B C A A C B D A -> input
LRU -1 -1 0 -1 2 0 1 2 -1 3 -> output needed

For now my tree does everything as needed perfectly, just as the table tells me, but my tree is not balanced which causes to be extremely slow and I need it to perform faster and to be balanced, I would like to achieve O(1) or O(logn) time, here is my code, hpp class :
--------------------------------------------------------------------------------------
/* $Id: nutri.hpp,v 1.3 2006/04/15 09:33:03 adnanm Exp adnanm $ */

#ifndef __HEADER_FILE_INCLUDED__nutri_hpp__
#define __HEADER_FILE_INCLUDED__nutri_hpp__

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>

#include "interface_LRU.hpp"

class nutri
{
public:
struct tree_node
{
tree_node * mom_ptr;
tree_node * left_child;
tree_node * right_child;
unsigned int nodes_in_left_subtree;
};
tree_node * root;
typedef tree_node * key;

void clear()
{
kill();
reset();
};
void insert_leftmost(tree_node * & moving_node,
tree_node * & local_root)
{
if (local_root == NULL)
{
local_root = moving_node;
local_root->left_child = NULL;
local_root->right_child = NULL;
local_root->nodes_in_left_subtree = 0;
}
else
{
insert_leftmost(moving_node,
local_root->left_child);
local_root->left_child->mom_ptr = local_root;
local_root->nodes_in_left_subtree++;
};
};
key new_item()
{
tree_node * result = new tree_node;
insert_leftmost(result, root);
root->mom_ptr = NULL;
return result;
};

unsigned int position(key & item)
{
unsigned int result = 0;
result = item->nodes_in_left_subtree;
for (tree_node * current = item->mom_ptr;
current != NULL;
current = current->mom_ptr)
{
if (current->right_child == item)
{
result += current->nodes_in_left_subtree + 1;
};
item = current;
};
return result;
};
tree_node * & moms_ptr_to_me(tree_node * me)
{
if (me->mom_ptr == NULL)
{
return root;
}
else if (me->mom_ptr->left_child == me)
{
return me->mom_ptr->left_child;
}
else
{
return me->mom_ptr->right_child;
};
};

tree_node * & rightmost(tree_node * & subtree)
{
if (subtree->right_child == NULL)
{
return subtree;
}
else
{
return rightmost(subtree->right_child);
};
};
void nodeswap(tree_node * & A, tree_node * & B)
{
std::swap(moms_ptr_to_me(A->mom_ptr),
moms_ptr_to_me(B->mom_ptr));
std::swap(A->mom_ptr, B->mom_ptr);
std::swap(A->left_child, B->left_child);
std::swap(A->right_child, B->right_child);
std::swap(A->nodes_in_left_subtree,
B->nodes_in_left_subtree);
};
void update_count(tree_node * item)
{
for (tree_node * current = item->mom_ptr;
current != NULL;
current = current->mom_ptr)
{
if (current->left_child == item)
{
current->nodes_in_left_subtree--;
};
item = current;
};
};

void remove_from_tree(tree_node * item)
{
if (item->left_child == NULL)
{
update_count(item);
moms_ptr_to_me(item) = item->right_child;
}
else if (item->right_child == NULL)
{
update_count(item);
moms_ptr_to_me(item) = item->left_child;
}
else
{
nodeswap(item, rightmost(item->left_child));
remove_from_tree(item);
};

};
void move_to_front(key & item)
{
remove_from_tree(item);
insert_leftmost(item, root);
root->mom_ptr = NULL;
};
private:
void reset()
{
root = NULL;
};
void copy(const nutri & other)
{
throw std::string("Bad idea dude!");
};
void kill_tree_node(tree_node * & condemned_root)
{
if (condemned_root != NULL)
{
kill_tree_node(condemned_root->left_child);
kill_tree_node(condemned_root->right_child);
delete condemned_root;
};
};
void kill()
{
kill_tree_node(root);
};
public:
nutri()
{
reset();
};
nutri(const nutri & other)
{
reset();
copy(other);
};
nutri & operator=(const nutri & other)
{
if (this != &other)
{
kill();
reset();
copy(other);
};
return *this;
};
~nutri()
{
kill();
};
private:
void dump_tree_node(std:stream & fout, const tree_node * root, int depth) const
{
if (root != NULL)
{
dump_tree_node(fout, root->left_child, depth + 1);
indent(fout, depth);
fout << "@" << root->nodes_in_left_subtree << std::endl;
dump_tree_node(fout, root->right_child, depth + 1);
};
};
public:
void dump(std:stream & fout) const
{
dump_tree_node(fout, root, 0);
};

static void indent(std:stream & fout, int n)
{
for (int i = 0; i < n; i++)
{
fout << " ";
};
};
};

inline
std:stream & operator<<(std:stream & fout, const nutri & X)
{
X.dump(fout);
return fout;
};
#endif // __HEADER_FILE_INCLUDED__nutri_hpp__

--------------------------------------------------------------------------

/* Interface: interface_LRU.hpp */

#ifndef __HEADER_FILE_INCLUDED__interface_LRU_hpp
#define __HEADER_FILE_INCLUDED__interface_LRU_hpp

class interface_LRU
{
public:
virtual const char * identifier() const = 0;
virtual void clear () = 0;
virtual int touch(long long int item) = 0;
virtual ~interface_LRU() {};
};

#endif //__HEADER_FILE_INCLUDED__interface_LRU_hpp
-----------------------------------------------
/* Test program:nutri_tester.cpp */

#include "nutri.hpp"

#include <iostream>
#include <map>

using namespace std;

#define SInt64 long long int

int main ()
{
/*
* Ovo pod komentarima ispisuje elemente u arrayu,
* ne sortiranim redosljedom
*/
nutri shisko;
map<SInt64, nutri::key> finder;

cout << "Which number you want to find" << endl;
SInt64 num;

while (cin >> num)
{
if (finder.find(num) == finder.end())
{
finder[num] = shisko.new_item();
cout << -1 << endl;
cout << shisko << endl;
}
else
{
cout << shisko.position(finder[num]) << endl;
shisko.move_to_front(finder[num]);
cout << shisko << endl;
};
};
return 0;
}
---------------------------------------------
 
Old 04-25-2006, 01:12 PM   #6
adnanm
Member
 
Registered: Dec 2004
Location: Bosnia and Herzegowina
Distribution: Centos, FreeBSD
Posts: 49

Original Poster
Rep: Reputation: 15
My tree should do like this table below. When you see new element in tree it prints out -1 and puts it on the begining, else count distinct steps when you seen your element last time and write its position. You can get more out of it by looking at the table:

i 0 1 2 3 4 5 6 7 8 9 -> index
ai A B B C A A C B D A -> input
LRU -1 -1 0 -1 2 0 1 2 -1 3 -> output needed

For now my tree does everything as needed perfectly, just as the table tells me, but my tree is not balanced which causes to be extremely slow and I need it to perform faster and to be balanced, I would like to achieve O(1) or O(logn) time, here is my code, hpp class :
Quote:
Originally Posted by adnanm
--------------------------------------------------------------------------------------
/* $Id: nutri.hpp,v 1.3 2006/04/15 09:33:03 adnanm Exp adnanm $ */

#ifndef __HEADER_FILE_INCLUDED__nutri_hpp__
#define __HEADER_FILE_INCLUDED__nutri_hpp__

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>

#include "interface_LRU.hpp"

class nutri
{
public:
struct tree_node
{
tree_node * mom_ptr;
tree_node * left_child;
tree_node * right_child;
unsigned int nodes_in_left_subtree;
};
tree_node * root;
typedef tree_node * key;

void clear()
{
kill();
reset();
};
void insert_leftmost(tree_node * & moving_node,
tree_node * & local_root)
{
if (local_root == NULL)
{
local_root = moving_node;
local_root->left_child = NULL;
local_root->right_child = NULL;
local_root->nodes_in_left_subtree = 0;
}
else
{
insert_leftmost(moving_node,
local_root->left_child);
local_root->left_child->mom_ptr = local_root;
local_root->nodes_in_left_subtree++;
};
};
key new_item()
{
tree_node * result = new tree_node;
insert_leftmost(result, root);
root->mom_ptr = NULL;
return result;
};

unsigned int position(key & item)
{
unsigned int result = 0;
result = item->nodes_in_left_subtree;
for (tree_node * current = item->mom_ptr;
current != NULL;
current = current->mom_ptr)
{
if (current->right_child == item)
{
result += current->nodes_in_left_subtree + 1;
};
item = current;
};
return result;
};
tree_node * & moms_ptr_to_me(tree_node * me)
{
if (me->mom_ptr == NULL)
{
return root;
}
else if (me->mom_ptr->left_child == me)
{
return me->mom_ptr->left_child;
}
else
{
return me->mom_ptr->right_child;
};
};

tree_node * & rightmost(tree_node * & subtree)
{
if (subtree->right_child == NULL)
{
return subtree;
}
else
{
return rightmost(subtree->right_child);
};
};
void nodeswap(tree_node * & A, tree_node * & B)
{
std::swap(moms_ptr_to_me(A->mom_ptr),
moms_ptr_to_me(B->mom_ptr));
std::swap(A->mom_ptr, B->mom_ptr);
std::swap(A->left_child, B->left_child);
std::swap(A->right_child, B->right_child);
std::swap(A->nodes_in_left_subtree,
B->nodes_in_left_subtree);
};
void update_count(tree_node * item)
{
for (tree_node * current = item->mom_ptr;
current != NULL;
current = current->mom_ptr)
{
if (current->left_child == item)
{
current->nodes_in_left_subtree--;
};
item = current;
};
};

void remove_from_tree(tree_node * item)
{
if (item->left_child == NULL)
{
update_count(item);
moms_ptr_to_me(item) = item->right_child;
}
else if (item->right_child == NULL)
{
update_count(item);
moms_ptr_to_me(item) = item->left_child;
}
else
{
nodeswap(item, rightmost(item->left_child));
remove_from_tree(item);
};

};
void move_to_front(key & item)
{
remove_from_tree(item);
insert_leftmost(item, root);
root->mom_ptr = NULL;
};
private:
void reset()
{
root = NULL;
};
void copy(const nutri & other)
{
throw std::string("Bad idea dude!");
};
void kill_tree_node(tree_node * & condemned_root)
{
if (condemned_root != NULL)
{
kill_tree_node(condemned_root->left_child);
kill_tree_node(condemned_root->right_child);
delete condemned_root;
};
};
void kill()
{
kill_tree_node(root);
};
public:
nutri()
{
reset();
};
nutri(const nutri & other)
{
reset();
copy(other);
};
nutri & operator=(const nutri & other)
{
if (this != &other)
{
kill();
reset();
copy(other);
};
return *this;
};
~nutri()
{
kill();
};
private:
void dump_tree_node(std::ostream & fout, const tree_node * root, int depth) const
{
if (root != NULL)
{
dump_tree_node(fout, root->left_child, depth + 1);
indent(fout, depth);
fout << "@" << root->nodes_in_left_subtree << std::endl;
dump_tree_node(fout, root->right_child, depth + 1);
};
};
public:
void dump(std::ostream & fout) const
{
dump_tree_node(fout, root, 0);
};

static void indent(std::ostream & fout, int n)
{
for (int i = 0; i < n; i++)
{
fout << " ";
};
};
};

inline
std::ostream & operator<<(std::ostream & fout, const nutri & X)
{
X.dump(fout);
return fout;
};
#endif // __HEADER_FILE_INCLUDED__nutri_hpp__

--------------------------------------------------------------------------

/* Interface: interface_LRU.hpp */

#ifndef __HEADER_FILE_INCLUDED__interface_LRU_hpp
#define __HEADER_FILE_INCLUDED__interface_LRU_hpp

class interface_LRU
{
public:
virtual const char * identifier() const = 0;
virtual void clear () = 0;
virtual int touch(long long int item) = 0;
virtual ~interface_LRU() {};
};

#endif //__HEADER_FILE_INCLUDED__interface_LRU_hpp
-----------------------------------------------
/* Test program:nutri_tester.cpp */

#include "nutri.hpp"

#include <iostream>
#include <map>

using namespace std;

#define SInt64 long long int

int main ()
{
/*
* Ovo pod komentarima ispisuje elemente u arrayu,
* ne sortiranim redosljedom
*/
nutri shisko;
map<SInt64, nutri::key> finder;

cout << "Which number you want to find" << endl;
SInt64 num;

while (cin >> num)
{
if (finder.find(num) == finder.end())
{
finder[num] = shisko.new_item();
cout << -1 << endl;
cout << shisko << endl;
}
else
{
cout << shisko.position(finder[num]) << endl;
shisko.move_to_front(finder[num]);
cout << shisko << endl;
};
};
return 0;
}
---------------------------------------------
 
Old 04-25-2006, 07:09 PM   #7
Flesym
Member
 
Registered: Aug 2005
Location: Germany
Distribution: Ubuntu, Debian
Posts: 189

Rep: Reputation: 31
Quote:
Originally Posted by adnanm
...
For now my tree does everything as needed perfectly, just as the table tells me, but my tree is not balanced which causes to be extremely slow and I need it to perform faster and to be balanced, I would like to achieve O(1) or O(logn) time
...
I haven't read all of your code; please use code tags!! -It makes things really easier. However, you won't be able to achieve basic balanced-tree operations (search, insert, delete) in constant time. Searching a balanced (best case) tree will always take you O(log n); either will the (self-)balancing itself take O(log n) time, no matter if AVL. Red-Black, Splay (well, actually splaying is a bit different, but in avarage you gain the same performance) or any other. But in my opinion the AVL algorithm is the most intuitive, although it's not always the best and easiest to implement, but I think it is a good starting point into this whole balancing thing. I don't know how this fits your LRU problem, but a very good C++ tutorial of an AVL implementation is here:
http://www.cmcrossroads.com/bradapp/.../AvlTrees.html

Last edited by Flesym; 04-25-2006 at 07:16 PM.
 
Old 04-26-2006, 09:36 AM   #8
adnanm
Member
 
Registered: Dec 2004
Location: Bosnia and Herzegowina
Distribution: Centos, FreeBSD
Posts: 49

Original Poster
Rep: Reputation: 15
Ok I am reposting again so people can read :
My tree should do like this table below. When you see new element in tree it prints out -1 and puts it on the begining, else count distinct steps when you seen your element last time and write its position. You can get more out of it by looking at the table:

i 0 1 2 3 4 5 6 7 8 9 -> index
ai A B B C A A C B D A -> input
LRU -1 -1 0 -1 2 0 1 2 -1 3 -> output needed

For now my tree does everything as needed perfectly, just as the table tells me, but my tree is not balanced which causes to be extremely slow and I need it to perform faster and to be balanced, I need a code which will balance my tree I would like to achieve O(logn) time, here is my code, hpp class :


Code:
/* $Id: nutri.hpp,v 1.3 2006/04/15 09:33:03 adnanm Exp adnanm $ */

#ifndef __HEADER_FILE_INCLUDED__nutri_hpp__
#define __HEADER_FILE_INCLUDED__nutri_hpp__

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>

#include "interface_LRU.hpp"

class nutri
{
public:
struct tree_node
{
tree_node * mom_ptr;
tree_node * left_child;
tree_node * right_child;
unsigned int nodes_in_left_subtree;
};
tree_node * root;
typedef tree_node * key;

void clear()
{
kill();
reset();
};
void insert_leftmost(tree_node * & moving_node,
tree_node * & local_root)
{
if (local_root == NULL)
{
local_root = moving_node;
local_root->left_child = NULL;
local_root->right_child = NULL;
local_root->nodes_in_left_subtree = 0;
}
else
{
insert_leftmost(moving_node,
local_root->left_child);
local_root->left_child->mom_ptr = local_root;
local_root->nodes_in_left_subtree++;
};
};
key new_item()
{
tree_node * result = new tree_node;
insert_leftmost(result, root);
root->mom_ptr = NULL;
return result;
};

unsigned int position(key & item)
{
unsigned int result = 0;
result = item->nodes_in_left_subtree;
for (tree_node * current = item->mom_ptr;
current != NULL;
current = current->mom_ptr)
{
if (current->right_child == item)
{
result += current->nodes_in_left_subtree + 1;
};
item = current;
};
return result;
};
tree_node * & moms_ptr_to_me(tree_node * me)
{
if (me->mom_ptr == NULL)
{
return root;
}
else if (me->mom_ptr->left_child == me)
{
return me->mom_ptr->left_child;
}
else
{
return me->mom_ptr->right_child;
};
};

tree_node * & rightmost(tree_node * & subtree)
{
if (subtree->right_child == NULL)
{
return subtree;
}
else
{
return rightmost(subtree->right_child);
};
};
void nodeswap(tree_node * & A, tree_node * & B)
{
std::swap(moms_ptr_to_me(A->mom_ptr),
moms_ptr_to_me(B->mom_ptr));
std::swap(A->mom_ptr, B->mom_ptr);
std::swap(A->left_child, B->left_child);
std::swap(A->right_child, B->right_child);
std::swap(A->nodes_in_left_subtree,
B->nodes_in_left_subtree);
};
void update_count(tree_node * item)
{
for (tree_node * current = item->mom_ptr;
current != NULL;
current = current->mom_ptr)
{
if (current->left_child == item)
{
current->nodes_in_left_subtree--;
};
item = current;
};
};

void remove_from_tree(tree_node * item)
{
if (item->left_child == NULL)
{
update_count(item);
moms_ptr_to_me(item) = item->right_child;
}
else if (item->right_child == NULL)
{
update_count(item);
moms_ptr_to_me(item) = item->left_child;
}
else
{
nodeswap(item, rightmost(item->left_child));
remove_from_tree(item);
};

};
void move_to_front(key & item)
{
remove_from_tree(item);
insert_leftmost(item, root);
root->mom_ptr = NULL;
};
private:
void reset()
{
root = NULL;
};
void copy(const nutri & other)
{
throw std::string("Bad idea dude!");
};
void kill_tree_node(tree_node * & condemned_root)
{
if (condemned_root != NULL)
{
kill_tree_node(condemned_root->left_child);
kill_tree_node(condemned_root->right_child);
delete condemned_root;
};
};
void kill()
{
kill_tree_node(root);
};
public:
nutri()
{
reset();
};
nutri(const nutri & other)
{
reset();
copy(other);
};
nutri & operator=(const nutri & other)
{
if (this != &other)
{
kill();
reset();
copy(other);
};
return *this;
};
~nutri()
{
kill();
};
private:
void dump_tree_node(std::ostream & fout, const tree_node * root, int depth) const
{
if (root != NULL)
{
dump_tree_node(fout, root->left_child, depth + 1);
indent(fout, depth);
fout << "@" << root->nodes_in_left_subtree << std::endl;
dump_tree_node(fout, root->right_child, depth + 1);
};
};
public:
void dump(std::ostream & fout) const
{
dump_tree_node(fout, root, 0);
};

static void indent(std::ostream & fout, int n)
{
for (int i = 0; i < n; i++)
{
fout << " ";
};
};
};

inline
std::ostream & operator<<(std::ostream & fout, const nutri & X)
{
X.dump(fout);
return fout;
};
#endif // __HEADER_FILE_INCLUDED__nutri_hpp__

--------------------------------------------------------------------------

/* Interface: interface_LRU.hpp */

#ifndef __HEADER_FILE_INCLUDED__interface_LRU_hpp
#define __HEADER_FILE_INCLUDED__interface_LRU_hpp

class interface_LRU
{
public:
virtual const char * identifier() const = 0;
virtual void clear () = 0;
virtual int touch(long long int item) = 0;
virtual ~interface_LRU() {};
};

#endif //__HEADER_FILE_INCLUDED__interface_LRU_hpp
-----------------------------------------------
/* Test program:nutri_tester.cpp */

#include "nutri.hpp"

#include <iostream>
#include <map>

using namespace std;

#define SInt64 long long int

int main ()
{
/*
* Ovo pod komentarima ispisuje elemente u arrayu,
* ne sortiranim redosljedom
*/
nutri shisko;
map<SInt64, nutri::key> finder;

cout << "Which number you want to find" << endl;
SInt64 num;

while (cin >> num)
{
if (finder.find(num) == finder.end())
{
finder[num] = shisko.new_item();
cout << -1 << endl;
cout << shisko << endl;
}
else
{
cout << shisko.position(finder[num]) << endl;
shisko.move_to_front(finder[num]);
cout << shisko << endl;
};
};
return 0;
}
 
Old 04-26-2006, 01:51 PM   #9
graemef
Senior Member
 
Registered: Nov 2005
Location: Hanoi
Distribution: Fedora 13, Ubuntu 10.04
Posts: 2,379

Rep: Reputation: 148Reputation: 148
The process of balancing a binary tree will typically occur when the nodes change. That is when a node is inserted, or when a node is deleted. The AVL tree determines if a tree is out of balance by calculating a balance factor. Each node has an extra piece of information, the balance factor. For a tree to be balanced valid values are -1, 0 or +1, should the balance factor reach +2 or -2 then the tree is out of balance and a rotation is required, to bring the tree back into balance.

I suggest that you first try and implement the balance factor. The balance factor is calculated as the height of the subtree rooted at its left child, minus the height of the subtree rooted at its right child.

Thus a leaf will have a value of 0
A node with a single leaf on its left will have a value of: 1 - 0 = +1
A node with a single leaf on its right will have a value of: 0 - 1 = -1
A node with a left subtree with a height of 3 and a right subtree with a height of 1 will have a value of 3 - 1 = +2 and is thus out of balance.

So to calculate the balance factor it is important to be able to keep track of the height of a subtree.

If you can implement that correctly then I woudl suggest that you are ready to move on to the rotation.

As a test, what would be the balance factors for the following tree?

Code:
        50
      /    \
    17       76
  /    \    /
 9      23 54
  \    /     \
  14  19     72
 /          /
12         67
graeme
 
Old 04-26-2006, 02:08 PM   #10
adnanm
Member
 
Registered: Dec 2004
Location: Bosnia and Herzegowina
Distribution: Centos, FreeBSD
Posts: 49

Original Poster
Rep: Reputation: 15
Thank you for your comment, but I think that theoretical implementation is not problem, I think my problem is code implementation, ok balanced tree should look like this I think :
Code:
           50
         /    \
       17       67
     /    \    /  \
    12    23  54  76
   /  \   /       /
  9   14 19      72
Please correct me if I am wrong !
 
Old 04-26-2006, 02:16 PM   #11
graemef
Senior Member
 
Registered: Nov 2005
Location: Hanoi
Distribution: Fedora 13, Ubuntu 10.04
Posts: 2,379

Rep: Reputation: 148Reputation: 148
What I am suggesting is if you understand how the balance factor works then you can start to implement the balance factor. That is the first step in process. So I wasn't actually asking what the balanced tree will look like, rather what is the balance factor of each node in the unbalanced tree.
 
Old 04-27-2006, 01:33 PM   #12
adnanm
Member
 
Registered: Dec 2004
Location: Bosnia and Herzegowina
Distribution: Centos, FreeBSD
Posts: 49

Original Poster
Rep: Reputation: 15
Ok people I now have a position tree which puts all elements on the left side whether I insert search or whatever, my idea is to balance it by rotating right whenever I see a NULL root and NULL left child, so it did it but I still have problems with my LRU, it doesn't count as it should but it does good rotate, I will paste my rotate code I feel I need 1 line to make this LRU working so if anyone can help I would appriciate Here is my rotate routine :

Code:
void rotate_right(tree_node * & local_root)
   {
      tree_node * next_root = local_root->left_child;
      local_root->left_child = next_root->right_child;
      next_root->right_child = local_root;
      next_root->mom_ptr = local_root->mom_ptr;
      local_root->mom_ptr = next_root;
      local_root = next_root;

   };
 
Old 04-27-2006, 03:27 PM   #13
graemef
Senior Member
 
Registered: Nov 2005
Location: Hanoi
Distribution: Fedora 13, Ubuntu 10.04
Posts: 2,379

Rep: Reputation: 148Reputation: 148
The rotate is a little more complex than your code would suggest:

Take the following sub tree
Code:
    22
   /
 15
 /
9
In this scenario the new node was 9 and it has unbalanced the tree. The node 15 needs to become the parent node and the others rotate around. Giving:
Code:
  15
 /  \
9   22
However now take the following tree (this time the new node is 17)
Code:
    22
   /
 15
   \
   17
In this case the result from the rotation is:
Code:
  17
 /  \
15  22
The first case is known as a left-left rotation or LL rotation. This is done by finding the root of the subtree that is now unbalanced. From this root take the left node call this left, assign the right node of left to the left node of root Assign root to the right node or left, left is now the new root.

The second case is known as a left-right rotation, or LR rotation.
let left be the left child of root
let grandchild be the right node of left
Set the right child of left to the left child of grandchild
set the left child of grandchild to left
set the left child of root to the right child of grandchild
set the right child of grandchild to root
now grandchild is the new root of the subtree

To understand it I would suggest that you run through a few examples.

In need of a LL rotation
Code:
          50
         /   \
       22     75
      /  \
     15   43
    /
   9
In need of a LR rotation
Code:
          50
         /   \
       22     75
      /  \
     15   43
          /
        28
There are also RL and RR rotations although these tend to mirror the above algorithms.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Binary tree in C spank Programming 20 04-25-2006 10:45 AM
representation of binary tree using array sajith Programming 3 10-06-2005 10:59 PM
the bible = the tree of the knowledge of good and evil () Jesus = the tree of life Michael111 General 2 04-14-2004 04:28 PM
Binary search tree insertion in java ksgill Programming 6 02-12-2004 05:11 PM
Printing a binary tree in c? JMC Programming 5 09-26-2003 11:02 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 01:44 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration