Results 1 to 6 of 6

Thread: Binary Tree

  1. #1

    Thread Starter
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594

    Binary Tree

    The .Net framework is horribly lacking a binary tree. The attached file remedies this lack. It provides the interface ISet, which defines the interface of a lookup-only container, and the classes TreeSet, which is an implementation of ISet, and TreeDictionary, which is an implementation of IDictionary (from System.Collections). It also provides the hidden class BinaryTree, which is a balanced binary search tree (AVL tree), to provide the implementation for both tree classes.
    Attached Files Attached Files
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  2. #2
    New Member
    Join Date
    Feb 2006
    Posts
    3

    Re: Binary Tree

    Hey, you're tree looks very nice but


    private void RotateLeft(ref TreeNode node)
    {
    TreeNode t = node.right;
    node.right = t.left;
    if(node.right != null)
    node.right.parent = node;
    t.left = node;
    t.parent = node.parent;
    if(t.left != null)
    t.left.parent = t;
    AdjustHeight(node);
    AdjustHeight(t);
    node = t;
    }

    and

    private void RotateRight(ref TreeNode node)
    {
    TreeNode t = node.left;
    node.left = t.right;
    if(node.left != null)
    node.left.parent = node;
    t.right = node;
    if(t.right != null)
    t.right.parent = t;
    t.parent = node.parent;
    AdjustHeight(node);
    AdjustHeight(t);
    node = t;
    }

    differs from each others.

    When is the t.parent=node.parent supposed to be?

  3. #3

    Thread Starter
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594

    Re: Binary Tree

    It makes no difference. The two statements that are exchanged don't access common data and thus don't interefere with each other.

    Please use [code][/code] tags when posting code.
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  4. #4
    New Member
    Join Date
    Feb 2006
    Posts
    3

    Re: Binary Tree

    Yeah I noticed thanks for answering

    Btw, normaly one would do a double right or double left but you do leftright and rightleft, a short explanation would be nice.

  5. #5

    Thread Starter
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594

    Re: Binary Tree

    I can't remember. It's been a long time since I wrote this thing, and I strictly followed the theoretical approach in my university scripts. (In other words, don't expect this tree to perform ideally. AFAIK, red-black trees are better, but I don't know how to implement those.)
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  6. #6
    New Member
    Join Date
    Feb 2006
    Posts
    3

    Re: Binary Tree

    Ok, thanks for the reply thou.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width