群组
Flutter,iOS,Android,Python等,闲聊工作&技术&问题;
个人主页:https://waitwalker.cn
telegram群链接:https://t.me/joinchat/Ej0o0A1ntlq5ZFIMzzO5Pw
二叉查找树定义
二叉搜索树也叫二叉查找树(Binary Search Tree)是二叉树的一个类型.二叉搜索树具有以下性质:
1)若任意节点的左子树不空,则左子树上所有节点的值均小于它根节点的值;
2)若任意节点的右子树不空,则右子树上所有节点的值均大于它根节点的值;
3)任意节点的左右子树也分别为二叉查找树;
4)没有键值相等的节点.
二叉查找树相比去其他数据结构的优势在于查找,插入的时间复杂度较低,为O(logn).二叉查找树是基础数据结构,长用于构建更为抽象的数据结构,如集合,关联数组等.搜索,插入,删除的复杂度等于树高,期望O(logn),最坏O(n),虽然二叉查找树的最坏效率是O(n),但它支持动态查询,而且一些改进版的二叉查找树可以使树高为O(logn),从而将最坏效率将至O(logn),如AVL树,红黑树等.
二叉查找树的存储结构常用二叉链表来构建.
二叉查找树实现
这里二叉查找树的存储结构我们用的是上一节定义的二叉树.
// MARK: - 二叉查找树
class BinarySearchTree<T:Comparable> {
private(set) var root:BinaryTree<T>?
// MARK: - 构造函数
init() {
}
}
查找
查找逻辑:
1)从根节点开始查找,如果待查找的值等于根节点的值,直接返回;
2)如果待查找的值小于根节点的值,则在根节点的左子树执行查找;
3)如果待查找的值大于根节点的值,则在根节点的右子树执行查找;
4)递归执行以上步骤
/// 查找例程
///
/// - Parameter value: 待查找的值
/// - Returns: 查找到的值
func find(value:T) -> BinaryTree<T>? {
guard let node = binaryTree else { return nil }
if node.value == value {
return node
} else if value < node.value {
return find(binaryTree: node.leftChildNode, value: value)
} else {
return find(binaryTree: node.rightChildNode, value: value)
}
}
在我们的示例中,查找128:
数组需要对整个列表进行查找,逐个元素比较128是否相等;
二叉搜索树则先比较和根元素120比较,128比120大,则在120的右子树查找,然后找到130,128比130小,则在130的左子树找,最终找到.
插入
插入逻辑:
1)先创建一个新节点,如果新节点的值与根节点的值相等,则插入到根节点位置;
2)如果新节点的值小于等于根节点的值,则将新节点赋值给根节点的左子树;
3)如果新节点的值大于根节点的值,则将新节点赋值给根节点的右子树;
4)递归执行以上步骤.
/// 插入例程
///
/// - Parameter value: 插入的值
/// - Returns: 插入后返回的二叉查找树
func insert(value:T) -> Void {
root = insert(root: root, value: value)
}
private func insert(root binaryTree:BinaryTree<T>?, value:T) -> BinaryTree<T>? {
guard let node = binaryTree else { return BinaryTree(value: value) }
if value <= node.value {
node.leftChildNode = insert(root: node.leftChildNode, value: value)
} else {
node.rightChildNode = insert(root: node.rightChildNode, value: value)
}
return node
}
删除
删除逻辑:
1)删除的节点是叶子节点,直接删除;
2)删除的节点只有一个儿子,则将其儿子赋值给当前节点
3)删除的节点有两个儿子,则需要将此节点替换为左子树最大的子节点或者右子树最小子节点
func delete(value:T) -> Void {
root = delete(binaryTree: root, value: value)
}
private func delete(binaryTree:BinaryTree<T>?, value:T) -> BinaryTree<T>? {
guard let node = binaryTree else { return nil }
if node.value == value {
// 左右节点都为空
if node.leftChildNode == nil && node.rightChildNode == nil {
return nil
}
// 左右节点有一个为空
if node.leftChildNode == nil {
return node.rightChildNode
}
if node.rightChildNode == nil {
return node.leftChildNode
}
// 左右节点都不为空
// 将左子树中最小的节点赋值给当前节点
node.value = (node.rightChildNode?.minNode.value)!
// 删除右子树中最小节点
node.rightChildNode = delete(binaryTree: node.rightChildNode, value: node.value)
} else if value < node.value {
node.leftChildNode = delete(binaryTree: node.leftChildNode, value: value)
} else {
node.rightChildNode = delete(binaryTree: node.rightChildNode, value: value)
}
return node
}
最小值
最小值一直遍历二叉搜索树的左子树,直到左子树为空.
/// 最小值
///
/// - Returns: 最小值节点
func min() -> BinaryTree<T>? {
guard let node = root else { return nil }
var tmp = node
while tmp.leftChildNode != nil {
tmp = tmp.leftChildNode!
}
return tmp
}
最大值
最大值一直遍历二叉搜索树右子树,直到右子树为空
/// 最大值
///
/// - Returns: 最大值节点
func max() -> BinaryTree<T>? {
guard let node = root else { return nil }
var tmp = node
while tmp.rightChildNode != nil {
tmp = node.rightChildNode!
}
return tmp
}
源码地址
这里的实现代码已放到GitHub,测试用例详见DataStructureAlgorithmTests.swift文件
参考文献
《数据结构与算法分析C语言描述》(Data Structures and Algorithm Analysis in C:Second Edition)–译者: 冯舜玺
https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9
