Mercurial > hg > Database > jungle-sharp
view Main/jungle-main/data/treemap/RedNode.cs @ 35:f2ea780b3e80
fix
author | Kazuma Takeda |
---|---|
date | Wed, 22 Feb 2017 16:30:19 +0900 |
parents | 1f99e150f336 |
children |
line wrap: on
line source
using System; using System.Collections; using System.Collections.Generic; public class RedNode<K,V> : TreeMapNode<K,V>{ // Use this for initialization public RedNode (K key, V value, TreeMapNode<K,V> left, TreeMapNode<K,V> right) : base (key, value, left, right) { } // Update is called once per frame public override bool isNotEmpty () { return true; } public override rebuildNode<K,V> deleteNode() { TreeMapNode<K,V> emptyNode = new EmptyNode<K,V>(this.getKey()); return new rebuildNode<K,V>(false, emptyNode); } public override Rotate checkRotate(Rotate side) { if (side == Rotate.L) { if (left.isRed()) return Rotate.R; else if (right.isRed()) return Rotate.LR; return Rotate.N; } else { if (left.isRed()) return Rotate.RL; else if (right.isRed()) return Rotate.L; return Rotate.N; } } public override rebuildNode<K,V> replaceNode(TreeMapNode<K, V> parent, Comparer<K> ctr) { TreeMapNode<K, V> newNode; if (!this.lefts().isNotEmpty() && !this.rights().isNotEmpty()) { //自身を削除する return deleteNode(); } else if (this.lefts().isNotEmpty() && !this.rights().isNotEmpty()) { //左の部分木を昇格させる newNode = lefts().createNode(lefts().getKey(), lefts().getValue(), lefts().lefts(), lefts().rights()); return new rebuildNode<K,V>(false, newNode); } else if (!this.lefts().isNotEmpty() && this.rights().isNotEmpty()) { //右の部分木を昇格させる newNode = rights().createNode(rights().getKey(), rights().getValue(), rights().lefts(), rights().rights()); return new rebuildNode<K,V>(false, newNode); } else {//子ノードが左右にある場合 //左の部分木の最大の値を持つNodeと自身を置き換える TreeMapNode<K, V> cur = this.lefts(); while (cur.rights().isNotEmpty()) { cur = cur.rights(); } if (this.lefts().rights().isNotEmpty()) { rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.lefts().deleteSubTreeMaxNode(null, ctr, Rotate.L); if (leftSubTreeNodeRebuildNode.rebuilds()) { TreeMapNode<K, V> node = leftSubTreeNodeRebuildNode.getNode(); TreeMapNode<K, V> newParent = createNode(cur.getKey(), cur.getValue(), node, this.rights()); return node.deleteBalance(newParent, ctr); } TreeMapNode<K, V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode(); newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.rights()); return new rebuildNode<K,V>(false, newNode); } else { rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.lefts().replaceNode(this, ctr); if (leftSubTreeNodeRebuildNode.rebuilds()) { TreeMapNode<K, V> node = leftSubTreeNodeRebuildNode.getNode(); TreeMapNode<K, V> newParent = createNode(this.lefts().getKey(), this.lefts().getValue(), node, this.rights()); return node.deleteBalance(newParent, ctr); } TreeMapNode<K, V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode(); newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.rights()); return new rebuildNode<K,V>(false, newNode); } } } public override bool isRed() { return true; } public override TreeMapNode<K, V> createNode(K key, V value, TreeMapNode<K, V> left, TreeMapNode<K, V> right) { return new RedNode<K,V>(key, value, left, right); } public override TreeMapNode<K, V> insBalance() { return this; } public override int checkDepth(int count, int minCount) { // test method count++; minCount = lefts().checkDepth(count, minCount); minCount = rights().checkDepth(count, minCount); return minCount; } }