c# coding question you need to create code which insert, Traverse (you only need
ID: 3902928 • Letter: C
Question
c# coding question you need to create code which insert, Traverse (you only need one traversal),Find (note that in the splay tree “Find” puts the found node at the root)
FindAndDelete (this should search for a specific entry, if it exists delete it and then properly fix the tree) for
Red Black Tree
A 2-3-4 Tree.
It’s up to you to write test cases to show that the trees are working properly for small numbers of inputs (less than 20 elements is fine).
You will likely need to make several methods which make this work (rotations for example), show tests for each of those as well.
Explanation / Answer
Tree.cs
***************
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _234Tree
{
public class Tree
{
public Node Root;
public Tree()
{
Root = null;
}
public void Insert(ulong value)
{
if (Root == null)
{
Root = new Node(value);
return;
}
Node curr = Root;
Node parent=null;
while(curr!=null)
{
//If we encounter a node with 3 keys, restructure the node, pushing the middle key upwards,
if (curr.Keys.Count == 3)
{
if (parent == null)//the only time when the parent is null is when we are at the root node
{
ulong k=curr.Pop(1).Value;
Node newRoot = new Node(k);
Node[] newNodes = curr.Split();
newRoot.InsertEdge(newNodes[0]);
newRoot.InsertEdge(newNodes[1]);
Root = newRoot;//make the new subtree's root node the entire tree's root node
//curr now points to the left node
curr = newRoot;
}
else
{
ulong? k=curr.Pop(1);//pop middle key and push it up
if(k!=null)
{
parent.Push(k.Value);//push the value up to the parent
}
Node[] newNodes = curr.Split();
//int pos0=parent.FindEdgePosition(newNodes[0].Keys[0].Value);
//parent.SetEdge(pos0, newNodes[0]);
int pos1 = parent.FindEdgePosition(newNodes[1].Keys[0]);
parent.InsertEdge(newNodes[1]);
int posCurr=parent.FindEdgePosition(value);
curr=parent.GetEdge(posCurr);
}
}
parent=curr;
curr=curr.Traverse(value);
if(curr==null)//leave node
{
parent.Push(value);
}
}
}
public Node Find(ulong k)
{
Node curr = Root;
while (curr != null)
{
if(curr.HasKey(k)>=0)
{
return curr;
}
else
{
int p=curr.FindEdgePosition(k);
curr=curr.GetEdge(p);
}
}
return null;
}
public void FindAndDelete(ulong k)
{
//1 if in the leaf node, simply remove it.
//2 as we encounter 1 key nodes,
// a) pull the key from the siblings if they have 2 or more keys, via rotation
// b) if both siblings have only 1 key, the parent (except if it is root) will always have 2 or more keys,
// so pull a key from parent and fuse with it's sibling.
// c) if siblings have only 1 key and parent is a 1 key root node, fuse all 3 nodes into 1
if(Find(k) == null) {
break;
}
Node curr = Root;
Node parent = null;
while (curr != null)
{
//check for 1 key nodes
if(curr.Keys.Count==1)
{
if (curr!=Root)//skip root node
{
ulong cK=curr.Keys[0];
int edgePos=parent.FindEdgePosition(cK);
bool? takeRight = null;
Node sibling = null;
if (edgePos > -1)//edge is found
{
if (edgePos < 3)//use right sibling if it is not the right most node
{
sibling = parent.GetEdge(edgePos + 1);
if (sibling.Keys.Count > 1)
{
takeRight = true;
}
}
if (takeRight == null)//if this is the right most node, or there wasn't any left sibling with >1 keys
{
if (edgePos > 0)//use left sibling if it is not the left most node
{
sibling = parent.GetEdge(edgePos - 1);
if (sibling.Keys.Count > 1)
{
takeRight = false;//use left
}
}
}
if (takeRight != null)//case 2a) perform rotation with sibling
{
ulong pK = 0;
ulong sK = 0;
if (takeRight.Value)//take from right sibling
{
pK = parent.Pop(edgePos).Value;//take parent's key (corresponding to this edge)
sK = sibling.Pop(0).Value;//take sibling's left most key
if (sibling.Edges.Count > 0)
{
Node edge = sibling.RemoveEdge(0);//move left most edge
curr.InsertEdge(edge);
}
}
else//take from left sibling
{
pK = parent.Pop(edgePos).Value;//take parent's key (corresponding to this edge)
sK = sibling.Pop(sibling.Keys.Count-1).Value;//take sibling's right most key
if (sibling.Edges.Count > 0)
{
Node edge = sibling.RemoveEdge(sibling.Edges.Count-1);//move right most edge
curr.InsertEdge(edge);
}
}
parent.Push(sK);
curr.Push(pK);
}
else//case 2b) or 2c) no siblings with >1 keys available
{
ulong? pK = null;
if(parent.Edges.Count>=2)//case 2b
{
if (edgePos == 0)//if n is left most node, take parent's first key
{
pK = parent.Pop(0);
}
else if(edgePos == parent.Edges.Count)//if n is the right most node take parent's right most key
{
pK = parent.Pop(parent.Keys.Count-1);
}
else//take parent's middle key
{
pK = parent.Pop(1);
}
if (pK != null)
{
curr.Push(pK.Value);
Node sib=null;
if (edgePos !=parent.Edges.Count)//use right sibling if it is not the rightmost node
{
sib = parent.RemoveEdge(edgePos + 1);
}
else
{
sib = parent.RemoveEdge(parent.Edges.Count-1);
}
curr.Fuse(sib);
}
}
else//case 2c
{
curr.Fuse(parent,sibling);
Root = curr;
parent = null;
}
}
}
}
}
int rmPos = -1;
if ((rmPos = curr.HasKey(k)) >= 0)
{
//if it is a leaf node, remove the key
if(curr.Edges.Count==0)
{
if (curr.Keys.Count == 0)
{
parent.Edges.Remove(curr);
}
else
{
curr.Pop(rmPos);
}
}
else//otherwise, replace it with the next higher key
{
Node successor = Min(curr.Edges[rmPos]);
ulong sK = successor.Keys[0];
if(successor.Keys.Count>1)
{
successor.Pop(0);
}
else
{
if (successor.Edges.Count == 0)//just remove it if it is leaf
{
Node p = successor.Parent;
p.RemoveEdge(successor);
}
else
{
//not leaf so we have to rotate
}
}
}
curr = null;
}
else
{
//not found, so we move down the tree
int p = curr.FindEdgePosition(k);
parent = curr;
curr = curr.GetEdge(p);
}
}
}
public ulong[] Inorder(Node n = null)
{
if (n == null)
{
n = Root;
}
List<ulong> items = new List<ulong>();
Tuple<Node,int> curr=new Tuple<Node,int>(n,0);
Stack<Tuple<Node, int>> stack = new Stack<Tuple<Node, int>>();
while(stack.Count>0 || curr.Item1!=null)
{
if (curr.Item1 != null)//Case 1
{
stack.Push(curr);
Node leftChild = curr.Item1.GetEdge(curr.Item2);//move to leftmost unvisited child
curr = new Tuple<Node, int>(leftChild, 0);
}
else//Case 2
{
curr = stack.Pop();
Node currNode=curr.Item1;
//because for every node, it can possibly have more edges than key
//if the current index corresponds to a key, we want to add the key into the list.
//else we just want to traverse it's edges.
if (curr.Item2 < currNode.Keys.Count)
{
items.Add(currNode.Keys[curr.Item2]);
curr = new Tuple<Node, int>(currNode, curr.Item2 + 1);
}
else
{
Node rightChild = currNode.GetEdge(curr.Item2 + 1);//get the rightmost child, may be null
//if right most child is null, we will visit 'Case 2' again in the next loop,
//and the parent will be popped off the stack
curr = new Tuple<Node, int>(rightChild, curr.Item2 + 1);
}
}
}
return items.ToArray();
}
public Node Min(Node n=null)
{
if(n==null)
{
n = Root;
}
Node curr=n;
if (curr != null)
{
while (curr.Edges.Count > 0)
{
curr = curr.Edges[0];
}
}
return curr;
}
}
}
Node.cs
********************
NOTE: Since this is a very big assignment, I could complete the implementation only for 2-3-4 tree. Please create a new post for Red black tree and I will try to answer it.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.