hi , i found an balanced tree on the internet

i want to put a string in it value , not a number . how could i change
it?

sorry it is too long , i realy need a help . . .


using System;

public class AATree<TKey, TValue> where TKey : IComparable<TKey>
{
private class Node
{
// node internal data
internal int level;
internal Node left;
internal Node right;

// user data
internal TKey key;
internal TValue value;

// constuctor for the sentinel node
internal Node()
{
this.level = 0;
this.left = this;
this.right = this;
}

// constuctor for regular nodes (that all start life
as leaf nodes)
internal Node(TKey key, TValue value, Node sentinel)
{
this.level = 1;
this.left = sentinel;
this.right = sentinel;
this.key = key;
this.value = value;
}
}

Node root;
Node sentinel;
Node deleted;

public AATree()
{
root = sentinel = new Node();
deleted = null;
}

private void Skew(ref Node node)
{
if (node.level == node.left.level)
{
// rotate right
Node left = node.left;
node.left = left.right;
left.right = node;
node = left;
}
}

private void Split(ref Node node)
{
if (node.right.right.level == node.level)
{
// rotate left
Node right = node.right;
node.right = right.left;
right.left = node;
node = right;
node.level++;
}
}

private bool Insert(ref Node node, TKey key, TValue value)
{
if (node == sentinel)
{
node = new Node(key, value, sentinel);
return true;
}

int compare = key.CompareTo(node.key);
if (compare < 0)
{
if (!Insert(ref node.left, key, value))
{
return false;
}
}
else if (compare > 0)
{
if (!Insert(ref node.right, key, value))
{
return false;
}
}
else
{
return false;
}

Skew(ref node);
Split(ref node);

return true;
}

private bool Delete(ref Node node, TKey key)
{
if (node == sentinel)
{
return (deleted != null);
}

int compare = key.CompareTo(node.key);
if (compare < 0)
{
if (!Delete(ref node.left, key))
{
return false;
}
}
else
{
if (compare == 0)
{
deleted = node;
}
if (!Delete(ref node.right, key))
{
return false;
}
}

if (deleted != null)
{
deleted.key = node.key;
deleted.value = node.value;
deleted = null;
node = node.right;
}
else if (node.left.level < node.level - 1
|| node.right.level < node.level - 1)
{
--node.level;
if (node.right.level > node.level)
{
node.right.level = node.level;
}
Skew(ref node);
Skew(ref node.right);
Skew(ref node.right.right);
Split(ref node);
Split(ref node.right);
}

return true;
}

private Node Search(Node node, TKey key)
{
if (node == sentinel)
{
return null;
}

int compare = key.CompareTo(node.key);
if (compare < 0)
{
return Search(node.left, key);
}
else if (compare > 0)
{
return Search(node.right, key);
}
else
{
return node;
}
}

public bool Add(TKey key, TValue value)
{
return Insert(ref root, key, value);
}

public bool Remove(TKey key)
{
return Delete(ref root, key);
}

public TValue this[TKey key]
{
get
{
Node node = Search(root, key);
return node == null ? default(TValue) :
node.value;
}
set
{
Node node = Search(root, key);
if (node == null)
{
Add(key, value);
}
else
{
node.value = value;
}
}
}
}

