Mercurial > hg > Members > shoshi > jungle > jungle-core
view src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/RedNode.java @ 216:9a410eddbfa4 OptionalTreeMap
delete warning
author | tatsuki |
---|---|
date | Tue, 01 Sep 2015 05:04:38 +0900 |
parents | 1b3661be3119 |
children | 3b31dd5e5a28 |
line wrap: on
line source
package jp.ac.u_ryukyu.ie.cr.jungle.data.treemap; import org.junit.Test; import java.util.Comparator; public class RedNode<K, V> extends Node<K, V> { public RedNode(K key, V value, Node<K, V> left, Node<K, V> right) { super(key, value, left, right); } @Override protected boolean isNotEmpty() { return true; } @Override public Node<K, V> createNode(K key, V value, Node<K, V> left, Node<K, V> right) { return new RedNode<>(key, value, left, right); } @Override protected Node<K, V> insBalance() { return this; } @Override protected Node<K, V> deleteNode() throws RotateParent { return new EmptyNode<>(this.getKey()); } @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; } } @Override boolean isRed() { return true; } @SuppressWarnings("unchecked") @Override public Node<K, V> replaceNode(Node<K, V> parent, Comparator ctr) throws RotateParent { Node<K, V> newNode; if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する return deleteNode(); } else if (this.left().isNotEmpty() && !this.right().isNotEmpty()) { //左の部分木を昇格させる newNode = left().createNode(left().getKey(), left().getValue(), left().left(), left().right()); return newNode; } else if (!this.left().isNotEmpty() && this.right().isNotEmpty()) { //右の部分木を昇格させる newNode = right().createNode(right().getKey(), right().getValue(), right().left(), right().right()); return newNode; } else {//子ノードが左右にある場合 //左の部分木の最大の値を持つNodeと自身を置き換える Node<K, V> cur = this.left(); while (cur.right().isNotEmpty()) { cur = cur.right(); } Node<K, V> leftSubTreeNode; if (this.left().right().isNotEmpty()) { try { leftSubTreeNode = this.left().deleteSubTreeMaxNode(null, ctr, Rotate.L); newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right()); return newNode; } catch (RotateParent e) { leftSubTreeNode = e.getParent(); Node<K, V> newParent = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right()); return leftSubTreeNode.deleteBalance(newParent, ctr); } } else { try { leftSubTreeNode = this.left().replaceNode(this, ctr); newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right()); return newNode; } catch (RotateParent e) { Node<K, V> node = e.getParent(); Node<K, V> newParent = createNode(this.left().getKey(), this.left().getValue(), node, this.right()); return node.deleteBalance(newParent, ctr); } } } } @Override @Test protected int checkDepth(int count, int minCount) { // test method count++; minCount = left().checkDepth(count, minCount); minCount = right().checkDepth(count, minCount); return minCount; } }