Question
In C# Language, create a Splay Tree that does the following:(Include with main program and testing if possible. 1. Insert element 2. Traverse (one traversal) 3. Find (note that in the splay tree "Find" puts the found node at the root)
Explanation / Answer
The code is below: using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; public class Splay_Tree : IDictionary where TKey : IComparable { private Splay_TreeNode root_node; private int Count_Nodes; private int version = 0; public void AddNode(TKey key, TValue value) { this.Set(key, value, throwOnExisting: true); } public void AddNode(KeyValuePair item) { this.Set(item.Key, item.Value, throwOnExisting: true); } private void Set(TKey key, TValue value, bool throwOnExisting) { if (this.Count_Nodes == 0) { this.version++; this.root_node = new Splay_TreeNode(key, value); this.Count_Nodes = 1; return; } this.Splay(key); var c = key.CompareTo(this.root_node.Key); if (c == 0) { if (throwOnExisting) { throw new ArgumentException("An item with the same key already exists in the tree."); } this.version++; this.root_node.Value = value; return; } var n = new Splay_TreeNode(key, value); if (c < 0) { n.LeftDescendent = this.root_node.LeftDescendent; n.RightDescendent = this.root_node; this.root_node.LeftDescendent = null; } else { n.RightDescendent = this.root_node.RightDescendent; n.LeftDescendent = this.root_node; this.root_node.RightDescendent = null; } this.root_node = n; this.Count_Nodes++; this.Splay(key); this.version++; } public void Clear() { this.root_node = null; this.Count_Nodes = 0; this.version++; } public bool Contains_key(TKey key) { if (this.Count_Nodes == 0) { return false; } this.Splay(key); return key.CompareTo(this.root_node.Key) == 0; } public bool Contains(KeyValuePair item) { if (this.Count_Nodes == 0) { return false; } this.Splay(item.Key); return item.Key.CompareTo(this.root_node.Key) == 0 && (object.ReferenceEquals(this.root_node.Value, item.Value) || (!object.ReferenceEquals(item.Value, null) && item.Value.Equals(this.root_node.Value))); } private void Splay(TKey key) { Splay_TreeNode l, r, t, y, header; l = r = header = new Splay_TreeNode(default(TKey), default(TValue)); t = this.root_node; while (true) { var c = key.CompareTo(t.Key); if (c < 0) { if (t.LeftDescendent == null) break; if (key.CompareTo(t.LeftDescendent.Key) < 0) { y = t.LeftDescendent; t.LeftDescendent = y.RightDescendent; y.RightDescendent = t; t = y; if (t.LeftDescendent == null) break; } r.LeftDescendent = t; r = t; t = t.LeftDescendent; } else if (c > 0) { if (t.RightDescendent == null) break; if (key.CompareTo(t.RightDescendent.Key) > 0) { y = t.RightDescendent; t.RightDescendent = y.LeftDescendent; y.LeftDescendent = t; t = y; if (t.RightDescendent == null) break; } l.RightDescendent = t; l = t; t = t.RightDescendent; } else { break; } } l.RightDescendent = t.LeftDescendent; r.LeftDescendent = t.RightDescendent; t.LeftDescendent = header.RightDescendent; t.RightDescendent = header.LeftDescendent; this.root_node = t; } public bool remove_node(TKey key) { if (this.Count_Nodes == 0) { return false; } this.Splay(key); if (key.CompareTo(this.root_node.Key) != 0) { return false; } if (this.root_node.LeftDescendent == null) { this.root_node = this.root_node.RightDescendent; } else { var swap = this.root_node.RightDescendent; this.root_node = this.root_node.LeftDescendent; this.Splay(key); this.root_node.RightDescendent = swap; } this.version++; this.Count_Nodes--; return true; } public bool TryGetValue(TKey key, out TValue value) { if (this.Count_Nodes == 0) { value = default(TValue); return false; } this.Splay(key); if (key.CompareTo(this.root_node.Key) != 0) { value = default(TValue); return false; } value = this.root_node.Value; return true; } public TValue this[TKey key] { get { if (this.Count_Nodes == 0) { throw new KeyNotFoundException("The key was not found in the tree."); } this.Splay(key); if (key.CompareTo(this.root_node.Key) != 0) { throw new KeyNotFoundException("The key was not found in the tree."); } return this.root_node.Value; } set { this.Set(key, value, throwOnExisting: false); } } public int Count_Nodes { get { return this.Count_Nodes; } } public bool IsReadOnly { get { return false; } } public bool remove_node(KeyValuePair item) { if (this.Count_Nodes == 0) { return false; } this.Splay(item.Key); if (item.Key.CompareTo(this.root_node.Key) == 0 && (object.ReferenceEquals(this.root_node.Value, item.Value) || (!object.ReferenceEquals(item.Value, null) && item.Value.Equals(this.root_node.Value)))) { return false; } if (this.root_node.LeftDescendent == null) { this.root_node = this.root_node.RightDescendent; } else { var swap = this.root_node.RightDescendent; this.root_node = this.root_node.LeftDescendent; this.Splay(item.Key); this.root_node.RightDescendent = swap; } this.version++; this.Count_Nodes--; return true; } public void Trim_Tree(int depth) { if (depth < 0) { throw new ArgumentOutOfRangeException("depth", "The Trim_Tree depth must not be negative."); } if (this.Count_Nodes == 0) { return; } if (depth == 0) { this.Clear(); } else { var prevCount_Nodes = this.Count_Nodes; this.Count_Nodes = this.Trim_Tree(this.root_node, depth - 1); if (prevCount_Nodes != this.Count_Nodes) { this.version++; } } } private int Trim_Tree(Splay_TreeNode node, int depth) { if (depth == 0) { node.LeftDescendent = null; node.RightDescendent = null; return 1; } else { int Count_Nodes = 1; if (node.LeftDescendent != null) { Count_Nodes += Trim_Tree(node.LeftDescendent, depth - 1); } if (node.RightDescendent != null) { Count_Nodes += Trim_Tree(node.RightDescendent, depth - 1); } return Count_Nodes; } } public ICollection Keys { get { return new TiedList(this, this.version, this.AsList(node => node.Key)); } } public ICollection Values { get { return new TiedList(this, this.version, this.AsList(node => node.Value)); } } public void CopyTo(KeyValuePair[] array, int arrayIndex) { this.AsList(node => new KeyValuePair(node.Key, node.Value)).CopyTo(array, arrayIndex); } public IEnumerator GetEnumerator() { return new TiedList(this, this.version, this.AsList(node => new KeyValuePair(node.Key, node.Value))).GetEnumerator(); } private IList AsList(Func selector) { if (this.root_node == null) { return new TEnumerator[0]; } var result = new List(this.Count_Nodes); PopulateList(this.root_node, result, selector); return result; } private void PopulateList(Splay_TreeNode node, List list, Func selector) { if (node.LeftDescendent != null) PopulateList(node.LeftDescendent, list, selector); list.AddNode(selector(node)); if (node.RightDescendent != null) PopulateList(node.RightDescendent, list, selector); } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return this.GetEnumerator(); } private sealed class Splay_TreeNode { public readonly TKey Key; public TValue Value; public Splay_TreeNode LeftDescendent; public Splay_TreeNode RightDescendent; public Splay_TreeNode(TKey key, TValue value) { this.Key = key; this.Value = value; } } [DebuggerDisplay("Count_Nodes = {Count_Nodes}")] private sealed class TiedList : IList { private readonly Splay_Tree tree; private readonly int version; private readonly IList backingList; public TiedList(Splay_Tree tree, int version, IList backingList) { if (tree == null) { throw new ArgumentNullException("tree"); } if (backingList == null) { throw new ArgumentNullException("backingList"); } this.tree = tree; this.version = version; this.backingList = backingList; } public int IndexOf(T item) { if (this.tree.version != this.version) throw new InvalidOperationException("The collection has been modified."); return this.backingList.IndexOf(item); } public void Insert_Node(int index, T item) { throw new NotSupportedException(); } public void remove_nodeAt(int index) { throw new NotSupportedException(); } public T this[int index] { get { if (this.tree.version != this.version) throw new InvalidOperationException("The collection has been modified."); return this.backingList[index]; } set { throw new NotSupportedException(); } } public void AddNode(T item) { throw new NotSupportedException(); } public void Clear() { throw new NotSupportedException(); } public bool Contains(T item) { if (this.tree.version != this.version) throw new InvalidOperationException("The collection has been modified."); return this.backingList.Contains(item); } public void CopyTo(T[] array, int arrayIndex) { if (this.tree.version != this.version) throw new InvalidOperationException("The collection has been modified."); this.backingList.CopyTo(array, arrayIndex); } public int Count_Nodes { get { return this.tree.Count_Nodes; } } public bool IsReadOnly { get { return true; } } public bool remove_node(T item) { throw new NotSupportedException(); } public IEnumerator GetEnumerator() { if (this.tree.version != this.version) throw new InvalidOperationException("The collection has been modified."); foreach (var item in this.backingList) { yield return item; if (this.tree.version != this.version) throw new InvalidOperationException("The collection has been modified."); } } IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); } } }