|
一，二叉树查找 除了前面介绍的几个查找算法以外，还有一种叫二叉树查找，二叉树查找比较简单，我们知道二叉树的节点有两种常见的遍历方式，一种是BFS（广度优先搜索），一种是DFS（深度优先搜索）。如果二叉树是排序好的，我们使用DFS，查找的时候先找根节点，如果找到就返回，如果没找到，判断是大于根节点还是小于根节点，如果小于根节点就在左半部分找，如果大于根节点就在右半部分找……一直递归下去。如果二叉树没有排序我们也可以一层一层的找，使用BFS，当然这个比较费劲，但也没办法，因为没有排过序，也只能这样干了。 二，跳表查找 我们知道链表添加和删除比较方便，但查找不是很方便，对于排过序的单向链表来说如果我们要查找，每次我们都要从头开始查，如果链表比较长的话，这样效率很慢。但使用跳表效率可以大大改善，虽然跳表每次也是从头开始查，但他每次可以跳很多步，不像链表每次只能走一步，java中有ConcurrentSkipListMap 这个类，是基于跳表的，代码就不在贴了，大家有兴趣可以自己看，关于跳表在网上找了一张图，可以参照下
三，其他查找 当然还有一些其他的比如2-3树，红黑树，B树、B+树。其中2-3树是最简单的B-树（或-树）结构，其每个非叶节点都有两个或三个子节点。红黑树也算是个平衡二叉树，他会根据插入的节点进行左旋或右旋来达到平衡。B树也称为B-树，首先把根结点取来，在根结点所包含的关键字K1,…,Kn查找给定的关键字（可用顺序查找或二分查找法），若找到等于给定值的关键字，则查找成功；否则，一定可以确定要查找的关键字在Ki与Ki+1之间，Pi为指向子树根节点的指针，此时取指针Pi所指的结点继续查找，直至找到，或指针Pi为空时查找失败。B+ 树元素自底向上插入，这与二叉树恰好相反。 |
|
|
