b-tree

  • Thread starter Thread starter tom
  • Start date Start date
T

tom

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 + 1)))
{
Console.WriteLine("Failed to insert
{0}", values);
}
}
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))
{
Console.WriteLine("Failed to delete
{0}", values);
}
}
}

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 = r;
}
Test(a);
}
}
}
 
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?
Click to expand...

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
 
The code currently uses "AATree<int, int>" as the declaration for the
types used.  Have you tried changing the word "int" to "string" there?
Click to expand...

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


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

- Show quoted text -
Click to expand...



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


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?
Click to expand...


sorry , how should i pass it string ?
 
On 6/16/11 7:47 PM, tom wrote:
tree.Add(values, (i + 1))
it said it could not convert int to string
Click to expand...
Click to expand...

If you want the data structure to store strings, then pass it strings,
not ints.
Click to expand...
If you want to pass it ints, then why in the world would you say you
want to change the type to string?
Click to expand...

sorry ,  how should i pass it string ?
Click to expand...



i did this too , but it did't work .
static void Test(string[] values)
 
On 6/16/11 7:47 PM, tom wrote:
tree.Add(values, (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?
Click to expand...
Click to expand...

sorry ,  how should i pass it string ?
Click to expand...

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


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 + 1)))
{
Console.WriteLine("Failed to insert {0}", values);
}
}
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))
{
// Console.WriteLine("Failed to delete {0}",
values);
}
}
}

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


Test(new string[] { x, yz });
}
}
 
On 6/16/11 7:47 PM, tom wrote:
tree.Add(values, (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 ?
Click to expand...
Click to expand...

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

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 + 1)))
            {
                Console.WriteLine("Failed to insert {0}",values);
            }
        }
        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))
            {
               // Console.WriteLine("Failed to delete {0}",
values);
            }
        }
    }

    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 -
Click to expand...


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



plz help for other problems . ... .
 
On 6/16/11 7:47 PM, tom wrote:
tree.Add(values, (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)
Click to expand...
Click to expand...

i made that code smaller , and i solve some of it problems but not
all, plz help
Click to expand...
using System;
Click to expand...
public class AATree<TKey, TValue> where TKey : IComparable<TKey>
{
    private class Node
    {
        // node internal data
        internal int level;
        internal Node left;
        internal Node right;
Click to expand...
        // user data
        internal TKey key;
        internal TValue value;
Click to expand...
        // constuctor for the sentinel node
        internal Node()
        {
            this.level = 0;
            this.left = this;
            this.right = this;
        }
Click to expand...
        // 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;
        }
    }
Click to expand...
    Node root;
    Node sentinel;
    Node deleted;
Click to expand...
    public AATree()
    {
        root = sentinel = new Node();
        deleted = null;
    }
Click to expand...
    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;
        }
    }
Click to expand...
    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++;
        }
    }
Click to expand...
    private bool Insert(ref Node node, TKey key, TValue value)
    {
        if (node == sentinel)
        {
            node = new Node(key, value, sentinel);
            return true;
        }
Click to expand...
        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;
        }
Click to expand...
        Skew(ref node);
        Split(ref node);
Click to expand...
        return true;
    }
    public bool Add(TKey key, TValue value)
    {
        return Insert(ref root, key, value);
    }
}
Click to expand...

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 + 1)))
            {
                Console.WriteLine("Failed to insert {0}", values);
            }
        }
        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))
            {
               // Console.WriteLine("Failed to delete {0}",
values);
            }
        }
    }
Click to expand...

    static void Main(string[] args)
    {
        //Test(new int[] { 1 });
Click to expand...
        Test(new string[] { x, yz });
    }
Click to expand...
}- Hide quoted text -
Click to expand...
- Show quoted text -- Hide quoted text -
Click to expand...
- Show quoted text -
Click to expand...

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

plz help for other problems    . ... .- Hide quoted text -

- Show quoted text -
Click to expand...



Error 1 The best overloaded method match for
'AATree<string,string>.Add(string, string)' has some invalid
arguments
 
On 6/16/11 7:47 PM, tom wrote:
tree.Add(values, (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 + 1)))
            {
                Console.WriteLine("Failed to insert {0}", values);
            }
        }
        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))
            {
               // Console.WriteLine("Failed to delete{0}",
values);
            }
        }
    }
    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 -
Click to expand...
Click to expand...

i undrestand one other problem : i should do -----
test (new string {"x","xy"})
Click to expand...
plz help for other problems    . ... .- Hide quoted text -
Click to expand...
- Show quoted text -
Click to expand...

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

- Show quoted text -
Click to expand...


PETER help me plzzzzzzzzzzz .....................................
 
Back
Top