using System;
|
using System.Collections.Generic;
|
using System.Text;
|
|
namespace QiHe.CodeLib
|
{
|
public class BinarySearchTreeBase<TItem, TTreeNode>
|
where TItem : IComparable<TItem>
|
where TTreeNode : BinaryTreeNodeBase<TItem, TTreeNode>, new()
|
{
|
public TTreeNode Root;
|
|
private int count;
|
|
public BinarySearchTreeBase()
|
{
|
Root = Nil;
|
}
|
|
public virtual TTreeNode Nil
|
{
|
get { return null; }
|
}
|
|
/// <summary>
|
/// The number of nodes contained in the tree.
|
/// </summary>
|
public int Size
|
{
|
get { return count; }
|
}
|
|
public IEnumerable<TItem> InorderTreeWalk()
|
{
|
foreach (TTreeNode node in InorderTreeWalk(Root))
|
{
|
yield return node.Data;
|
}
|
}
|
|
public bool Contains(TItem item)
|
{
|
return Search(Root, item) != Nil;
|
}
|
|
public TTreeNode Find(TItem item)
|
{
|
return Search(Root, item);
|
}
|
|
public void Add(TItem item)
|
{
|
TTreeNode node = new TTreeNode();
|
node.Data = item;
|
Insert(node);
|
}
|
|
public void Remove(TItem item)
|
{
|
TTreeNode node = Search(Root, item);
|
if (node != Nil)
|
{
|
Delete(node);
|
}
|
}
|
|
public void Clear()
|
{
|
Root = Nil;
|
count = 0;
|
}
|
|
public IEnumerable<TTreeNode> InorderTreeWalk(TTreeNode node)
|
{
|
if (node != Nil)
|
{
|
foreach (TTreeNode subnode in InorderTreeWalk(node.Left))
|
{
|
yield return subnode;
|
}
|
yield return node;
|
|
foreach (TTreeNode subnode in InorderTreeWalk(node.Right))
|
{
|
yield return subnode;
|
}
|
}
|
}
|
|
public TTreeNode Search(TTreeNode node, TItem item)
|
{
|
if (node == Nil || node.Data.CompareTo(item) == 0)
|
{
|
return node;
|
}
|
if (item.CompareTo(node.Data) < 0)
|
{
|
return Search(node.Left, item);
|
}
|
else
|
{
|
return Search(node.Right, item);
|
}
|
}
|
|
public TTreeNode Minimum(TTreeNode node)
|
{
|
if (node == Nil) return Nil;
|
TTreeNode left = node;
|
while (left.Left != Nil)
|
{
|
left = left.Left;
|
}
|
return left;
|
}
|
|
public TTreeNode Maximum(TTreeNode node)
|
{
|
if (node == Nil) return Nil;
|
TTreeNode right = node;
|
while (right.Right != Nil)
|
{
|
right = right.Right;
|
}
|
return right;
|
}
|
|
protected TTreeNode Successor(TTreeNode node)
|
{
|
if (node.Right != Nil)
|
{
|
return Minimum(node.Right);
|
}
|
TTreeNode parent = node.Parent;
|
while (parent != Nil && node == parent.Right)
|
{
|
node = parent;
|
parent = parent.Parent;
|
}
|
return parent;
|
}
|
|
protected TTreeNode Predecessor(TTreeNode node)
|
{
|
if (node.Left != Nil)
|
{
|
return Maximum(node.Left);
|
}
|
TTreeNode parent = node.Parent;
|
while (parent != Nil && node == parent.Left)
|
{
|
node = parent;
|
parent = parent.Parent;
|
}
|
return parent;
|
}
|
|
///<summary>
|
/// Rebalance the tree by rotating the nodes to the left.
|
///</summary>
|
protected void RotateLeft(TTreeNode x)
|
{
|
// pushing node x down and to the Left to balance the tree. x's Right child (y)
|
// replaces x (since y > x), and y's Left child becomes x's Right child
|
// (since it's < y but > x).
|
|
TTreeNode y = x.Right;
|
|
// Turn y's left subtree into x's right subtree
|
x.Right = y.Left;
|
|
// modify parents
|
if (y.Left != Nil)
|
{
|
y.Left.Parent = x;
|
}
|
if (y != Nil)
|
{
|
y.Parent = x.Parent;
|
}
|
|
if (x.Parent != Nil)
|
{
|
// determine which side of it's Parent x was on
|
if (x.IsLeftChild)
|
{
|
x.Parent.Left = y;
|
}
|
else
|
{
|
x.Parent.Right = y;
|
}
|
}
|
else
|
{
|
// at rbTree, set it to y
|
Root = y;
|
}
|
|
// link x and y
|
// put x on y's Left
|
y.Left = x;
|
if (x != Nil)
|
{
|
x.Parent = y;
|
}
|
}
|
|
///<summary>
|
/// Rebalance the tree by rotating the nodes to the right.
|
///</summary>
|
protected void RotateRight(TTreeNode x)
|
{
|
// pushing node x down and to the Right to balance the tree. x's Left child (y)
|
// replaces x (since x < y), and y's Right child becomes x's Left child
|
// (since it's < x but > y).
|
|
// get x's Left node, this becomes y
|
TTreeNode y = x.Left;
|
|
// y's Right child becomes x's Left child
|
x.Left = y.Right;
|
|
// modify parents
|
if (y.Right != Nil)
|
{
|
y.Right.Parent = x;
|
}
|
|
if (y != Nil)
|
{
|
y.Parent = x.Parent;
|
}
|
|
// Nil=rbTree, could also have used rbTree
|
if (x.Parent != Nil)
|
{
|
// determine which side of it's Parent x was on
|
if (x.IsRightChild)
|
{
|
x.Parent.Right = y;
|
}
|
else
|
{
|
x.Parent.Left = y;
|
}
|
}
|
else
|
{
|
// at rbTree, set it to y
|
Root = y;
|
}
|
|
// link x and y
|
// put x on y's Right
|
y.Right = x;
|
if (x != Nil)
|
{
|
x.Parent = y;
|
}
|
}
|
|
public virtual void Insert(TTreeNode node)
|
{
|
TTreeNode parent = Nil;
|
TTreeNode current = Root;
|
|
while (current != Nil)
|
{
|
parent = current;
|
|
if (node.Data.CompareTo(current.Data) < 0)
|
{
|
current = current.Left;
|
}
|
else
|
{
|
current = current.Right;
|
}
|
}
|
|
node.Parent = parent;
|
|
if (parent == Nil)
|
{
|
Root = node;
|
}
|
else
|
{
|
if (node.Data.CompareTo(parent.Data) < 0)
|
{
|
parent.Left = node;
|
}
|
else
|
{
|
parent.Right = node;
|
}
|
}
|
count++;
|
}
|
|
public virtual TTreeNode Delete(TTreeNode node)
|
{
|
TTreeNode tobeDeleted;
|
if (node.Left == Nil || node.Right == Nil)
|
{
|
tobeDeleted = node;
|
}
|
else
|
{
|
tobeDeleted = Successor(node);
|
}
|
|
TTreeNode childNode;
|
if (tobeDeleted.Left != Nil)
|
{
|
childNode = tobeDeleted.Left;
|
}
|
else
|
{
|
childNode = tobeDeleted.Right;
|
}
|
|
if (childNode != Nil)
|
{
|
childNode.Parent = tobeDeleted.Parent;
|
}
|
|
TTreeNode parent = tobeDeleted.Parent;
|
if (parent == Nil)
|
{
|
Root = childNode;
|
}
|
else
|
{
|
if (tobeDeleted.IsLeftChild)
|
{
|
parent.Left = childNode;
|
}
|
else
|
{
|
parent.Right = childNode;
|
}
|
}
|
|
if (tobeDeleted != node)
|
{
|
node.Data = tobeDeleted.Data;
|
}
|
count--;
|
return tobeDeleted;
|
}
|
}
|
}
|
