using System.Collections.Generic;
namespace LearnAL.DataStructs.Generic
{
public class BST<TKey, TValue>
{
private Node _root;
private class Node
{
public TKey key;
public TValue value;
public Node left;
public Node right;
public int size;
public Node()
{
}
public Node(TKey key, TValue value, Node left, Node right, int size)
{
this.key = key;
this.value = value;
this.left = left;
this.right = right;
this.size = size;
}
}
private IComparer<TKey> _cmper;
public BST() : this(null) { }
public BST(IComparer<TKey> cmer)
{
_cmper = cmer == null ? Comparer<TKey>.Default : cmer;
}
public void DeleteMin()
{
DeleteMin(ref _root);
}
private void DeleteMin(ref Node node)
{
if (node == null)
{
return;
}
if (node.left != null)
{
DeleteMin(ref node.left);
}
else
{
node = node.right;
}
if(node != null){
node.size = Size(node.left) + 1 + Size(node.right);
}
}
public void DeleteMax()
{
DeleteMax(ref _root);
}
private void DeleteMax(ref Node node)
{
if (node == null)
{
return;
}
else if (node.right == null)
{
node = node.left;
}
else
{
DeleteMax(ref node.right);
}
if(node != null){
node.size = Size(node.left) + 1 + Size(node.right);
}
}
public void Delete(TKey key)
{
Delete(ref _root, key);
}
private void Delete(ref Node node, TKey key)
{
if (node == null)
{
return;
}
else
{
var cmp = _cmper.Compare(key, node.key);
if (cmp == 0)
{
Delete(ref node);
}
else if (cmp > 0)
{
Delete(ref node.right, key);
}
else
{
Delete(ref node.left, key);
}
if (node != null)
{
node.size = Size(node.left) + 1 + Size(node.right);
}
}
}
private void Delete(ref Node node)
{
if (node == null)
{
return;
}
else
{
if (node.left == null) { node = node.right; }
else if (node.right == null) { node = node.left; }
else
{
//node 指向右子树的最小结点
//移除右子树的最小结点
var min = Min(node).node;
DeleteMin(ref node);
if (min != null)
{
min.left = node.left;
min.right = node.right;
}
node = min;
}
if (node != null)
{
node.size = Size(node.left) + 1 + Size(node.right);
}
}
}
public (bool ok, TKey key) Select(int k)
{
return Select(_root, k);
}
private (bool ok, TKey key) Select(Node node, int k)
{
if (node == null)
{
return (false, default);
}
else
{
var leftSize = Size(node.left);
if (leftSize == k)
{
return (true, node.key);
}
else if (leftSize > k)
{
return Select(node.left, k);
}
else
{
return Select(node.right, k - leftSize - 1);
}
}
}
public (bool ok, int k) Rank(TKey key)
{
return Rank(_root, key);
}
private (bool ok, int k) Rank(Node node, TKey key)
{
if (node == null)
{
return (false, default);
}
else
{
var cmpRes = _cmper.Compare(key, node.key);
if (cmpRes == 0)
{
return (true, Size(node.left));
}
else if (cmpRes < 0)
{
return Rank(node.left, key);
}
else
{
var rankInRight = Rank(node.right, key);
return (true, Size(node.left) + 1 + rankInRight.k);
}
}
}
public (bool ok, TKey key) Celing(TKey key)
{
return Celing(_root, key);
}
private (bool ok, TKey key) Celing(Node x, TKey key)
{
if (x == null)
{
return (false, default);
}
else
{
var cmpRes = _cmper.Compare(key, x.key);
if (cmpRes == 0)
{
return (true, x.key);
}
else if (cmpRes < 0)
{
var res = Celing(x.left, key);
return res.ok == true ? res : (true, x.key);
}
else
{
return Celing(x.right, key);
}
}
}
public (bool ok, TKey key) Floor(TKey key)
{
return Floor(_root, key);
}
private (bool ok, TKey key) Floor(Node x, TKey key)
{
if (x == null)
{
return (false, default);
}
else
{
var cmpRes = _cmper.Compare(key, x.key);
if (cmpRes == 0)
{
return (true, x.key);
}
else if (cmpRes < 0)
{
return Floor(x.left, key);
}
else
{
var res = Floor(x.right, key);
return res.ok == true ? res : (true, x.key);
}
}
}
public (bool, TValue) Get(TKey key)
{
return Get(_root, key);
}
private (bool, TValue) Get(Node node, TKey key)
{
if (node == null)
{
return (false, default);
}
else if (_cmper.Compare(key, node.key) == 0)
{
return (true, node.value);
}
else if (_cmper.Compare(key, node.key) > 0)
{
return Get(node.right, key);
}
else
{
return Get(node.left, key);
}
}
public void Put(TKey key, TValue value)
{
Put(ref _root, key, value);
}
private void Put(ref Node x, TKey key, TValue value)
{
if (x == null)
{
x = new Node();
x.key = key;
x.value = value;
x.size = 1;
}
else
{
var cmpResult = _cmper.Compare(key, x.key);
if (cmpResult == 0)
{
x.value = value;
}
else if (cmpResult > 0)
{
Put(ref x.right, key, value);
}
else
{
Put(ref x.left, key, value);
}
}
x.size = Size(x) + Size(x.left) + Size(x.right);
}
private int Size(Node x)
{
return x == null ? 0 : x.size;
}
public (bool ok, TKey key) Min()
{
var res = Min(_root);
return res.ok ? (true, res.node.key) : (false, default);
}
private (bool ok, Node node) Min(Node x)
{
if (x == null)
{
return (false, default);
}
else if (x.left == null)
{
return (true, x);
}
else
{
return Min(x.left);
}
}
public (bool ok, TKey key) Max()
{
return Max(_root);
}
private (bool ok, TKey key) Max(Node x)
{
if (x == null)
{
return (false, default);
}
else if (x.right == null)
{
return (true, x.key);
}
else
{
return Max(x.right);
}
}
}
}
网友评论