Mercurial > hg > Members > tatsuki > TreeMap
view src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java @ 13:b6739b88edeb
create Tuple<Node,rebuildFlag>
author | tatsuki |
---|---|
date | Sat, 18 Apr 2015 12:01:41 +0900 |
parents | ef442c796b20 |
children | ab026848665a |
line wrap: on
line source
package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap; import static jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.Rotate.*; /** * Created by e115731 on 15/03/25. */ 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<K, V>(key, value, left, right); } @Override protected Node<K, V> insBalance() { return this; } @Override protected Tuple deleteNode() { EmptyNode emptyNode = new EmptyNode(this.getKey()); return new Tuple(emptyNode, false); } @Override Rotate checkRotate(Rotate side) { if (side == L) { if (left.isRed()) return R; else if (right.isRed()) return LR; return N; } else { if (left.isRed()) return RL; else if (right.isRed()) return L; return N; } } @Override boolean isRed() { return true; } @Override public Tuple replaceNode(Node<K, V> parent) { Node<K, V> newNode = null; 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 new Tuple(newNode,false); } else if (!this.left().isNotEmpty() && this.right().isNotEmpty()) { //右の部分木を昇格させる newNode = right().createNode(right().getKey(), right().getValue(), right().left(), right().right()); return new Tuple(newNode,false); } else {//子ノードが左右にある場合 //左の部分木の最大の値を持つNodeと自身を置き換える Node<K, V> cur = this.left(); while (cur.right().isNotEmpty()) { cur = cur.right(); } Tuple leftSubTreeNode = null; if (this.left().right().isNotEmpty()) { leftSubTreeNode = this.left().deleteSubTreeMaxNode(null); newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode.getNode(), this.right()); return leftSubTreeNode.getNode().deleteBalance(newNode,leftSubTreeNode.getRebuildFlag()); } else { leftSubTreeNode = this.left().replaceNode(this); newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode.getNode(), this.right()); return leftSubTreeNode.getNode().deleteBalance(newNode,leftSubTreeNode.getRebuildFlag()); } } } @Override protected int checkBlackCount(int count) { // test method left().checkBlackCount(count); right().checkBlackCount(count); return count; } }