没有合适的资源?快使用搜索试试~ 我知道了~
Java中AVL平衡二叉树实现Map_(仿照TreeMap和TreeSet)1
需积分: 0 0 下载量 85 浏览量
2022-08-08
22:39:02
上传
评论
收藏 74KB DOCX 举报
温馨提示
试读
45页
Java中AVL平衡二叉树实现Map_(仿照TreeMap和TreeSet)1
资源推荐
资源详情
资源评论
Java 中 AVL 平衡二叉树实现 Map (仿照 TreeMap 和 TreeSet)
1、下面是 AVLTreeMap 的实现
package com;
import java.io.IOException;
import java.util.*;
public class AVLTreeMap<K, V> extends AbstractMap<K, V> implements NavigableMap<K,
V>, java.io.Serializable {
private static final long serialVersionUID = 1731396135957583906L;
private final Comparator<? super K> comparator;
private transient Entry<K, V> root = null;
private transient int size = 0;
private transient int modCount = 0;
public AVLTreeMap() {
comparator = null;
}
public AVLTreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public AVLTreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
public AVLTreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (IOException e) {
} catch (ClassNotFoundException e) {
}
}
public int size() {
return size;
}
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
public boolean containsValue(Object value) {
for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
if (valEquals(value, e.value))
return true;
}
return false;
}
public V get(Object key) {
Entry<K, V> p = getEntry(key);
return p == null ? null : p.value;
}
public Comparator<? super K> comparator() {
return comparator;
}
public K firstKey() {
return key(getFirstEntry());
}
public K lastKey() {
return key(getLastEntry());
}
@SuppressWarnings({ "rawtypes", "unchecked" })
public void putAll(Map<? extends K, ? extends V> map) {
int mapSize = map.size();
if (size == 0 && mapSize != 0 && map instanceof SortedMap) {
Comparable<? super K> cmp = (Comparable<? super K>) ((SortedMap)
map).comparator();
if (cmp == comparator || (cmp != null && cmp.equals(comparator))) {
++modCount;
try {
buildFromSorted(mapSize, map.entrySet().iterator(), null, null);
} catch (IOException e) {
} catch (ClassNotFoundException e) {
}
return;
}
}
super.putAll(map);
}
@SuppressWarnings("unchecked")
final Entry<K, V> getEntry(Object key) {
if (comparator != null) {
return getEntryUsingComparator(key);
}
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K, V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0) {
p = p.left;
} else if (cmp > 0) {
p = p.right;
} else {
return p;
}
}
return null;
}
@SuppressWarnings("unchecked")
final Entry<K, V> getEntryUsingComparator(Object key) {
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K, V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
}
final Entry<K, V> getCeilingEntry(Object key) {
Entry<K, V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
} else if (cmp < 0) {
if (p.right != null)
p = p.right;
else {
Entry<K, V> parent = p.parent;
Entry<K, V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
} else {
return p;
}
}
return null;
}
final Entry<K, V> getFloorEntry(Object key) {
Entry<K, V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp > 0) {
if (p.right != null)
p = p.right;
else
return p;
} else if (cmp < 0) {
if (p.left != null)
p = p.left;
else {
Entry<K, V> parent = p.parent;
Entry<K, V> ch = p;
while (parent != null && ch == parent.left) {
ch = parent;
parent = parent.parent;
}
return parent;
}
} else {
return p;
}
}
return null;
}
final Entry<K, V> getHigherEntry(Object key) {
Entry<K, V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
} else {
if (p.right != null)
p = p.right;
else {
Entry<K, V> parent = p.parent;
Entry<K, V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
}
}
return null;
}
final Entry<K, V> getLowerEntry(Object key) {
Entry<K, V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
剩余44页未读,继续阅读
资源评论
H等等H
- 粉丝: 31
- 资源: 337
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功