A brief discussion on the collection summary and analysis of binary search tree
- 2020-05-12 03:02:45
- OfStack
We all know Dictionary
<
TKey, TValue
>
Finding elements is very fast, and it works by hashing your TKey values to the specified location in the array, storing the TValue values in the corresponding location,
Since the same algorithm is used for fetching and saving, it is easy to locate the location of TValue, and the time spent is basically the time to realize the hash algorithm, which has no relation to the number of elements, so the time complexity of the value is O(1).
The collection is nothing more than an array based on the most basic syntax []. If you want to allocate and then add elements to it, you can create an array with twice the capacity if you don't have enough capacity. Assign the previous elements and recycle the previous array.
But set based on hash algorithm that is a little different, every time he is not to create a 2 times the capacity of the array, in order to make homogeneous distribution of elements to the array, the array is the capacity of the such a growth: 3,7,11,17,23,29,37,47,59,71,89,107,131,163,197,239,293,353,431,521,631,761,919,1103...
It grows as a prime number. Because the size of the array is small at a time, adding many elements to it without the programmer pre-allocating memory can result in multiple array creation, replication, and reclamation.
1 want to be a useful things out, let the people who want to use, can let oneself headphones again, so this made one based on 2 set of fork search trees, we know that in the 2 forks search trees query elements of the optimal time complexity is O (logN) or in the case of a full two forks tree, is the worst time complexity O (n) in addition to the leaf node each node only one child,
It's also very fast to find elements, and it's only doing Int comparisons, Dictionary < TKey, TValue > It is based on a hash algorithm. Of course, the set of search tree based on 2 inserts also has its own disadvantages:
1: the element must implement the interface IBinaryTree, and its attribute CompareValue is mainly used for comparison to generate a two-fork lookup tree
2: elements must be new enabled, that is, base types int, char, string, etc are not supported
3: each node has about two child nodes, which only act as Pointers to the child nodes of the node, and only need to occupy a small amount of extra memory
4: it is basically based on recursive implementation. If there are too many elements, the stack will overflow
The advantage is commonly used 1 some function have, the function is as follows, practice a hand, but can 1 straight optimization go down
Since the same algorithm is used for fetching and saving, it is easy to locate the location of TValue, and the time spent is basically the time to realize the hash algorithm, which has no relation to the number of elements, so the time complexity of the value is O(1).
The collection is nothing more than an array based on the most basic syntax []. If you want to allocate and then add elements to it, you can create an array with twice the capacity if you don't have enough capacity. Assign the previous elements and recycle the previous array.
But set based on hash algorithm that is a little different, every time he is not to create a 2 times the capacity of the array, in order to make homogeneous distribution of elements to the array, the array is the capacity of the such a growth: 3,7,11,17,23,29,37,47,59,71,89,107,131,163,197,239,293,353,431,521,631,761,919,1103...
It grows as a prime number. Because the size of the array is small at a time, adding many elements to it without the programmer pre-allocating memory can result in multiple array creation, replication, and reclamation.
1 want to be a useful things out, let the people who want to use, can let oneself headphones again, so this made one based on 2 set of fork search trees, we know that in the 2 forks search trees query elements of the optimal time complexity is O (logN) or in the case of a full two forks tree, is the worst time complexity O (n) in addition to the leaf node each node only one child,
It's also very fast to find elements, and it's only doing Int comparisons, Dictionary < TKey, TValue > It is based on a hash algorithm. Of course, the set of search tree based on 2 inserts also has its own disadvantages:
1: the element must implement the interface IBinaryTree, and its attribute CompareValue is mainly used for comparison to generate a two-fork lookup tree
2: elements must be new enabled, that is, base types int, char, string, etc are not supported
3: each node has about two child nodes, which only act as Pointers to the child nodes of the node, and only need to occupy a small amount of extra memory
4: it is basically based on recursive implementation. If there are too many elements, the stack will overflow
The advantage is commonly used 1 some function have, the function is as follows, practice a hand, but can 1 straight optimization go down
public class BinaryTree<T> : IDisposable, IEnumerable<T>, IEnumerable where T :IBinaryTree, new()
{
public BinaryTree();
public BinaryTree(IEnumerable<T> list);// will 1 Number fabric 2 Insert search trees
public BinaryTree(T root); // Specify the following node
public int Count { get; }// Number of elements
public T this[IBinaryTree iBinaryTree] { get; }// The array index accesses the element directly
public void Add(T t);// Add elements
public void Clear();// Clear all elements
public bool Contains(T iBinaryTree);// Contains a custom element
public void Dispose();// Release resources, support using
public T Find(IBinaryTree iBinaryTree);// Look for the element
public T Find(IBinaryTree iBinaryTree, TreeNode<T> node);// Finds the element under the specified node
public T FindMax();// The largest element
public T FindMin();// The smallest element
public T FindMin(TreeNode<T> node);// Finds the smallest element under the specified node
public IEnumerator<T> GetEnumerator();// Returns all elements supported foreach
public TreeNode<T> Remove(T t);// Remove elements
public TreeNode<T> Remove(IBinaryTree iBinaryTree, TreeNode<T> node);// Deletes an element under the specified node
public IEnumerable<T> Sort();// Sort (ascending)
public IEnumerable<T> ToList();// Return all elements
}
The source code
namespace Utils
{
/// <summary>
/// 2 Quadtree interface
/// </summary>
public interface IBinaryTree
{
/// <summary>
/// Value used for comparison
/// </summary>
int CompareValue
{
get;
set;
}
}
public class TreeNode<T> where T : IBinaryTree, new()
{
public TreeNode<T> Left
{
get;
set;
}
public TreeNode<T> Right
{
set;
get;
}
public T Data
{
get;
set;
}
public TreeNode(T t)
{
this.Data = t;
}
public TreeNode()
: this(default(T))
{
}
}
/// <summary>
/// 2 Insert search trees
/// </summary>
public class BinaryTree<T> : IDisposable,IEnumerable<T> where T : IBinaryTree, new()
{
public BinaryTree()
{
}
public BinaryTree(T root)
{
if (root == null)
{
throw new NullReferenceException("Parameter is null");
}
Add(root);
}
public BinaryTree(IEnumerable<T> list)
{
if (list == null)
{
throw new NullReferenceException("Parameter is null");
}
foreach (var item in list)
{
Add(item);
}
}
// The root node
private TreeNode<T> root;
// Add a node (without checking if the root node is empty, set to private )
private void Add(T t, TreeNode<T> root)
{
if (t == null)
{
return;
}
if (t.CompareValue < root.Data.CompareValue)
{
if (root.Left == null)
{
root.Left = new TreeNode<T>(t);
++Count;
}
else
{
Add(t, root.Left);
}
}
else if (t.CompareValue > root.Data.CompareValue)
{
if (root.Right == null)
{
root.Right = new TreeNode<T>(t);
++Count;
}
else
{
Add(t, root.Right);
}
}
else
{
root.Data = t;
}
}
// Add a node
public void Add(T t)
{
if (t == null)
{
return;
}
if (this.root == null)
{
this.root = new TreeNode<T>(t);
++Count;
}
else
{
Add(t, this.root);
}
}
// Finds the smallest node under the specified node
public T FindMin(TreeNode<T> node)
{
if (node == null)
{
return default(T);
}
if (node.Left == null)
{
return node.Data;
}
else
{
return FindMin(node.Left);
}
}
// Find the minimum node
public T FindMin()
{
return FindMin(this.root);
}
// Find the maximum node
private T FindMax(TreeNode<T> node)
{
if (node.Right == null)
{
return node.Data;
}
else
{
return FindMax(node.Right);
}
}
// Find the maximum node
public T FindMax()
{
return FindMax(this.root);
}
// Deletes a node under the specified node
public TreeNode<T> Remove(IBinaryTree iBinaryTree, TreeNode<T> node)
{
if (node == null)
{
return null;
}
if (iBinaryTree == null)
{
return node;
}
if (iBinaryTree.CompareValue < node.Data.CompareValue)
{
node.Left = Remove(iBinaryTree, node.Left);
}
else if (iBinaryTree.CompareValue > node.Data.CompareValue)
{
node.Right = Remove(iBinaryTree, node.Right);
}
else
{
if (node.Left != null && node.Right != null)
{
T tmpNode = FindMin(node.Right);// Find the smallest node with a subtree for the current node
node.Data.CompareValue = tmpNode.CompareValue;// Replaces the current node to be deleted with the smallest node of the right subtree
node.Right = Remove(tmpNode, node.Right);// Here is the highlight, which deletes the smallest node of the right subtree of the current node
}
else
{
if (node.Left == null)
{
node = node.Right;
}
else if (node.Right == null)
{
node = node.Left;
}
else
{
node = null;
}
if (this.root.Data.CompareValue == iBinaryTree.CompareValue)// Processing root node
{
this.root = node;
}
}
--Count;
}
return node;
}
// Remove nodes
public TreeNode<T> Remove(T t)
{
if (this.root == null || t==null)
{
return null;
}
return Remove(t, this.root);
}
// Find nodes
public T Find(IBinaryTree iBinaryTree, TreeNode<T> node)
{
if (node == null || iBinaryTree == null)
{
return default(T);
}
if (iBinaryTree.CompareValue < node.Data.CompareValue)
{
return Find(iBinaryTree, node.Left);
}
else if (iBinaryTree.CompareValue > node.Data.CompareValue)
{
return Find(iBinaryTree, node.Right);
}
return node.Data;
}
// Find nodes
public T Find(IBinaryTree iBinaryTree)
{
return Find(iBinaryTree, this.root);
}
// Contains the specified element
private bool Contains(IBinaryTree iBinaryTree, TreeNode<T> node)
{
if (node == null || iBinaryTree == null)
{
return false; ;
}
if (iBinaryTree.CompareValue < node.Data.CompareValue)
{
return Contains(iBinaryTree, node.Left);
}
else if (iBinaryTree.CompareValue > node.Data.CompareValue)
{
return Contains(iBinaryTree, node.Right);
}
return iBinaryTree.Equals(node.Data);
}
// Contains the specified element
public bool Contains(T iBinaryTree)
{
return Contains(iBinaryTree, this.root);
}
// Clear all nodes
public void Clear()
{
while (this.Count > 0)
{
Remove(this.root.Data);
}
this.root = new TreeNode<T>();
}
// Release resources
public void Dispose()
{
while (this.Count > 0)
{
Remove(this.root.Data);
}
this.root = null;
}
// Number of nodes
public int Count
{
private set;
get;
}
// Convert to set
public IEnumerable<T> ToList()
{
IList<T> list = new List<T>(Count);
LCR(this.root,list);
return list;
}
// The previous sequential traversal method of adding nodes to a collection is implemented recursively, and stack overflow may occur if there are many elements
private void LCR(TreeNode<T> node, IList<T> list)
{
if (node == null)
{
return;
}
if (node.Left != null)
{
LCR(node.Left, list);
}
list.Add(node.Data);// Add elements
if (node.Right != null)
{
LCR(node.Right, list);
}
}
// The sorting
public IEnumerable<T> Sort()
{
return ToList();
}
// return 1 Two loops access the enumerator of the collection
public IEnumerator<T> GetEnumerator()
{
return this.ToList().GetEnumerator();
}
// return 1 Two loops access the enumerator of the collection
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
public T this[IBinaryTree iBinaryTree]
{
get {
return this.Find(iBinaryTree);
}
}
}
public class Node : IBinaryTree
{
/// <summary>
/// Value used for comparison
/// </summary>
public int CompareValue
{
get;
set;
}
public string Name
{
get;
set;
}
public override string ToString()
{
return string.Format("CompareValue:{0},Name:{1}", this.CompareValue, this.Name);
}
}
}