查找
1. 线性表的查找
1.1 顺序查找
时间复杂度： O(n)
function SeqSearch(arr, k) {
let i = 0, len = arr.length;
while (i < len && arr[i] !== k)
i++;
if (i < len)
return i + 1;
else
return 0;
}
优化方式，在数组末尾添加一个关键字为 k 的记录，作为哨兵，这样在查找过程中不用再判断 i 是否越界
function SeqSearch1(arr, k) {
let i = 0, len = arr.length;
arr[len] = k;
while (arr[i] !== k)
i++;
arr.pop(); // 删除最后一个元素
if (i < len)
return i + 1;
else
return 0;
}
1.2 折半查找
折半查找又称二分查找
要求：顺序表是按照关键字有序的
时间复杂度：O(log?n)
平均查找长度：log?(n+1)-1
function BinSearch(arr, k) {
let low = 0,
high = arr.length - 1,
mid;
while (low <= high) {
mid = Math.floor((low + high) / 2);
if (k === arr[mid])
return mid;
else if (k < arr[mid])
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
1.3 索引存储和分块查找
1. 索引存储结构
在存储数据的同时还建立附加的索引表，索引表由关键字和地址组成。
在索引存储结构中对关键字查找时可以进行快速查找（因为索引表中按关键字有序排序，可以使用折半查找）。
优点：查找效率变高。
缺点：要建立索引表，增加空间开销。
2.分块查找
将数组 arr[0...n-1] 分为 b 块，前 b - 1块 元素个数为 s = n/b 最后一块元素个数小于等于 s。
要求：整个表是”分块有序“的，前一块的最大值必须小于后一块的最小值
查找思路：
- 抽取各块中最大关键字以及起始位置建立索引表 IDX[0…b-1]。
- 查找索引表确定数据在哪个块之中。
- 然后在块中使用顺序查找查找数据。
平均查找长度：log?(b+1)-1 + s/2
时间复杂度：O(log?b + s)
/**
* 采用折半查找的分块查找
* @param idxArr 分块索引表
* @param arr 数组
* @param k 要查找的关键字
* @return index 返回关键字位置
*/
function IdxSearch(idxArr, arr, k) {
let low = 0, idxLen = idxArr.length, high = idxLen - 1, mid;
// 找到大于等于 k 的最左边的记录：high + 1
while(low <= high) {
mid = Math.floor((low + high) / 2);
if (k <= idxArr[mid].max)
high = mid - 1;
else
low = mid + 1;
}
let start = idxArr[high + 1].start; // k 所在块的起始下标
let end = high + 2 < idxLen ? idxArr[high + 2].start : arr.length - 1;
while(start <= end && arr[start] !== k)
start++;
if (arr[start] === k)
return start;
return -1;
}
验证
let arr1 = [101, 102, 103, 104, 105,
201, 202, 203, 204, 200,
307, 302, 303, 304, 310];
let idxArr = [{max: 105, start: 0}, {max: 204, start: 5}, {max: 310, start: 10}]
console.log(IdxSearch(idxArr, arr1, 302)); // 11
2. 树表的查找
2.1 二叉排序树
概念：二叉排序树又称二叉搜索树(binary search tree, BST)
必须满足以下性质
- 左子树所有结点关键字均小于（实际应用中为小于等于）根结点关键字。
- 右子树所有结点关键字均大于（实际应用中为大于等于）根结点关键字。
- 即二叉排序树的中序遍历是有序的。
时间复杂度：O(log?n)
// BTS 节点
class BTSNode {
constructor(val) {
this.val = val;
this.left = this.right = null;
}
}
二叉搜索树
class BFS {
constructor() {
this.root = null;
this.count = 1;
}
/**
* 向二叉排序树插入一个值为 k 的节点，插入成功返回 true，否则返回 false
* @param val 插入的值
* @return {boolean} 是否插入成功
*/
insert(val) {
let node = new BTSNode(val);
if (this.root === null) {
this.root = node;
this.count++;
return true;
} else {
let cur = this.root;
while(true) {
if (cur.val === val) // 树中存在相同值的节点，返回假
return false;
if (val < cur.val) {
if (cur.left === null) {
cur.left = node;
break;
}
cur = cur.left;
}
else if (val > cur.val) {
if (cur.right === null) {
cur.right = node;
break;
}
cur = cur.right;
}
}
this.count++;
return true;
}
}
// 根据数组中对应的值创建二叉树
create(arr) {
for (let i = 0;i < arr.length; i++)
this.insert(arr[i]);
}
// 查找值为 val 元素的节点
search(val) {
function searchNode(node, val) {
if (node === null || node.val === val)
return node;
else if (val < node.val)
return searchNode(node.left, val);
else if (val > node.val)
return searchNode(node.right, val);
}
return searchNode(this.root, val)
}
//查找值为 val 的节点，返回 { current: 值为 val 的节点, parent: 其父节点 };
searchWithParent(val) {
function t
empSearch(bt, val, parent) {
if (bt === null)
return { current: null, parent };
if (bt.val === val)
return { current: bt, parent };
else if (val < bt.val)
return tempSearch(bt.left, val, bt);
return tempSearch(bt.right, val, bt);
}
return tempSearch(this.root, val, null);
}
}
递归实现删除BST中的节点
因为BST的左子树总是比根节点小，右子树总是比根节点大，所以我们将根节点的值与要删除的 key 值对比，就知道要删除的值大概在哪个位置：
- 相等：要删除的节点就是当前根节点，即递归退出条件
- key更大：则要递归朝右子树去删除
- key更小：则要递归朝左子树去删除
找到要删除后的节点会出现四种情况：
-
待删除的节点左右子树均为空。证明是叶子节点，直接删除即可，即将该节点置为
null -
待删除的节点左子树为空，让待删除节点的右子树替代自己。
- 待删除的节点右子树为空，让待删除节点的左子树替代自己。
- 如果待删除的节点的左右子树都不为空。我们需要找到比当前节点小的最大节点（前驱）[或比当前节点大的最小节点（后继）]，来替换自己.
具体代码实现：
function removeNode (root, key) {
if (root == null) return root
if (root.val > key) {
// 往左子树找
root.left = removeNode(root.left, key)
} else if (root.val < key) {
// 往右子树找
root.right = removeNode(root.right, key)
} else {
// 找到了
if (!root.left && !root.right) {
// 待删除的节点左右子树均为空。证明是叶子节点，直接删除即可
root = null
} else if (root.left && !root.right) {
// 待删除的节点右子树为空，让待删除节点的左子树替代自己。
root = root.left
} else if (!root.left && root.right) {
// 待删除的节点左子树为空，让待删除节点的右子树替代自己。
root = root.right
} else if (root.left && root.right) {
// 如果待删除的节点的左右子树都不为空。我们需要找到比当前节点小的最大节点（前驱）来替换自己
let last = root.left
while (last.right) {
last = last.left
}
// 最终的last就是比当前节点小的最大节点，将值进行替换
root.val = last.val
// 删除该最大节点
root.left = removeNode(root.left, last.val)
}
}
return root
}