二叉查找树(英语:Binary Search Tree),也称为二叉查找树、有序二叉树(ordered binary tree)或排序二叉树(sorted binary tree)
他拥有以下性质:
图中的二叉树就是一颗二叉查找树
const nodes = { value: 6, left: { value: 3, left: { value: 1, left: { value: 0 }, right: { value: 2 } }, right: { value: 5 } }, right: { value: 8, left: { value: 7 }, right: { value: 9 } } }
在二叉查找树b中查找x的过程为:
const SearchBST = (tree, value) => { if (!tree) { return false } if (value === tree.value) { return tree } if (value < tree.value) { return SearchBST(tree.left, value) } return SearchBST(tree.right, value) }
向一个二叉查找树b中插入一个节点s的算法,过程为:
const InsertBST = (tree, value, parent, key) => { if (!tree) { parent[key] = { value } return true } if (tree.value === value) { return false } if (tree.value > value) { return InsertBST(tree.left, value, tree, 'left') } return InsertBST(tree.right, value, tree, 'right') }
相比较其他算法, JS 的实现感觉有些不足
二叉搜索树的节点删除包括两个过程,查找和删除。
在二叉查找树删去一个结点,分三种情况讨论:
节点度可以看成分支数
const DeleteBST = (root, value) => { if (!root) { return false } if (root.value === value) { return DELETE(root) } if (root.value > value) { return DeleteBST(root.left, value, root, 'left') } return DeleteBST(root.right, value, root, 'left') } const DELETE = (root, parent, key) => { // 在这里实现三种情况 // 情况 1 没有左右子节点 可直接删除 if (!root.left && !root.right) { parent[key] = null return true } // 情况 2 只有一个子节点 重新连接即可 if (!root.right) { const q = root.left root.value = q.value root.left = q.left root.right = q.right return true } if (!root.left) { const p = root.right root.value = p.value root.left = p.left root.right = p.right return true } // 情况 3 // 删除节点后,为了维持二叉搜索树的结构特性,需要从其左子树中选出一个最大值的节点,“上移”到删除的节点位置上 let temp = root let l = root.left while (l.right) { temp = l l = l.right } root.value = l.value if (root != temp) { temp.right = l.left } else { temp.left = l.left } return true }
虽然二叉查找树的最坏效率是O(n),但它支持动态查询,且有很多改进版的二叉查找树可以使树高为O(log n),从而将最坏效率降至O(log n),如AVL树、红黑树等。
二叉查找树它既有链表的快速插入与删除操作的特点,又有数组快速查找的优势,应用十分广泛,例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作
仓库地址: https://github.com/Grewer/notes
参考: