Pattern for splitting, traversing and tracking objects

Question

Hi, can anyome help me find an elegant design for splitting, traversing and tracking objects.

The diagram below shows an object with an initial size of 100 which is spilt into two (50, 75) then one of the child objects (75) is subsequently split into three (25, 25 ,25).

My question is can anyone think of an elegant design that will allow me from any object to traverse the entire tree (for example to identify the root parent from any subsequently child object)?

My current attempt (see code below) uses the instance fields Parent and Children to track the objects but it obviously doesn’t give me the functionality I require – as from Obj [Id:6] I cannot recursively find the root parent.

Can anyone think of a solution? I don’t think a double linked list will work as the spilt parameter is not limited to just two.

                      Obj [Id:1, Size:100]
                             |
                    Split operation (50, 75)
                             <>
       Obj [Id:2, Size:25]   Obj [Id:2, Size:75]
                                          |
                              Split operation (25, 25, 25)
                                          <>
         Obj [Id:4, Size:25]     Obj [Id:5, Size:25]    Obj [Id:6, Size:25]




public class SplitableObj : IEquatable<SplitableObj>
{
    private Guid _id = Guid.NewGuid();
    private int _size;
    private SplitableObj _parent;
    private List<SplitableObj> _childern;

    public SplitableObj(int size)
    {
        _size = size;
    }
    public Guid id
    {
        get { return _id; }
        set { _id = value; }
    }

    public SplitableObj Parent
    {
        get { return _parent; }
        set { _parent = value; }
    }

    public List<SplitableObj> Children
    {
        get { return _childern; }
        set { _childern = value; }
    }

    public int Size
    {
        get { return _size; }
        set { _size = value; }
    }

    public IEnumerable<SplitableObj> Split(params int[] splits)
    {
        if (splits.Length < 2)
        {
            throw new ApplicationException("splits must be least 2.");
        }

        int totalSplits = 0;
        foreach (int split in splits)
        {
            totalSplits += split;
        }

        if (_size != totalSplits)
        {
            throw new ApplicationException("Total splits must equal Size.");
        }

        foreach (int split in splits)
        {
            SplitableObj splitAmount = new SplitableObj(split);
            splitAmount.Parent = this;
            this.Children.Add(splitAmount);
            yield return splitAmount;
        }
    }

    public bool Equals(SplitableObj splitableObj)
    {
        if (splitableObj == null) return false;
        return Equals(_id, splitableObj._id);
    }
    public override bool Equals(object obj)
    {
        if (ReferenceEquals(this, obj)) return true;
        return Equals(obj as SplitableObj);
    }
    public override int GetHashCode()
    {
        return _id.GetHashCode();
    }
}

Answer 1

don't know. Please show an example using a B+ tree.

Answer 2

Homework?

set RootObject to the current object.
while the parent of RootObject is not undefined, set RootObject to its parent.
Finally, return RootObject.