0037データ構造のSetとMap
14969 ワード
チェーンテーブルと二分探索ツリーに基づいてSetを実現し,二分探索ツリーに基づいてMapを実現する.
-----------------------------集合Set--------------------------------------
Set
void add
void remove
boolean contains
int getSize()
boolean isEmpty()
1、二分探索木を使用してSet集合を実現する:
package set; import tree.BST; /* * コレクションに格納されている要素を比較可能にするには、E extends Comparable*/public class BSTSetextends Comparable>implements Set{BST bst=new BST<>();@Override public int getSize(){return bst.getSize(); } @Override public boolean isEmpty() { return bst.isEmpty(); } @Override public boolean contains(E e) { return bst.contains(e); }@Override public void add(E e){//自分が実装したBSTクラスのaddメソッドには重複要素が含まれていないため、bst.add(e)を直接呼び出すことができる. } @Override public void remove(E e) { bst.removeElement(e); } @Override public String toString() { return bst.toString(); } }
2、チェーンテーブルを使用して集合Setを実現する:
package set; import linked.LinkedList; /* * チェーンテーブル実装のSetに含まれる要素は、Comparableインタフェース**/public class LinkedListSet implements Set{private LinkedListlinkedList;public LinkedListSet(){linkedList=new LinkedList(); } @Override public int getSize() { return linkedList.getSize(); } @Override public boolean isEmpty() { return linkedList.isEmpty(); } @Override public boolean contains(E e) { return linkedList.contains(e); }@Override public void add(E e){//チェーンテーブルに制限要素がなく重複できないため、ここで判断if(!linkedList.contains(e){//チェーンヘッダーに新しい要素を追加する必要があり、時間複雑度が最も低いlinkedList.addFirst(e); } } @Override public void remove(E e) { linkedList.removeElement(e); } @Override public String toString() { return linkedList.toString(); } }
まとめ:チェーンテーブルによるSet効率は二分探索ツリーによるSetよりも遅い.なぜなら二分探索ツリーによるチェーンテーブルのadd,remove,containsはいずれもO(h)レベルであり、hは二分探索ツリーの高さであり、満二分探索ツリーではh=log 2 nがlogが2をベースnとする対数を表すため、時間複雑度もO(log 2 n)と見なすことができる.2が基数であろうと10が基数であろうと、100が基数であろうと、O(logn)と書くことができるが、最悪の形態の二分探索ツリーは分岐が1つしかない、すなわちチェーンテーブル形式の二分探索ツリーであり、時間の複雑さはO(n)となる.一方,チェーンテーブルによるSet,add(チェーンテーブルのcontainsを呼び出して判断する),remove,containsの時間的複雑度はいずれもO(n)である.
例えば、n=100万の場合、lognは20で、両者は5万倍の差があります.すなわち、lognが1秒であれば、nは14時間かかります.このように見ると、両者の差は非常に大きいようです.nが大きくなるにつれて格差はますます大きくなる.
nlognとn 2の差はlognとnの差に相当する.
lognの効率は非常に高い.
秩序化集合は探索ツリーに基づいて実現することが好ましく、無秩序集合はhashテーブルに基づいて実現することが好ましい(例えば、無秩序集合はチェーンテーブルに基づいて実現効率が極めて低い)
--------------------------------------マッピングMapMapMapMapMapMapMapMapMapMapMapMapMap------------------------------------
チェーンテーブルの実装:
class Node{
K key;
V value;
Node next;
}
二分検索ツリーの実装:
class Node{
K key;
V value;
Node left;
Node right;
}
Mapインタフェース定義:
int getSize()
boolean isEmpty()
Map
void add(K,V)
V remove(K)
boolean contains(K)
V get(K)
void set(K,V)
1、二分探索木に基づいてMapを実現する
-----------------------------集合Set--------------------------------------
Set
void add
void remove
boolean contains
int getSize()
boolean isEmpty()
1、二分探索木を使用してSet集合を実現する:
package set; import tree.BST; /* * コレクションに格納されている要素を比較可能にするには、E extends Comparable*/public class BSTSetextends Comparable>implements Set{BST bst=new BST<>();@Override public int getSize(){return bst.getSize(); } @Override public boolean isEmpty() { return bst.isEmpty(); } @Override public boolean contains(E e) { return bst.contains(e); }@Override public void add(E e){//自分が実装したBSTクラスのaddメソッドには重複要素が含まれていないため、bst.add(e)を直接呼び出すことができる. } @Override public void remove(E e) { bst.removeElement(e); } @Override public String toString() { return bst.toString(); } }
2、チェーンテーブルを使用して集合Setを実現する:
package set; import linked.LinkedList; /* * チェーンテーブル実装のSetに含まれる要素は、Comparableインタフェース**/public class LinkedListSet implements Set{private LinkedListlinkedList;public LinkedListSet(){linkedList=new LinkedList(); } @Override public int getSize() { return linkedList.getSize(); } @Override public boolean isEmpty() { return linkedList.isEmpty(); } @Override public boolean contains(E e) { return linkedList.contains(e); }@Override public void add(E e){//チェーンテーブルに制限要素がなく重複できないため、ここで判断if(!linkedList.contains(e){//チェーンヘッダーに新しい要素を追加する必要があり、時間複雑度が最も低いlinkedList.addFirst(e); } } @Override public void remove(E e) { linkedList.removeElement(e); } @Override public String toString() { return linkedList.toString(); } }
まとめ:チェーンテーブルによるSet効率は二分探索ツリーによるSetよりも遅い.なぜなら二分探索ツリーによるチェーンテーブルのadd,remove,containsはいずれもO(h)レベルであり、hは二分探索ツリーの高さであり、満二分探索ツリーではh=log 2 nがlogが2をベースnとする対数を表すため、時間複雑度もO(log 2 n)と見なすことができる.2が基数であろうと10が基数であろうと、100が基数であろうと、O(logn)と書くことができるが、最悪の形態の二分探索ツリーは分岐が1つしかない、すなわちチェーンテーブル形式の二分探索ツリーであり、時間の複雑さはO(n)となる.一方,チェーンテーブルによるSet,add(チェーンテーブルのcontainsを呼び出して判断する),remove,containsの時間的複雑度はいずれもO(n)である.
例えば、n=100万の場合、lognは20で、両者は5万倍の差があります.すなわち、lognが1秒であれば、nは14時間かかります.このように見ると、両者の差は非常に大きいようです.nが大きくなるにつれて格差はますます大きくなる.
nlognとn 2の差はlognとnの差に相当する.
lognの効率は非常に高い.
秩序化集合は探索ツリーに基づいて実現することが好ましく、無秩序集合はhashテーブルに基づいて実現することが好ましい(例えば、無秩序集合はチェーンテーブルに基づいて実現効率が極めて低い)
--------------------------------------マッピングMapMapMapMapMapMapMapMapMapMapMapMapMap------------------------------------
チェーンテーブルの実装:
class Node{
K key;
V value;
Node next;
}
二分検索ツリーの実装:
class Node{
K key;
V value;
Node left;
Node right;
}
Mapインタフェース定義:
int getSize()
boolean isEmpty()
Map
void add(K,V)
V remove(K)
boolean contains(K)
V get(K)
void set(K,V)
1、二分探索木に基づいてMapを実現する
package map;
public class BSTMapextends Comparable,V> implements Map {
private class Node{
public K key;
public V value;
public Node left;
public Node right;
public Node(K key,V value,Node left,Node right){
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
public Node(K key,V value){
this.key = key;
this.value = value;
this.left = null;
this.right = null;
}
public Node(){
this.key = null;
this.value = null;
this.left = null;
this.right = null;
}
}
private int size;
private Node root;
public BSTMap(){
root = null;
size = 0;
}
@Override
public int getSize() {
// root， node == null
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void add(K k, V v) {
root = add(root,k,v);
}
// ， node node node
private Node add(Node node,K k,V v){
if(k == null){
return null;
}
//1
if(node == null){
//
size++;
return new Node(k,v);
}
//2
if(k.compareTo(node.key) == 0){
//
return node;
}else if(k.compareTo(node.key) < 0){
node.left = add(node.left,k,v);
return node;
}else{
node.right = add(node.right,k,v);
return node;
}
}
@Override
public V remove(K k) {
V v = get(k);
root = remove(root,k);
return v;
}
//
public Node remove(Node node,K k){
//1
if(node == null){
return null;
}
//2
if(k.compareTo(node.key) == 0){
// null，
if(node.right == null){
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}else if(node.left == null){
// null，
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}else{
//
// getMin ，removeMin ， node
Node rightNode = node.right;
Node min = minumum(rightNode);
Node newRightNode = removeMin(rightNode);
min.left = node.left;
min.right = newRightNode;
node.left = node.right = null;
return min;
}
}else if(k.compareTo(node.key) < 0){
node.left = remove(node.left,k);
}else{
node.right = remove(node.right,k);
}
return node;
}
//
private Node minumum(Node node){
//
if(node.left == null){
return node;
}
return minumum(node.left);
}
// node
public Node removeMin(Node node){
//
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
// node.left ，
// node.left = node.left.right
node.left = removeMin(node.left);
return node;
}
@Override
public V get(K k) {
return get(root,k);
}
//
private V get(Node node,K k){
//1
if(node == null || k == null){
return null;
}
//2
if(k.compareTo(node.key) == 0){
//
return node.value;
}else if(k.compareTo(node.key) < 0){
return get(node.left,k);
}else{
return get(node.right,k);
}
}
@Override
public void set(K k, V v) {
root = set(root,k,v);
}
// , node node
public Node set(Node node,K k,V v){
if(k == null){
return null;
}
//1
if(node == null){
//
size++;
return new Node(k,v);
}
//2
if(k.compareTo(node.key) == 0){
// , add add
node.value = v;
return node;
}else if(k.compareTo(node.key) < 0){
node.left = add(node.left,k,v);
return node;
}else{
node.right = add(node.right,k,v);
return node;
}
}
@Override
public boolean contains(K k){
return contains(root,k);
}
public boolean contains(Node node,K k) {
/* if(k == null){
return false;
}
//1
if(node == null){
return false;
}
//2
if(k.compareTo(node.key) == 0){
return true;
}else if(k.compareTo(node.key) < 0){
return contains(node.left,k);
}else{
return contains(node.right,k);
}*/
// get(root,k)
return get(root,k) != null;
}
}
2、BSTMap ： package map;
import java.util.HashMap;
public class Main {
public static void main(String[] args) {
Map map = new BSTMap();
System.out.println("isEmpty:" + map.isEmpty());
int[] arr = {13,6,9,2,7,3,1,8,2,6,4,5,8};
for(int i=0;i map.add(arr[i],arr[i]);
}
System.out.println("size:" + map.getSize());
System.out.println("isEmpty:" + map.isEmpty());
System.out.println("contains5:" + map.contains(5));
System.out.println("contains1:" + map.contains(5));
System.out.println("contains12:" + map.contains(12));
System.out.println("get6:" + map.get(6));
map.set(12,12);
map.set(13,14);
System.out.println("size:" + map.getSize());
System.out.println("get12:" + map.get(12));
System.out.println("get13:" + map.get(13));
}
}
， ！