查找算法总结

发表于 | 分类于 | | 阅读次数:

顺序查找

按顺序依次遍历数组找到一个对应的数字.
时间复杂度是 O(n)

折半查找法

要求数组已经排好序,采用二分法来查找数字.首先看中间的数字是否和查找的数字一样,如果一样则返回.如果大于当前查找数则到前半部分找到,否则在后面部分查找.逐步缩小查找范围.
复杂度: O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int binarySearch(int[] array,int key){
	int lo = 0;
	int hi = array.length - 1;
	while(lo <= hi){
		int mid = (lo + hi)>>1;
		if(array[mid] < key){
			lo = mid +1;
		}else if(array[mid] > key){
			hi = mid - 1;
		}else{
			return mid;
		}
	}
	return -1;
}

二叉查找树

插入和查找时间复杂度为 O(lgN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private Node get(Node node, int key){
	if(node == null) return null;
	if(node.val == key) return node;
	else if(node.val > key) return get(node.left,key);
	else return get(node.right,key);
	
}
private Node put(Node node,int key){
	if(node == null) return new Node(key);
	if(node.val > key) node.left = put(node.left,key);
	else if(node.val < key) node.right = put(node.right,key);
	else node.val = key;
	return node;
}

红黑树

五个性质:
1) 每个结点要么红色,要么黑色
2) 根结点是黑色
3) 叶子结点是黑色
4) 红色结点的孩子结点必须是黑色
5) 从任意一个结点到所有叶子结点的简单路径上的黑色结点数量一样.

时间复杂度: lgN
复杂度原因分析: 因为红黑树是一颗近似平衡的二叉查找树

插入,
红黑树的插入相当于在二叉查找树插入的基础上，将插入点设置为红色，继续做了插入修复操作，以保证红黑树满足5个性质。修复可以分为以下几个情况：
1）如果原树是空树，则直接将此节点改为黑色。
2）如果插入的结点的父结点是黑色，红黑树性质没有破坏，此时什么都不做
以下几种情况需要做调整：
1) 如果当前结点的父结点是红色且祖父结点的另一子结点（叔叔结点）是红色
对策： 将当前节点的父节点和叔叔节点涂黑，祖父结点涂红，把当前结点指向祖父节点，从新的当前节点重新开始算法。

2）当前节点的父节点是红色，叔叔结点是黑色，当前节点是其父节点的右子
解决对策是：当前节点的父节点做为新的当前节点，以新当前节点为支点左旋

3）当前节点的父节点是红色，叔叔结点是黑色，当前节点是其父节点的左子
解决对策是：父节点变为黑色，祖父节点变为红色，在祖父节点为支点右旋

删除

继续讲解之前，补充说明下二叉树结点删除的几种情况，待删除的节点按照儿子的个数可以分为三种：

1）没有儿子，即为叶结点。直接把父结点的对应儿子指针设为NULL，删除儿子结点就OK了。
2）只有一个儿子。那么把父结点的相应儿子指针指向儿子的独生子，删除儿子结点也OK了。
3）有两个儿子。这是最麻烦的情况，因为你删除节点之后，还要保证满足搜索二叉树的结构。其实也比较容易，我们可以选择左儿子中的最大元素或者右儿子中
的最小元素放到待删除节点的位置，就可以保证结构的不变。当然，你要记得调整子树，毕竟又出现了节点删除。习惯上大家选择左儿子中的最大元素，其实
选择右儿子的最小元素也一样，没有任何差别，只是人们习惯从左向右。这里咱们也选择左儿子的最大元素，将它放到待删结点的位置。左儿子的最大元素其
实很好找，只要顺着左儿子不断的去搜索右子树就可以了，直到找到一个没有右子树的结点。那就是最大的了。

删除修复情况1：当前节点是黑+黑且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)
把父节点染成红色，把兄弟结点染成黑色，以兄弟节点为转轴左旋（右旋）之后重新进入算法

删除修复情况2：当前节点是黑加黑且兄弟是黑色且兄弟节点的两个子节点全为黑色
把当前节点和兄弟节点中抽取一重黑色追加到父节点上，把父节点当成新的当前节点，重新进入算法。

删除修复情况3：当前节点颜色是黑+黑，兄弟节点是黑色，兄弟的左子是红色，右子是黑色
解法：把兄弟结点染红，兄弟左子节点染黑，之后再在兄弟节点为支点解右旋，之后重新进入算法。

删除修复情况4：当前节点颜色是黑-黑色，它的兄弟节点是黑色，但是兄弟节点的右子是红色
把兄弟节点染成当前节点父节点的颜色，把当前节点父节点染成黑色，兄弟节点右子染成黑色，之后以当前节点的父节点为支点进行左旋

http://blog.csdn.net/v_JULY_v/article/details/6105630

0%