rainyzz's blog

搜索复习

二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int search(int[] a, int target){
int low = 0;
int high = a.length - 1;
while(low <= high){
int mid = low + (high - low) / 2;
if(target < a[mid]){
high = mid - 1;
}else if(target > a[mid]){
low = mid + 1;
}else{
return mid;
}
}
return -1;
}

二叉查找树

由于二分搜索需要保持数据有序,在数据量巨大的情况下,二叉查找树能够在lgN时间内插入新数据并保持有序,方便二分搜索的进行。

二叉搜索树中删除元素时需要重新调整树结构

当二叉查找树不平衡时,退化成链表形式,搜索速度降低。因此需要引入平衡二叉树,搜索时间上界为lgN。

2-3树

每个节点有2个子树或者3个子树。

插入新节点时,将新节点加入其该插入的位置,如果该节点子树数量超过2个,则进行对应的调整。

所有的调整都是局部的调整,能够很快完成。

###红黑树

每一棵左倾红黑树都对应一棵2-3树。每一棵普通红黑树都对应一棵2-3-4树。

左倾红黑树:将3-节点转换称为一个左倾的红链接。不能有两个连续的红链接。

红黑树:节点是红色或黑色,根是黑色,所有叶子都是黑色(叶子是NIL节点),每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)

###红黑树 AVL树区别

AVL树达到高度平衡,红黑树牺牲高度平衡达到基本平衡程度,其新插入数据产生的不平衡都可以在三次旋转中解决,是一个现实中比较实用的算法。

#散列表

Java中默认的equals()方法和hashCode() 方法,equals() 方法默认比较引用,hashCode() 方法默认相当于返回内存地址。只有实现了hashCode()方法才能将其作为散列表的key。

1
2
3
4
5
6
7
public boolean equals(Object object) {
return this == object;
}
public int hashCode() {
return VMMemoryManager.getIdentityHashCode(this);
}

冲突处理:链表,线性探测

#Java

红黑树:java.util.TreeMap

基于拉链法的散列表:java.util.HashMap

TreeMap 和 TreeSet 是 Java Collection Framework 的两个重要成员,其中 TreeMap 是 Map 接口的常用实现类,而 TreeSet 是 Set 接口的常用实现类。虽然 HashMap 和 HashSet 实现的接口规范不同,但 TreeSet 底层是通过 TreeMap 来实现的,因此二者的实现方式完全一样。而 TreeMap 的实现就是红黑树算法。

对于 TreeMap 而言,由于它底层采用一棵红黑树来保存集合中的 Entry,这意味这 TreeMap 添加元素、取出元素的性能都比 HashMap 低:当 TreeMap 添加元素时,需要通过循环找到新增 Entry 的插入位置,因此比较耗性能;当从 TreeMap 中取出元素时,需要通过循环才能找到合适的 Entry,也比较耗性能。

但 TreeMap、TreeSet 比 HashMap、HashSet 的优势在于:TreeMap 中的所有 Entry 总是按 key 根据指定排序规则保持有序状态,TreeSet 中所有元素总是根据指定排序规则保持有序状态。