Sorted Dictionary
C# SortedDictionary
C# Sorted Dictionary Reference Source : 출처 MicroSoft
SortedDictionary의 기본 자료구조 멤버
private TreeSet<KeyValuePair<TKey, TValue>> _set;
TreeSet이란 자료구조를 사용한다.
TreeSet?
internal class TreeSet<T> : SortedSet<T> {
public TreeSet()
: base() { }
public TreeSet(IComparer<T> comparer) : base(comparer) { }
public TreeSet(ICollection<T> collection) : base(collection) { }
public TreeSet(ICollection<T> collection, IComparer<T> comparer) : base(collection, comparer) { }
#if !FEATURE_NETCORE
public TreeSet(SerializationInfo siInfo, StreamingContext context) : base(siInfo, context) { }
#endif
internal override bool AddIfNotPresent(T item) {
bool ret = base.AddIfNotPresent(item);
if (!ret) {
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
}
return ret;
}
}
SortedSet을 상속받아 사용한다.
SortedSet?
SortedSet은 Red-Black-Tree 균형이진트리 자료구조를 사용한다.
Add
internal virtual bool AddIfNotPresent(T item) {
if (root == null) { // empty tree
root = new Node(item, false);
count = 1;
version++;
return true;
}
//
// Search for a node at bottom to insert the new node.
// If we can guanratee the node we found is not a 4-node, it would be easy to do insertion.
// We split 4-nodes along the search path.
//
Node current = root;
Node parent = null;
Node grandParent = null;
Node greatGrandParent = null;
//even if we don't actually add to the set, we may be altering its structure (by doing rotations
//and such). so update version to disable any enumerators/subsets working on it
version++;
int order = 0;
while (current != null) {
order = comparer.Compare(item, current.Item);
if (order == 0) {
// We could have changed root node to red during the search process.
// We need to set it to black before we return.
root.IsRed = false;
return false;
}
// split a 4-node into two 2-nodes
if (Is4Node(current)) {
Split4Node(current);
// We could have introduced two consecutive red nodes after split. Fix that by rotation.
if (IsRed(parent)) {
InsertionBalance(current, ref parent, grandParent, greatGrandParent);
}
}
greatGrandParent = grandParent;
grandParent = parent;
parent = current;
current = (order < 0) ? current.Left : current.Right;
}
Debug.Assert(parent != null, "Parent node cannot be null here!");
// ready to insert the new node
Node node = new Node(item);
if (order > 0) {
parent.Right = node;
} else {
parent.Left = node;
}
// the new node will be red, so we will need to adjust the colors if parent node is also red
if (parent.IsRed) {
InsertionBalance(node, ref parent, grandParent, greatGrandParent);
}
// Root node is always black
root.IsRed = false;
++count;
return true;
}
레드블랙트리의 규칙
- 루트는 블랙이다.
- 모든 리프(NIL)는 블랙이다.
- 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.
- 로트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.
add 함수에서 레드블랙트리의 규칙을 적용하는 InsertionBalance라는 함수를 통해 트리를 재구성 한다.
Remove
internal virtual bool DoRemove(T item) {
if (root == null) {
return false;
}
// Search for a node and then find its succesor.
// Then copy the item from the succesor to the matching node and delete the successor.
// If a node doesn't have a successor, we can replace it with its left child (if not empty.)
// or delete the matching node.
//
// In top-down implementation, it is important to make sure the node to be deleted is not a 2-node.
// Following code will make sure the node on the path is not a 2 Node.
//even if we don't actually remove from the set, we may be altering its structure (by doing rotations
//and such). so update version to disable any enumerators/subsets working on it
version++;
Node current = root;
Node parent = null;
Node grandParent = null;
Node match = null;
Node parentOfMatch = null;
bool foundMatch = false;
while (current != null) {
if (Is2Node(current)) { // fix up 2-Node
if (parent == null) { // current is root. Mark it as red
current.IsRed = true;
} else {
Node sibling = GetSibling(current, parent);
if (sibling.IsRed) {
// If parent is a 3-node, flip the orientation of the red link.
// We can acheive this by a single rotation
// This case is converted to one of other cased below.
Debug.Assert(!parent.IsRed, "parent must be a black node!");
if (parent.Right == sibling) {
RotateLeft(parent);
} else {
RotateRight(parent);
}
parent.IsRed = true;
sibling.IsRed = false; // parent's color
// sibling becomes child of grandParent or root after rotation. Update link from grandParent or root
ReplaceChildOfNodeOrRoot(grandParent, parent, sibling);
// sibling will become grandParent of current node
grandParent = sibling;
if (parent == match) {
parentOfMatch = sibling;
}
// update sibling, this is necessary for following processing
sibling = (parent.Left == current) ? parent.Right : parent.Left;
}
Debug.Assert(sibling != null || sibling.IsRed == false, "sibling must not be null and it must be black!");
if (Is2Node(sibling)) {
Merge2Nodes(parent, current, sibling);
} else {
// current is a 2-node and sibling is either a 3-node or a 4-node.
// We can change the color of current to red by some rotation.
TreeRotation rotation = RotationNeeded(parent, current, sibling);
Node newGrandParent = null;
switch (rotation) {
case TreeRotation.RightRotation:
Debug.Assert(parent.Left == sibling, "sibling must be left child of parent!");
Debug.Assert(sibling.Left.IsRed, "Left child of sibling must be red!");
sibling.Left.IsRed = false;
newGrandParent = RotateRight(parent);
break;
case TreeRotation.LeftRotation:
Debug.Assert(parent.Right == sibling, "sibling must be left child of parent!");
Debug.Assert(sibling.Right.IsRed, "Right child of sibling must be red!");
sibling.Right.IsRed = false;
newGrandParent = RotateLeft(parent);
break;
case TreeRotation.RightLeftRotation:
Debug.Assert(parent.Right == sibling, "sibling must be left child of parent!");
Debug.Assert(sibling.Left.IsRed, "Left child of sibling must be red!");
newGrandParent = RotateRightLeft(parent);
break;
case TreeRotation.LeftRightRotation:
Debug.Assert(parent.Left == sibling, "sibling must be left child of parent!");
Debug.Assert(sibling.Right.IsRed, "Right child of sibling must be red!");
newGrandParent = RotateLeftRight(parent);
break;
}
newGrandParent.IsRed = parent.IsRed;
parent.IsRed = false;
current.IsRed = true;
ReplaceChildOfNodeOrRoot(grandParent, parent, newGrandParent);
if (parent == match) {
parentOfMatch = newGrandParent;
}
grandParent = newGrandParent;
}
}
}
// we don't need to compare any more once we found the match
int order = foundMatch ? -1 : comparer.Compare(item, current.Item);
if (order == 0) {
// save the matching node
foundMatch = true;
match = current;
parentOfMatch = parent;
}
grandParent = parent;
parent = current;
if (order < 0) {
current = current.Left;
} else {
current = current.Right; // continue the search in right sub tree after we find a match
}
}
// move successor to the matching node position and replace links
if (match != null) {
ReplaceNode(match, parentOfMatch, parent, grandParent);
--count;
}
if (root != null) {
root.IsRed = false;
}
return foundMatch;
}
Remove에서도 규칙에 따라 삭제 후 ReplaceChildOfNodeOrRoot함수를 통해 트리 재구성을 진행함
Find
internal virtual Node FindNode(T item) {
Node current = root;
while (current != null) {
int order = comparer.Compare(item, current.Item);
if (order == 0) {
return current;
} else {
current = (order < 0) ? current.Left : current.Right;
}
}
return null;
}