Java:二分検索ツリーに基づくMap
ガイド:本文は3つの部分に分かれています.カスタムMapインタフェース Mapの二分探索ツリーは を実現する.コード機能テスト 一.カスタムMapインタフェース
二.Mapの二分探索ツリー実装
三.機能テストコード
public interface Map {
void add(K key, V value);
V remove(K key);
boolean contains(K key);
V get(K key);
void set(K key, V newValue);
int getSize();
boolean isEmpty();
}
二.Mapの二分探索ツリー実装
ublic class BSTMap, V> implements Map {
public class Node {
public K key;
public V value;
public Node left, right;
public Node (K key, V value){
this.key = key;
this.value = value;
left = null;
right = null;
}
}
private Node root;
private int size;
public BSTMap(){
root = null;
size = 0;
}
// (key, value)
@Override
public void add(K key, V value) {
root = add(root, key, value);
}
// node (key, value),
//
private Node add(Node node, K key, V value){
if (node == null){
size++;
return new Node(key, value);
}
if (key.compareTo(node.key) < 0){
node.left = add(node.left, key, value);
}else if (key.compareTo(node.key) > 0){
node.right = add(node.right, key, value);
}else
node.value = value;
return node;
}
// node , key
private Node getNode(Node node, K key){
if (node == null)
return null;
if (key.compareTo(node.key) == 0){
return node;
}
else if (key.compareTo(node.key) > 0){
return getNode(node.right, key);
}
else
return getNode(node.left, key);
}
@Override
public boolean contains(K key) {
return getNode( root, key) == null;
}
@Override
public V get(K key) {
Node node = getNode(root, key);
return node == null?null : node.value;
}
// key
@Override
public void set(K key, V newValue) {
Node node = getNode(root, key);
if (node == null)
throw new IllegalArgumentException(key + " doesn't exist!");
node.value = newValue ;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size==0;
}
// key
@Override
public V remove(K key) {
Node node = getNode(root, key);
if (node != null){
root = remove(root, key);
return node.value;
}
return null;
}
// node key ,
// root
private Node remove(Node node, K key){
if (node == null)
return null;
if (key.compareTo(node.key) < 0) {
node.left = remove(node.left, key);
return node;
}
else if (key.compareTo(node.key) > 0) {
node.right = remove(node.right, key);
return node;
}
else{
//
if (node.left == null){
Node rightNode = node.right;
node.right = null;
size -- ;
return rightNode;
}
//
if (node.right == null){
Node leftNode = node.left;
node.left = null;
size -- ;
return leftNode;
}
//
Node successor = minimum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
}
return node;
}
//
private Node removeMin(Node node){
if (node.left == null){
Node rightNode = node.right;
node.right = null;
size -- ;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
//
private Node minimum(Node node){
if (node.left == null)
return node;
return minimum(node.left);
}
//
public void postOrder(){
postOrder(root);
}
private void postOrder(Node node){
if (node != null){
postOrder(node.left);
postOrder(node.right);
System.out.print(node.key + ": " + node.value);
}
}
}
三.機能テストコード
public static void main(String[] args) {
BSTMap map = new BSTMap<>();
Random random = new Random();
for (int i = 0; i < 20; i++) {
map.add(random.nextInt(10), random.nextInt(10));
}
map.postOrder();
System.out.println();
map.set(1,map.get(8).intValue());
System.out.println(map.remove(2));
map.postOrder();
System.out.println();
System.out.println("size " + map.getSize());
}