数据结构/查找方法
1 顺序查找
2 二分查找需要数据有序
3 查找树
3.1 二叉查找树
3.1.1 定义和性质
所谓二叉查找树(binary search tree , BST)或者是一棵空树;或者是具有以下性质的二叉树:
⑴ 若它的左子树不空,则其左子树中所有结点的值不大于根结点的值;
⑵ 若它的右子树不空,则其右子树中所有结点的值不小于根结点的值;
⑶ 它的左、右子树都是二叉查找树
总结:左小右大
3.1.2 二叉查找树中查找(递归)
3.1.3 二叉查找树中查找(非递归)
3.1.3 最小值(最左边)
public Node min(BinTreeNode v){
if (v!=null)
while (v.hasLChild()) v = v.getLChild();
return v;
}
3.1.4 最大值(最右边)
public Node min(BinTreeNode v){
if (v!=null)
while (v.hasRChild()) v = v.getRChild();
return v;
}
3.1.5 前驱
和后续的相反
3.1.6 后续
在二叉查找树中确定某个结点v 的后续结点的算法思想如下:如果结点v 有右子树,那么v 的后续结点是v 的右子树中关键字最小的;如果结点v 右子树为空,并且v 的后续结点存在,那么v 的后续结点是从v 到根的路径上第一个作为左孩子的父节点。
3.2 AVL树
二叉查找树高度直接影响到操作实现的性能,而在某些特殊的情况下二叉查找树会退化为一个单链表,如插入的结点序列本身就有序的情况下,此时各操作的效率会下降到Ο(n)。二叉查找树的高度越低越好,从树的形态来看,也就是使树尽可能平衡。
3.3 B-树
4 哈希