Binary Tree

[CornedBee]

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.

[Cold_Fusion]

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?

[CornedBee]

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 tags when posting code.

[Cold_Fusion]

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.

[CornedBee]

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.)

[Cold_Fusion]

Ok, thanks for the reply thou.