四、查找算法

一、查找算法介绍

二、线性查找算法

2.1 顺序查找

package com.gyh.search;/*** @author Gao YongHao* @version 1.0*/
public class SeqSearch implements Search<Integer> {public static void main(String[] args) {Integer arr[] = {1, 9, 11, -1, 34, 89};int index = new SeqSearch().search(arr, -1);System.out.println(index);}@Overridepublic int search(Integer[] nums, Integer value) {for (int i = 0; i < nums.length; i++) {if (nums[i].equals(value)) {return i;}}return -1;}
}

2.2 二分查找（折半查找）

package com.gyh.search;import java.util.ArrayList;/*** @author Gao YongHao* @version 1.0* <p>* 注意：使用二分查找的前提是 该数组是有序的*/
public class BinarySearch implements Search<Integer> {public static void main(String[] args) {Integer[] arr = {-1, 11, 11, 11, 34, 89};BinarySearch binarySearch = new BinarySearch();int index = binarySearch.search(arr, 11);System.out.println(index);ArrayList<Integer> integers = binarySearch.searchAll(arr, 11);integers.forEach(System.out::println);}@Overridepublic int search(Integer[] nums, Integer value) {if (nums[0] > value || nums[nums.length - 1] < value) {return -1;}return search(nums, value, 0, nums.length - 1);}private int search(Integer[] nums, int value, int left, int right) {if (left > right) {return -1;}int mid = (left + right) / 2;if (nums[mid] < value) {return search(nums, value, mid + 1, right);} else if (nums[mid] > value) {return search(nums, value, left, mid - 1);} else {return mid; // 只返回一个值的写法}}@Overridepublic ArrayList<Integer> searchAll(Integer[] nums, Integer value) {if (nums[0] > value || nums[nums.length - 1] < value) {return new ArrayList<>();}return search2(nums, value, 0, nums.length - 1);}private ArrayList<Integer> search2(Integer[] nums, int value, int left, int right) {if (left > right) {return new ArrayList<>();}int mid = (left + right) / 2;if (nums[mid] < value) {return search2(nums, value, mid + 1, right);} else if (nums[mid] > value) {return search2(nums, value, left, mid - 1);} else {/*** 思路分析* 1. 在找到 mid 索引值，不要马上返回* 2. 向 mid 索引值的左边扫描，将所有满足 等于value的元素下标加入到集合 ArrayList中* 3. 向 mid 索引值的右边扫描，将所有满足 等于value的元素下标加入到集合 ArrayList中*/ArrayList<Integer> integers = new ArrayList<>();int temp = mid - 1;while (temp >= 0 && nums[temp].equals(nums[mid])) {integers.add(temp--);}integers.add(mid);temp = mid + 1;while (temp <= nums.length - 1 && nums[temp].equals(nums[mid])) {integers.add(temp++);}return integers;}}
}

2.3 插值查找

package com.gyh.search;import java.util.ArrayList;/*** @author Gao YongHao* @version 1.0*/
public class InsertSearch implements Search<Integer> {public static void main(String[] args) {Integer[] arr = {-1, 11, 11, 11, 34, 89};InsertSearch insertSearch = new InsertSearch();int index = insertSearch.search(arr, 11);System.out.println(index);}@Overridepublic int search(Integer[] nums, Integer value) {return search(nums, value, 0, nums.length - 1);}private int search(Integer[] nums, int value, int left, int right) {// 注意：value < nums[0]  和  value  > nums[nums.length -1 ] 的条件必须有// 否则得到的mid值可能越界（如value比nums的最大的数大得多 ...）if (left > right || value < nums[left] || value > nums[right]) {return -1;}// 自适应的midint mid = left + (value - nums[left]) / (nums[right] - nums[left]) * (right - left);if (nums[mid] < value) {return search(nums, value, mid + 1, right);} else if (nums[mid] > value) {return search(nums, value, left, mid - 1);} else {return mid; // 只返回一个值的写法}}}

2.4 斐波拉契（黄金分割法）查找算法

package com.gyh.search;
import java.util.Arrays;/*** @author Gao YongHao* @version 1.0*/
public class FibonacciSearch implements Search<Integer> {private static final int MAX = 20;public static void main(String[] args) {Integer[] arr = {-1, 11, 11, 11, 34, 89};FibonacciSearch fibonacciSearch = new FibonacciSearch();int index = fibonacciSearch.search(arr, -1);System.out.println(index);}@Overridepublic int search(Integer[] nums, Integer value) {int low = 0;int high = nums.length - 1;int k = 0; // 表示斐波拉契分割数值的下标int mid = 0; // 表示存放mid值int[] f = fib(); // 获取到斐波拉契数列// 获取到斐波那契分割数值的下标while (high > f[k] - 1) {k++;}// 因为 f[k] 值可能大于 nums 的长度，因此我们需要使用Arrays类，构造一个新的数组，并指向a[]// 不足的部分会使用 0 填充Integer[] temp = Arrays.copyOf(nums, f[k]);// 实际上需求使用 nums 数组最后的数填充 temp// 只需要对总数据作一次填充即可for (int i = high + 1; i < temp.length; i++) {temp[i] = nums[high];}// 与二分查找类似使用while数组处理，找到我们的数 keywhile (low <= high) {mid = low + f[k - 1] - 1; // 黄金分割点位置if (value < temp[mid]) { // 我们应该继续向左继续向数组的前面查找high = mid - 1;/*** 为什么 k--* 说明* 1. 全部元素 = 前面的元素 + 后面的元素* 2. f[k] = f[k-1] + f[k-2]* 因为 前面的有 f[k-1] 元素，所以可以继续拆分 f[k-1] = f[k-2] + f[k-3]* 即 在前面的f[k-1]继续查找 k--* 即 下次循环 mid = low + f[k-1-1]-1*/k--;} else if (value > temp[mid]) {low = mid + 1;/*** 为什么是 k-=2* 说明* 1. 全部元素 = 前面的元素 + 后面的元素* 2. f[k] = f[k-1] + f[k-2]* 3. 因为后面我们有f[k-2]个数所以可以继续拆分 f[k-2] = f[k-3] + f[k-4]* 4. 即在后面的f[k-2]继续查找 k-=2* 5. 即下次循环 mid = low + f[k-1-2]-1*/k -= 2;} else { // 找到// 需要确定，返回的是哪个下标// 存在最终定位的 mid 是由原数组最大值扩充的元素return Math.min(mid, high);}}return -1;}private int[] fib() {int[] fs = new int[MAX];for (int i = 0; i < MAX; i++) {if (i == 0 || i == 1) {fs[i] = 1;continue;}fs[i] = fs[i - 1] + fs[i - 2];}return fs;}}

三、树表的查找

3.1 二叉排序树

3.1.1 引入

3.1.2 基本介绍

3.1.3 二叉树的遍历

package com.gyh.tree;/*** @author Gao YongHao* @version 1.0*/
public class BinarySortTree {public static void main(String[] args) {int[] arr = {7, 3, 10, 12, 5, 1, 9};BNode binarySortTree = new BinarySortTree().createBinarySortTree(arr);new BinarySortTree().midOrder(binarySortTree);}public void midOrder(BNode node) {if (node == null) {return;}midOrder(node.left);System.out.println(node.n);midOrder(node.right);}public BNode createBinarySortTree(int[] arr) {if (arr == null || arr.length <= 0) {return null;}BNode root = new BNode(arr[0]);BNode tNode;for (int i = 1; i < arr.length; i++) {tNode = root;while (true) {if (arr[i] < tNode.n) {if (tNode.left == null) {tNode.left = new BNode(arr[i]);break;} else {tNode = tNode.left;}} else {if (tNode.right == null) {tNode.right = new BNode(arr[i]);break;} else {tNode = tNode.right;}}}}return root;}
}class BNode {int n;BNode left;BNode right;public BNode(int n) {this.n = n;}public BNode(int n, BNode left, BNode right) {this.n = n;this.left = left;this.right = right;}
}

3.1.4 二叉树的删除

• 主要思想：

1. 前提是 需要有指向 当前结点 与 其双亲结点 的变量
2. 若当前结点是叶子结点，直接删除
3. 若当前结点的孩子结点只有一个（左或右），将当前结点的左（右）孩子赋给双亲结点的指向当前结点的变量(parent.left或parent.right)
4. 若当前结点的孩子结点有两个，则使用当前结点的右子树的中最小值对应的结点填充到这个位置(再该填充值原来的位置的结点); 或使用当前结点的左子树的中最大值对应的结点填充到这个位置(再该填充值原来的位置的结点)
   

package com.gyh.tree;/*** @author Gao YongHao* @version 1.0*/
public class BinarySortTree {private BNode root;public static void main(String[] args) {int[] arr = {7, 3, 10, 12, 5, 1, 9};BNode binarySortTree = BinarySortTree.createBinarySortTree(arr);new BinarySortTree(binarySortTree).midOrder();new BinarySortTree(binarySortTree).remove(7);new BinarySortTree(binarySortTree).midOrder();}public BinarySortTree(BNode root) {this.root = root;}public void midOrder() {midOrder(root);}private void midOrder(BNode bn) {if (bn == null) {return;}midOrder(bn.left);System.out.println(bn.n);midOrder(bn.right);}// 查找要删除的结点private BNode search(BNode bn, int value) {if (bn == null) {return null;}if (value < bn.n) {return search(bn.left, value);} else if (value > bn.n) {return search(bn.right, value);} else {return bn;}}// 查找要删除结点的父节点private BNode searchParent(BNode bn, int value) {if ((bn.left != null && bn.left.n == value) || (bn.right != null && bn.right.n == value)) {return bn;} else {if (value < bn.n && bn.left != null) {return searchParent(bn.left, value); // 向左子树寻找} else if (value > bn.n && bn.right != null) {return searchParent(bn.right, value); // 向右子树寻找} else {return null;}}}public void remove(int value) {remove(root, value);}public void remove(BNode bn, int value) {// 1、寻找要删除的结点BNode node;if (root == null || (node = search(bn, value)) == null) {return;}// 2、寻找要删除的结点的父结点BNode pNode = searchParent(root, value);// 若是叶子结点则直接删除后，重置其父节点的指向if (node.left == null && node.right == null) {if (pNode == null) {// 删除根节点信息并退出root = null;return;}if (pNode.left == node) {pNode.left = null;} else {pNode.right = null;}} else if (node.left == null) { // 若只有一棵子树if (pNode == null) {// 删除根节点root = node.right;return;}if (pNode.left == node) {pNode.left = node.right;} else {pNode.right = node.right;}} else if (node.right == null) {if (pNode == null) {// 删除根节点root = node.left;return;}if (pNode.left == node) {pNode.left = node.left;} else {pNode.right = node.left;}} else { // 有两棵子树// 方式一：找左子树的最大值(最右的结点)
//            BNode lNode = node.left;
//            while (lNode.right != null) {
//                lNode = lNode.right;
//            }
//            // 删除左边的最大值点
//            remove(node, lNode.n);
//            // 将左边的最大值赋给当前结点
//            node.n = lNode.n;// 方式二：找右子树的最小值(最最的结点)BNode rNode = node.right;while (rNode.left != null) {rNode = rNode.left;}// 删除右边的最小值点remove(node, rNode.n);// 将右边的最小值赋给当前结点node.n = rNode.n;}}public static BNode createBinarySortTree(int[] arr) {if (arr == null || arr.length <= 0) {return null;}BNode root = new BNode(arr[0]);BNode tNode;for (int i = 1; i < arr.length; i++) {tNode = root;while (true) {if (arr[i] < tNode.n) {if (tNode.left == null) {tNode.left = new BNode(arr[i]);break;} else {tNode = tNode.left;}} else {if (tNode.right == null) {tNode.right = new BNode(arr[i]);break;} else {tNode = tNode.right;}}}}return root;}
}class BNode {int n;BNode left;BNode right;public BNode(int n) {this.n = n;}public BNode(int n, BNode left, BNode right) {this.n = n;this.left = left;this.right = right;}
}

3.2 平衡二叉树

3.2.1 基本介绍

• 平衡二叉树的平衡调整方法
  在插入结点时，首先按照二叉排序树处理，若插入结点后破坏了平衡二叉树的特性，需要对平衡二叉树进行调整。调整方法是：找到离插入结点最近且平衡因子绝对值超过1的祖先结点，以该结点为根的子树称为 最小不平衡子树，可将重新平衡的范围局限于这棵树。
  

3.2.2 左旋转（对应RR型）

3.2.3 右旋转（对应LL型）

3.2.4 双旋转（对应LR型和RL型）

package com.gyh.tree;/*** @author Gao YongHao* @version 1.0* <p>* 平衡二叉树*/
public class BalancedBinaryTree {public static void main(String[] args) {int[] arr = {4, 3, 6, 5, 7, 8};BBNode binarySortTree = BalancedBinaryTree.createBinarySortTree(arr);BalancedBinaryTree.midOrder(binarySortTree);System.out.println("树的高度：" + BalancedBinaryTree.height(binarySortTree));System.out.println("树的左子树高度：" + BalancedBinaryTree.leftHeight(binarySortTree));System.out.println("树的右子树高度：" + BalancedBinaryTree.rightHeight(binarySortTree));}// RR 型对应左旋转public static void leftRote(BBNode root) {// 创建一个新节点，以当前根节点的值BBNode bbNode = new BBNode(root.d);// 把新的结点的左子树根节点值设置成当前结点的左子树根节点值bbNode.left = root.left;// 把新的结点的右子树节点值设置成当前结点的右子树的左子树节点值bbNode.right = root.right.left;// 把当前结点的值替换为右子树节点值root.d = root.right.d;// 把当前结点的右子树设置为右子树的右子树节点值root.right = root.right.right;// 把当前结点的左子树设置为新节点root.left = bbNode;}// LL型对应右旋转private static void rightRote(BBNode root) {BBNode bbNode = new BBNode(root.d);bbNode.right = root.right;bbNode.left = root.left.right;root.d = root.left.d;root.left = root.left.left;root.right = bbNode;}public static void midOrder(BBNode bn) {if (bn == null) {return;}midOrder(bn.left);System.out.println(bn.d);midOrder(bn.right);}// 计算平衡因子private static int avlFactor(BBNode bbn) {return leftHeight(bbn) - rightHeight(bbn);}// 平衡化过程// 本例中并没有寻找最小不平衡子树，直接对根进行平衡化操作（此操作过程有误，仅实验方法）private static void avl(BBNode root) {if (root == null) {return;}// 计算左子树高 和 右子树高int avlFactor = avlFactor(root);int leftAvlFactor;if (root.left == null) {leftAvlFactor = 0;} else {leftAvlFactor = avlFactor(root.left);}int rightAvlFactor;if (root.right == null) {rightAvlFactor = 0;} else {rightAvlFactor = avlFactor(root.right);}if (avlFactor == -2 && rightAvlFactor == -1) { // 需要左旋转leftRote(root);}if (avlFactor == -2 && rightAvlFactor == 1) { // 先右后左旋转rightRote(root.right);leftRote(root);return;}if (avlFactor == 2 && leftAvlFactor == 1) { // 需要右旋转rightRote(root);return;}if (avlFactor == 2 && leftAvlFactor == -1) { // 需要左后右旋转leftRote(root.left);rightRote(root);}}public static BBNode createBinarySortTree(int[] arr) {if (arr == null || arr.length <= 0) {return null;}BBNode root = new BBNode(arr[0]);BBNode tNode;for (int i = 1; i < arr.length; i++) {tNode = root;while (true) {if (arr[i] < tNode.d) {if (tNode.left == null) {// 添加新值tNode.left = new BBNode(arr[i]);// 平衡化处理avl(root);break;} else {tNode = tNode.left;}} else {if (tNode.right == null) {tNode.right = new BBNode(arr[i]);// 平衡化处理avl(root);break;} else {tNode = tNode.right;}}}}return root;}public static int leftHeight(BBNode bbn) {return height(bbn.left);}public static int rightHeight(BBNode bbn) {return height(bbn.right);}public static int height(BBNode bbn) {if (bbn == null) {return 0;}return Math.max(height(bbn.left), height(bbn.right)) + 1;}
}class BBNode {int d;BBNode left;BBNode right;public BBNode(int d) {this.d = d;}
}

3.3 B树

3.3.1 引入

3.3.2 B树的基本介绍

• 定义见书上 P210
  

3.3.3 2-3树

• 3阶（阶数代表最大分叉数）的B树，至多可有两个关键字，至少有一个关键字（即子树个数为2或者3，故成为 2-3树）
  

• 插入时的分裂方法参见书 P214

3.3.4 B树、B+树和B*树

• B树
  

• 注意：对B树数据存放位置的描述（可能存在于叶子结点与非叶子结点）

• B+树
  

• 注意：对B+树数据存放位置的描述（只存在于叶子结点）

• B*树
  

四、散列（哈希）表

4.1 散列（哈希）表引出

4.2 散列（哈希）表的基本介绍

4.3 散列（哈希）表 — 应用实例

package com.gyh.search;import java.util.HashMap;
import java.util.Objects;/*** @author Gao YongHao* @version 1.0*/
@SuppressWarnings("all")
public class HashTableDemo<K, V> {public static void main(String[] args) {HashTableDemo<Integer, Emp> hashTab = new HashTableDemo<Integer, Emp>();hashTab.put(1, new Emp(1, "aa", 1, 12, "zg"));hashTab.put(1, new Emp(1, "bb", 1, 12, "33"));hashTab.put(1, new Emp(1, "dd", 1, 12, "dd"));hashTab.put(101, new Emp(101, "cc", 1, 12, "55"));System.out.println(hashTab.get(1));}// 数组private Node<K, V>[] table;// 设置最大的容量private static int MAX = 100;private int size = 0;// 不考虑扩容public HashTableDemo() {table = (Node<K, V>[]) new Node[MAX];}public void put(K k, V v) {putVal(hash(k), k, v);}public V get(K k) {
//        HashMapint hash;Node<K, V> n, e;if (size > 0 && (e = table[hash = hash(k)]) != null) {// 遍历位于同一位置的单链表上的元素while (e != null) {if (hash == e.hash && (k == e.k || k.equals(e.k))) {return e.v;}e = e.next;}}return null;}private void putVal(int hash, K k, V v) {Node<K, V> cur, p;// 该位置没有初始的数值if ((cur = table[hash]) == null) {table[hash] = new Node<>(hash, k, v, null);size++;} else { // 遍历链表中的元素。相等则值替换，不等则直接添加至最后while (cur != null) {if (hash == cur.hash && (k == cur.k || k.equals(cur.k))) {// 表示相同则值替换cur.v = v;break;}// 若是最后一个元素则添加if ((p = cur.next) == null) {cur.next = new Node<>(hash, k, v, null);size++;break;} else {cur = p;}}}}// 散列函数计算存储的位置(除留余数法)private int hash(K v) {int h = v.hashCode();return h % MAX;}}class Node<K, V> {int hash;K k;V v;Node<K, V> next;public Node(int hash, K k, V v, Node<K, V> next) {this.hash = hash;this.k = k;this.v = v;this.next = next;}
}class Emp {private int id; // 雇员的Idprivate String name; // 名字private int gender; // 性别private int age; // 年龄private String address; // 地址public Emp() {}@Overridepublic String toString() {return "Emp{" +"id=" + id +", name='" + name + '\'' +", gender=" + gender +", age=" + age +", address='" + address + '\'' +'}';}public Emp(int id, String name, int gender, int age, String address) {this.id = id;this.name = name;this.gender = gender;this.age = age;this.address = address;}public int getId() {return id;}public void setId(int id) {this.id = id;}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getGender() {return gender;}public void setGender(int gender) {this.gender = gender;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}public String getAddress() {return address;}public void setAddress(String address) {this.address = address;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Emp emp = (Emp) o;return id == emp.id &&gender == emp.gender &&age == emp.age &&Objects.equals(name, emp.name) &&Objects.equals(address, emp.address);}@Overridepublic int hashCode() {return id; // 当前任务使用 id 作为 hashCode}
}