使用二叉搜索树实现一个简单的Map
2024-10-15 17:40:51
之前看了刘新宇大大的《算法新解》有了点收获，闲来无事，便写了一个二叉搜索树实现的Map类。
java的Map接口有很多不想要的方法，自己定义了一个
public interface IMap<K, V> {
V get(K k);
void put(K k, V v);
V remove(K k);
}
具体实现：
public class BSTree<K, V> implements IMap<K, V> {
Entry<K, V> head = null;
@Override
public V get(K k) {
return get(head, k);
}
private V get(Entry<K, V> node, K k) {
if (node == null) {
return null;
}
int compare = compare(node.key, k);
if (compare == 0) {
return node.value;
} else if (compare > 1) {
return get(node.right, k);
} else {
return get(node.left, k);
}
}
@Override
public void put(K k, V v) {
//1.head is null
if (head == null) {
head = new Entry<>(k, v, null);
}
//2.head is not null
else {
put(head, k, v);
}
}
private void put(Entry<K, V> node, K k, V v) {
int compare = compare(node.key, k);
if (compare == 0) {
node.value = v;
} else if (compare > 1) {
if (node.right == null) {
node.right = new Entry<>(k, null, node);
}
put(node.right, k, v);
} else {
if (node.left == null) {
node.left = new Entry<>(k, null, node);
}
put(node.left, k, v);
}
}
private int compare(K key, K k) {
return ((Comparable) key).compareTo(k);
}
@Override
public V remove(K k) {
return remove(head, k);
}
private V remove(Entry<K, V> node, K k) {
if (node == null) {
return null;
}
int compare = compare(node.key, k);
if (compare == 0) {
//1.no child
if (node.left == null && node.right == null) {
if (node.parent == null)
head = null;
else if (node == node.parent.left) {
node.parent.left = null;
} else {
node.parent.right = null;
}
return node.value;
}
//2.has right child
else if (node.right != null) {
V oldValue = node.value;
Entry<K, V> newNode = findMin(node.right);
node.key=newNode.key;
node.value = newNode.value;
newNode.parent.right = null;
return oldValue;
}
//3.has no right child,has left child
else{
V oldValue = node.value;
Entry<K, V> newNode = findMax(node.left);
node.key=newNode.key;
node.value = newNode.value;
newNode.parent.left= null;
return oldValue;
}
} else if (compare > 0) {
return remove(node.right, k);
} else {
return remove(node.left, k);
}
}
private Entry<K, V> findMax(Entry<K, V> left) {
if (left.right == null) {
return left;
}else{
return findMax(left.right);
}
}
private Entry<K, V> findMin(Entry<K, V> right) {
if (right.left == null) {
return right;
}else {
return findMin(right.left);
}
}
class Entry<K, V> {
K key;
V value;
Entry<K, V> left;
Entry<K, V> right;
Entry<K, V> parent;
private Entry(K key, V value, Entry<K, V> parent) {
this.key = key;
this.value = value;
left = null;
right = null;
this.parent = parent;
}
}
}
测试的类：
public class BSTreeTest {
private static int write_num = 100_0000;
private static int read_num = 100_0000;
public static void main(String[] args) {
// IMap<String,Integer> map = new BSTree();
// Map<String, Integer> map = new TreeMap<>();
// Map<String, Integer> map = new HashMap<>();
Map<String, Integer> map = new LinkedHashMap<>();
long start = System.nanoTime();
for (int i = 0; i < write_num; i++) {
map.put("" + i, i);
}
for (int i = 0; i < read_num; i++) {
Integer s = map.get(i + "");
assert s.equals(i);
}
for (int i = 0; i < read_num / 2; i++) {
map.remove(i + "");
}
for (int i = 0; i < read_num / 2; i++) {
Integer s = map.get(i + "");
assert s == null;
}
for (int i = read_num / 2; i < read_num / i++; i++) {
Integer s = map.get(i + "");
assert s.equals(i);
}
System.out.println("map cost:" + (System.nanoTime() - start));
}
}
在各自只运行一次的情况下测试数据如下：
map cost:1125174394 //myMap
map cost:812963047 //TreeMap
map cost:475993738 //HashMap
map cost:475993738 //LinkedHashMap
由于二叉搜索树没有自平衡机制，搜索的时间在O(n*n)与O(lgn)之间摇摆，因此对比java用红黑树实现的TreeMap时间O(lgn)要多上很多。
最新文章
- 从啥也不会到可以胜任最基本的JavaWeb工作，推荐给新人的学习路线（二）
- JSTL标签库
- 关于使用flexible.js自适应页面，发现文字很多时，字体会变大的问题的原因和解决方案
- java中的程序流程控制
- 如何去除内联元素（inline-block元素）之间的间距（转载）
- lucene 专业名词作用整理
- Windows下安装Cygwin
- C++编程技术之 异常处理（上）
- ubuntu上的附件-终端和用快捷键ctrl+alt+f1 有啥区别
- 【linux学习笔记之一】linux系统目录结构以及常用系统命令
- 编程&学习总结格式
- 10大必备的Intellij插件，大幅提高你的工作效率
- What is the RESTful API ?
- Python爬虫之PyQuery使用（六）
- Swift5 语言指南(二十七) 访问控制
- java: 保留两位小数4种方法
- java Calendar
- TPO-23 C2 Advice on choosing courses
- [QT_QML]qml假如调试信息 qDebug console.debug
- mybatis分页查询需要注意的问题