class Program
{
static void Test(int[] values)
{
AATree<int, int> tree = new AATree<int, int>();
for (int i = 0; i < values.Length; i++)
{
if (!tree.Add(values[i], (i + 1)))
{
Console.WriteLine("Failed to insert
{0}", values[i]);
}
}
for (int i = 0; i < values.Length; i++)
{
for (int j = 0; j < i; j++)
{
if (tree[values[j]] != 0)
{
Console.WriteLine("Found
deleted key {0}", values[j]);
}
}
for (int j = i; j < values.Length; j++)
{
if (tree[values[j]] != (j + 1))
{
Console.WriteLine("Could not
find key {0}", values[j]);
}
}
if (!tree.Remove(values[i]))
{
Console.WriteLine("Failed to delete
{0}", values[i]);
}
}
}

static void Main(string[] args)
{
Test(new int[] { 1 });

Test(new int[] { 1, 2 });
Test(new int[] { 2, 1 });

Test(new int[] { 1, 2, 3 });
Test(new int[] { 2, 1, 3 });
Test(new int[] { 1, 3, 2 });
Test(new int[] { 2, 3, 1 });
Test(new int[] { 3, 1, 2 });
Test(new int[] { 3, 2, 1 });

Test(new int[] { 1, 2, 3, 4 });
Test(new int[] { 2, 1, 3, 4 });
Test(new int[] { 1, 3, 2, 4 });
Test(new int[] { 2, 3, 1, 4 });
Test(new int[] { 3, 1, 2, 4 });
Test(new int[] { 3, 2, 1, 4 });
Test(new int[] { 1, 2, 4, 3 });
Test(new int[] { 2, 1, 4, 3 });
Test(new int[] { 1, 3, 4, 2 });
Test(new int[] { 2, 3, 4, 1 });
Test(new int[] { 3, 1, 4, 2 });
Test(new int[] { 3, 2, 4, 1 });
Test(new int[] { 1, 4, 2, 3 });
Test(new int[] { 2, 4, 1, 3 });
Test(new int[] { 1, 4, 3, 2 });
Test(new int[] { 2, 4, 3, 1 });
Test(new int[] { 3, 4, 1, 2 });
Test(new int[] { 3, 4, 2, 1 });
Test(new int[] { 4, 1, 2, 3 });
Test(new int[] { 4, 2, 1, 3 });
Test(new int[] { 4, 1, 3, 2 });
Test(new int[] { 4, 2, 3, 1 });
Test(new int[] { 4, 3, 1, 2 });
Test(new int[] { 4, 3, 2, 1 });

for (int count = 0; count < 1000; count++)
{
int[] a = new int[100];
Random random = new Random();
for (int i = 0; i < a.Length; i++)
{
int r;
bool dup;
do
{
dup = false;
r = random.Next();
for (int j = 0; j < i; j++)
{
if (a[j] == r)
{
dup = true;
break;
}
}
}
while (dup);
a[i] = r;
}
Test(a);
}
}
}

On 6/16/2011 10:24 PM, tom wrote:
> hi , i found an balanced tree on the internet
>
> i want to put a string in it value , not a number . how could i change
> it?

As far as I can see then the class is generic, so you do not need to
change it to use different types for key or value.

AATree<string,string>
AATree<string,int>
AATree<int,string>
AATree<int,int>
AATree<Foo,Bar>

should all work fine.

Arne

On Jun 17, 6:32*am, Peter Duniho <NpOeStPe...@NnOwSlPiAnMk.com> wrote:
> On 6/16/11 7:24 PM, tom wrote:
>
> > hi , i found an balanced tree on the internet
>
> > i want to put a string in it value , not a number . how could i change
> > it?
>
> The code currently uses "AATree<int, int>" as the declaration for the
> types used. *Have you tried changing the word "int" to "string" there?

thanks
you mean i should change this :
public class AATree<TKey, TValue> where TKey : IComparable<TKey>
to what?

On Jun 17, 6:39*am, tom <tom.t.2...@gmail.com> wrote:
> On Jun 17, 6:32*am, Peter Duniho <NpOeStPe...@NnOwSlPiAnMk.com> wrote:
>
> > On 6/16/11 7:24 PM, tom wrote:
>
> > > hi , i found an balanced tree on the internet
>
> > > i want to put a string in it value , not a number . how could i change
> > > it?
>
> > The code currently uses "AATree<int, int>" as the declaration for the
> > types used. *Have you tried changing the word "int" to "string" there?
>
> thanks
> you mean i should change this :
> *public class AATree<TKey, TValue> where TKey : IComparable<TKey>
> to what?


i made this change but now it have some error
AATree<string, string> tree = new AATree<string, string>();

On Jun 17, 6:42*am, tom <tom.t.2...@gmail.com> wrote:
> On Jun 17, 6:39*am, tom <tom.t.2...@gmail.com> wrote:
>
>
>
>
>
> > On Jun 17, 6:32*am, Peter Duniho <NpOeStPe...@NnOwSlPiAnMk.com> wrote:
>
> > > On 6/16/11 7:24 PM, tom wrote:
>
> > > > hi , i found an balanced tree on the internet
>
> > > > i want to put a string in it value , not a number . how could i change
> > > > it?
>
> > > The code currently uses "AATree<int, int>" as the declaration for the
> > > types used. *Have you tried changing the word "int" to "string" there?
>
> > thanks
> > you mean i should change this :
> > *public class AATree<TKey, TValue> where TKey : IComparable<TKey>
> > to what?
>
> i made this change but now it have some error
> AATree<string, string> tree = new AATree<string, string>();- Hide quoted text -
>
> - Show quoted text -



tree.Add(values[i], (i + 1))
it said it could not convert int to string

On Jun 17, 6:59*am, Peter Duniho <NpOeStPe...@NnOwSlPiAnMk.com> wrote:
> On 6/16/11 7:47 PM, tom wrote:
>
> > tree.Add(values[i], (i + 1))
> > it said it could not convert int to string
>
> If you want the data structure to store strings, then pass it strings,
> not ints.
>
> If you want to pass it ints, then why in the world would you say you
> want to change the type to string?

sorry , how should i pass it string ?

On Jun 17, 7:06*am, tom <tom.t.2...@gmail.com> wrote:
> On Jun 17, 6:59*am, Peter Duniho <NpOeStPe...@NnOwSlPiAnMk.com> wrote:
>
> > On 6/16/11 7:47 PM, tom wrote:
>
> > > tree.Add(values[i], (i + 1))
> > > it said it could not convert int to string
>
> > If you want the data structure to store strings, then pass it strings,
> > not ints.
>
> > If you want to pass it ints, then why in the world would you say you
> > want to change the type to string?
>
> sorry , *how should i pass it string ?


i did this too , but it did't work .
static void Test(string[] values)

On Jun 17, 7:20*am, tom <tom.t.2...@gmail.com> wrote:
> On Jun 17, 7:06*am, tom <tom.t.2...@gmail.com> wrote:
>
> > On Jun 17, 6:59*am, Peter Duniho <NpOeStPe...@NnOwSlPiAnMk.com> wrote:
>
> > > On 6/16/11 7:47 PM, tom wrote:
>
> > > > tree.Add(values[i], (i + 1))
> > > > it said it could not convert int to string
>
> > > If you want the data structure to store strings, then pass it strings,
> > > not ints.
>
> > > If you want to pass it ints, then why in the world would you say you
> > > want to change the type to string?
>
> > sorry , *how should i pass it string ?
>
> i did this too , but it did't work .
> static void Test(string[] values)

i made that code smaller , and i solve some of it problems but not
all, plz help





using System;

public class AATree<TKey, TValue> where TKey : IComparable<TKey>
{
private class Node
{
// node internal data
internal int level;
internal Node left;
internal Node right;

// user data
internal TKey key;
internal TValue value;

// constuctor for the sentinel node
internal Node()
{
this.level = 0;
this.left = this;
this.right = this;
}

// constuctor for regular nodes (that all start life as leaf
nodes)
internal Node(TKey key, TValue value, Node sentinel)
{
this.level = 1;
this.left = sentinel;
this.right = sentinel;
this.key = key;
this.value = value;
}
}

Node root;
Node sentinel;
Node deleted;

public AATree()
{
root = sentinel = new Node();
deleted = null;
}

private void Skew(ref Node node)
{
if (node.level == node.left.level)
{
// rotate right
Node left = node.left;
node.left = left.right;
left.right = node;
node = left;
}
}

private void Split(ref Node node)
{
if (node.right.right.level == node.level)
{
// rotate left
Node right = node.right;
node.right = right.left;
right.left = node;
node = right;
node.level++;
}
}

private bool Insert(ref Node node, TKey key, TValue value)
{
if (node == sentinel)
{
node = new Node(key, value, sentinel);
return true;
}

int compare = key.CompareTo(node.key);
if (compare < 0)
{
if (!Insert(ref node.left, key, value))
{
return false;
}
}
else if (compare > 0)
{
if (!Insert(ref node.right, key, value))
{
return false;
}
}
else
{
return false;
}

Skew(ref node);
Split(ref node);

return true;
}
public bool Add(TKey key, TValue value)
{
return Insert(ref root, key, value);
}




}

class Program
{
static void Test(string[] values)
{
AATree<string, string> tree = new AATree<string, string>();
for (int i = 0; i < values.Length; i++)
{
if (!tree.Add(values[i], (i + 1)))
{
Console.WriteLine("Failed to insert {0}", values[i]);
}
}
for (int i = 0; i < values.Length; i++)
{
for (int j = 0; j < i; j++)
{
if (tree[values[j]] !=" ")
{
Console.WriteLine("Found deleted key {0}",
values[j]);
}
}
for (int j = i; j < values.Length; j++)
{
if (tree[values[j]] != (j + 1))
{
Console.WriteLine("Could not find key {0}",
values[j]);
}
}
// if (!tree.Remove(values[i]))
{
// Console.WriteLine("Failed to delete {0}",
values[i]);
}
}
}

static void Main(string[] args)
{
//Test(new int[] { 1 });


Test(new string[] { x, yz });
}
}

On Jun 17, 7:38*am, tom <tom.t.2...@gmail.com> wrote:
> On Jun 17, 7:20*am, tom <tom.t.2...@gmail.com> wrote:
>
>
>
>
>
> > On Jun 17, 7:06*am, tom <tom.t.2...@gmail.com> wrote:
>
> > > On Jun 17, 6:59*am, Peter Duniho <NpOeStPe...@NnOwSlPiAnMk.com> wrote:
>
> > > > On 6/16/11 7:47 PM, tom wrote:
>
> > > > > tree.Add(values[i], (i + 1))
> > > > > it said it could not convert int to string
>
> > > > If you want the data structure to store strings, then pass it strings,
> > > > not ints.
>
> > > > If you want to pass it ints, then why in the world would you say you
> > > > want to change the type to string?
>
> > > sorry , *how should i pass it string ?
>
> > i did this too , but it did't work .
> > static void Test(string[] values)
>
> i made that code smaller , and i solve some of it problems but not
> all, plz help
>
> using System;
>
> public class AATree<TKey, TValue> where TKey : IComparable<TKey>
> {
> * * private class Node
> * * {
> * * * * // node internal data
> * * * * internal int level;
> * * * * internal Node left;
> * * * * internal Node right;
>
> * * * * // user data
> * * * * internal TKey key;
> * * * * internal TValue value;
>
> * * * * // constuctor for the sentinel node
> * * * * internal Node()
> * * * * {
> * * * * * * this.level = 0;
> * * * * * * this.left = this;
> * * * * * * this.right = this;
> * * * * }
>
> * * * * // constuctor for regular nodes (that all start life as leaf
> nodes)
> * * * * internal Node(TKey key, TValue value, Node sentinel)
> * * * * {
> * * * * * * this.level = 1;
> * * * * * * this.left = sentinel;
> * * * * * * this.right = sentinel;
> * * * * * * this.key = key;
> * * * * * * this.value = value;
> * * * * }
> * * }
>
> * * Node root;
> * * Node sentinel;
> * * Node deleted;
>
> * * public AATree()
> * * {
> * * * * root = sentinel = new Node();
> * * * * deleted = null;
> * * }
>
> * * private void Skew(ref Node node)
> * * {
> * * * * if (node.level == node.left.level)
> * * * * {
> * * * * * * // rotate right
> * * * * * * Node left = node.left;
> * * * * * * node.left = left.right;
> * * * * * * left.right = node;
> * * * * * * node = left;
> * * * * }
> * * }
>
> * * private void Split(ref Node node)
> * * {
> * * * * if (node.right.right.level == node.level)
> * * * * {
> * * * * * * // rotate left
> * * * * * * Node right = node.right;
> * * * * * * node.right = right.left;
> * * * * * * right.left = node;
> * * * * * * node = right;
> * * * * * * node.level++;
> * * * * }
> * * }
>
> * * private bool Insert(ref Node node, TKey key, TValue value)
> * * {
> * * * * if (node == sentinel)
> * * * * {
> * * * * * * node = new Node(key, value, sentinel);
> * * * * * * return true;
> * * * * }
>
> * * * * int compare = key.CompareTo(node.key);
> * * * * if (compare < 0)
> * * * * {
> * * * * * * if (!Insert(ref node.left, key, value))
> * * * * * * {
> * * * * * * * * return false;
> * * * * * * }
> * * * * }
> * * * * else if (compare > 0)
> * * * * {
> * * * * * * if (!Insert(ref node.right, key, value))
> * * * * * * {
> * * * * * * * * return false;
> * * * * * * }
> * * * * }
> * * * * else
> * * * * {
> * * * * * * return false;
> * * * * }
>
> * * * * Skew(ref node);
> * * * * Split(ref node);
>
> * * * * return true;
> * * }
> * * public bool Add(TKey key, TValue value)
> * * {
> * * * * return Insert(ref root, key, value);
> * * }
>
> }
>
> class Program
> {
> * * static void Test(string[] values)
> * * {
> * * * * AATree<string, string> tree = new AATree<string, string>();
> * * * * for (int i = 0; i < values.Length; i++)
> * * * * {
> * * * * * * if (!tree.Add(values[i], (i + 1)))
> * * * * * * {
> * * * * * * * * Console.WriteLine("Failed to insert {0}",values[i]);
> * * * * * * }
> * * * * }
> * * * * for (int i = 0; i < values.Length; i++)
> * * * * {
> * * * * * * for (int j = 0; j < i; j++)
> * * * * * * {
> * * * * * * * * if (tree[values[j]] !=" ")
> * * * * * * * * {
> * * * * * * * * * * Console.WriteLine("Found deleted key {0}",
> values[j]);
> * * * * * * * * }
> * * * * * * }
> * * * * * * for (int j = i; j < values.Length; j++)
> * * * * * * {
> * * * * * * * *if (tree[values[j]] != (j + 1))
> * * * * * * * * {
> * * * * * * * * * * Console.WriteLine("Could not findkey {0}",
> values[j]);
> * * * * * * * * }
> * * * * * * }
> * * * * * *// if (!tree.Remove(values[i]))
> * * * * * * {
> * * * * * * * *// Console.WriteLine("Failed to delete {0}",
> values[i]);
> * * * * * * }
> * * * * }
> * * }
>
> * * static void Main(string[] args)
> * * {
> * * * * //Test(new int[] { 1 });
>
> * * * * Test(new string[] { x, yz });
> * * }
>
>
>
> }- Hide quoted text -
>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -

i undrestand one other problem : i should do -----
test (new string {"x","xy"})



plz help for other problems . ... .

On Jun 17, 7:45*am, tom <tom.t.2...@gmail.com> wrote:
> On Jun 17, 7:38*am, tom <tom.t.2...@gmail.com> wrote:
>
>
>
>
>
> > On Jun 17, 7:20*am, tom <tom.t.2...@gmail.com> wrote:
>
> > > On Jun 17, 7:06*am, tom <tom.t.2...@gmail.com> wrote:
>
> > > > On Jun 17, 6:59*am, Peter Duniho <NpOeStPe...@NnOwSlPiAnMk.com> wrote:
>
> > > > > On 6/16/11 7:47 PM, tom wrote:
>
> > > > > > tree.Add(values[i], (i + 1))
> > > > > > it said it could not convert int to string
>
> > > > > If you want the data structure to store strings, then pass it strings,
> > > > > not ints.
>
> > > > > If you want to pass it ints, then why in the world would you say you
> > > > > want to change the type to string?
>
> > > > sorry , *how should i pass it string ?
>
> > > i did this too , but it did't work .
> > > static void Test(string[] values)
>
> > i made that code smaller , and i solve some of it problems but not
> > all, plz help
>
> > using System;
>
> > public class AATree<TKey, TValue> where TKey : IComparable<TKey>
> > {
> > * * private class Node
> > * * {
> > * * * * // node internal data
> > * * * * internal int level;
> > * * * * internal Node left;
> > * * * * internal Node right;
>
> > * * * * // user data
> > * * * * internal TKey key;
> > * * * * internal TValue value;
>
> > * * * * // constuctor for the sentinel node
> > * * * * internal Node()
> > * * * * {
> > * * * * * * this.level = 0;
> > * * * * * * this.left = this;
> > * * * * * * this.right = this;
> > * * * * }
>
> > * * * * // constuctor for regular nodes (that all start life asleaf
> > nodes)
> > * * * * internal Node(TKey key, TValue value, Node sentinel)
> > * * * * {
> > * * * * * * this.level = 1;
> > * * * * * * this.left = sentinel;
> > * * * * * * this.right = sentinel;
> > * * * * * * this.key = key;
> > * * * * * * this.value = value;
> > * * * * }
> > * * }
>
> > * * Node root;
> > * * Node sentinel;
> > * * Node deleted;
>
> > * * public AATree()
> > * * {
> > * * * * root = sentinel = new Node();
> > * * * * deleted = null;
> > * * }
>
> > * * private void Skew(ref Node node)
> > * * {
> > * * * * if (node.level == node.left.level)
> > * * * * {
> > * * * * * * // rotate right
> > * * * * * * Node left = node.left;
> > * * * * * * node.left = left.right;
> > * * * * * * left.right = node;
> > * * * * * * node = left;
> > * * * * }
> > * * }
>
> > * * private void Split(ref Node node)
> > * * {
> > * * * * if (node.right.right.level == node.level)
> > * * * * {
> > * * * * * * // rotate left
> > * * * * * * Node right = node.right;
> > * * * * * * node.right = right.left;
> > * * * * * * right.left = node;
> > * * * * * * node = right;
> > * * * * * * node.level++;
> > * * * * }
> > * * }
>
> > * * private bool Insert(ref Node node, TKey key, TValue value)
> > * * {
> > * * * * if (node == sentinel)
> > * * * * {
> > * * * * * * node = new Node(key, value, sentinel);
> > * * * * * * return true;
> > * * * * }
>
> > * * * * int compare = key.CompareTo(node.key);
> > * * * * if (compare < 0)
> > * * * * {
> > * * * * * * if (!Insert(ref node.left, key, value))
> > * * * * * * {
> > * * * * * * * * return false;
> > * * * * * * }
> > * * * * }
> > * * * * else if (compare > 0)
> > * * * * {
> > * * * * * * if (!Insert(ref node.right, key, value))
> > * * * * * * {
> > * * * * * * * * return false;
> > * * * * * * }
> > * * * * }
> > * * * * else
> > * * * * {
> > * * * * * * return false;
> > * * * * }
>
> > * * * * Skew(ref node);
> > * * * * Split(ref node);
>
> > * * * * return true;
> > * * }
> > * * public bool Add(TKey key, TValue value)
> > * * {
> > * * * * return Insert(ref root, key, value);
> > * * }
>
> > }
>
> > class Program
> > {
> > * * static void Test(string[] values)
> > * * {
> > * * * * AATree<string, string> tree = new AATree<string, string>();
> > * * * * for (int i = 0; i < values.Length; i++)
> > * * * * {
> > * * * * * * if (!tree.Add(values[i], (i + 1)))
> > * * * * * * {
> > * * * * * * * * Console.WriteLine("Failed to insert {0}", values[i]);
> > * * * * * * }
> > * * * * }
> > * * * * for (int i = 0; i < values.Length; i++)
> > * * * * {
> > * * * * * * for (int j = 0; j < i; j++)
> > * * * * * * {
> > * * * * * * * * if (tree[values[j]] !=" ")
> > * * * * * * * * {
> > * * * * * * * * * * Console.WriteLine("Found deleted key {0}",
> > values[j]);
> > * * * * * * * * }
> > * * * * * * }
> > * * * * * * for (int j = i; j < values.Length; j++)
> > * * * * * * {
> > * * * * * * * *if (tree[values[j]] != (j + 1))
> > * * * * * * * * {
> > * * * * * * * * * * Console.WriteLine("Could not find key {0}",
> > values[j]);
> > * * * * * * * * }
> > * * * * * * }
> > * * * * * *// if (!tree.Remove(values[i]))
> > * * * * * * {
> > * * * * * * * *// Console.WriteLine("Failed to delete {0}",
> > values[i]);
> > * * * * * * }
> > * * * * }
> > * * }
>
> > * * static void Main(string[] args)
> > * * {
> > * * * * //Test(new int[] { 1 });
>
> > * * * * Test(new string[] { x, yz });
> > * * }
>
> > }- Hide quoted text -
>
> > - Show quoted text -- Hide quoted text -
>
> > - Show quoted text -
>
> i undrestand one other problem : i should do -----
> test (new string {"x","xy"})
>
> plz help for other problems * *. ... .- Hide quoted text -
>
> - Show quoted text -


Error 1 The best overloaded method match for
'AATree<string,string>.Add(string, string)' has some invalid
arguments