introduce
Binary search tree is a special binary tree. Binary search trees have the following features:
-
The value of the left child node is less than that of the parent node;
-
The value of the child node on the right is greater than or equal to the parent node
For example:
Because of these features, binary search tree can greatly improve the performance of search, add and delete operations of sorted data, and the time complexity is O(log n).
implementation
The code implementation is added on the basis of a binary tree.
Here is the complete code for the previous binary tree implementation:
class BinaryNode<Element> {
var value: Element
var leftChild: BinaryNode? // 左节点
var rightChild: BinaryNode? // 右节点
init(value: Element) {
self.value = value
}
}
extension BinaryNode {
func traverseInOrder(visit: (Element) -> Void) {
leftChild?.traverseInOrder(visit: visit)
visit(value)
rightChild?.traverseInOrder(visit: visit)
}
func traversePreOrder(visit: (Element) -> Void) {
visit(value)
leftChild?.traversePreOrder(visit: visit)
rightChild?.traversePreOrder(visit: visit)
}
func traversePostOrder(visit: (Element) -> Void) {
leftChild?.traversePostOrder(visit: visit)
rightChild?.traversePostOrder(visit: visit)
visit(value)
}
}
extension BinaryNode {
// O(n)
var height: Int {
if leftChild == nil && rightChild == nil { return 0 }
return 1 + max(leftChild?.height ?? 0, rightChild?.height ?? 0)
}
}
extension BinaryNode: CustomStringConvertible {
public var description: String {
diagram(for: self)
}
private func diagram(for node: BinaryNode?,
_ top: String = "",
_ root: String = "",
_ bottom: String = "") -> String {
guard let node = node else {
return root + "nil\n"
}
if node.leftChild == nil && node.rightChild == nil {
return root + "\(node.value)\n"
}
return diagram(for: node.rightChild,
top + " ", top + "┌──", top + "│ ")
+ root + "\(node.value)\n"
+ diagram(for: node.leftChild,
bottom + "│ ", bottom + "└──", bottom + " ")
}
}
Copy the codeNode is inserted into the
Since the value of the left node of the binary search tree is smaller than the value of the right node, each comparison is made by comparing the value of the left and right nodes of the nodes to be inserted, and then recursive comparison is completed until the location of the node to be added is found.
Binary search tree basic code:
struct BinarySearchTree<Element: Comparable> {
var root: BinaryNode<Element>?
}
extension BinarySearchTree: CustomStringConvertible {
var description: String {
guard let root = root else {
return "empty tree"
}
return String(describing: root)
}
}
Copy the codeImplementation code:
extension BinarySearchTree { mutating func insert(_ value: Element) { root = insert(from: root, value: value) } private func insert(from node: BinaryNode<Element>? , value: Element) -> BinaryNode<Element>? Guard let node = node else {return BinaryNode(value: value) {return BinaryNode(value: value); Value)} if value < node.value {// Update node.leftChild = insert(from: node. RightChild = insert(from: node.rightChild, value: value)} return node}}Copy the codeIt can be seen that the insertion operation compares the data on one side each time, and the time complexity is O(log n). If it is an insertion of an array data structure, all elements after the insertion position need to be moved one bit later, and the time complexity is O(n).
Test insert operation:
func insertTest() { var tree = BinarySearchTree<Int>() tree.insert(5) tree.insert(2) tree.insert(3) tree.insert(0) Insert (5) print("before inserting:") print(inserting) tree.insert("after inserting:") print(inserting) tree.insert("after inserting:") print(tree) }Copy the codeOutput;
8 ┌ before inserting: ┌ ─ ─ ─ ─ seven │ └ ─ ─ nil 5 │ ┌ ─ ─ 3 └ ─ ─ 2 └ ─ ─ 0 after inserting: ┌ ─ ─ eight ┌ ─ ─ seven │ └ ─ ─ 5 6 │ ┌ ─ ─ 3 └ ─ ─ 2 └ ─ ─ 0Copy the codeNodes in the query
An immediate solution to checking the existence of a node is to traverse all nodes and see if it can be found. Such as:
extension BinarySearchTree {
func contains(_ value: Element) -> Bool {
guard let root = root else {
return false
}
var found = false
// O(n)
root.traverseInOrder { node in
if node == value {
found = true
}
}
return found
}
}
Copy the codeBut this is an O(n) operation.
The optimized code implementation using binary search tree features looks like this:
extension BinarySearchTree {
func contains(_ value: Element) -> Bool {
var current = root
// O(log n)
while let node = current {
if node.value == value {
return true
}
if value < node.value {
current = node.leftChild
} else {
current = node.rightChild
}
}
return false
}
}
Copy the codeThe node to delete
Deleting a node is more complex than inserting and querying, considering the following.
- This node is a leaf node
This is easy to delete, so just delete it.
- This node has one child node
The solution is for the child node to replace the original node position.
- This node has two children
According to the characteristics of binary search tree, the node with the smallest position on the right node is moved to replace the position of the node to be deleted, and then the original minimum node is deleted.
Such as:
To delete node 1, replace the value of node 2 to node 1, and then delete node 2 so that the binary search tree remains a binary search tree after the node is deleted.
Code implementation:
Var min: BinaryNode {leftChild? .min ?? self } } extension BinarySearchTree { mutating func remove(_ value: Element) { root = remove(node: root, value: value) } private func remove(node: BinaryNode<Element>? , value: Element) -> BinaryNode<Element>? {guard let node = node else {return nil} if value == node.value {// leaf node if Node. leftChild == nil && node.rightChild == nil {return nil} // Only one right node if node.leftChild == nil {return node.rightChild} // Only one left node if node.rightChild == Nil {return node.leftChild} // There are two child nodes, replace the position, delete the smallest node in the tree after the replacement node.value = Node.rightChild! .min.value node.rightChild = remove(node: node.rightChild, value: node.value) } else if value < node.value { node.leftChild = remove(node: node.leftChild, value: value) } else { node.rightChild = remove(node: node.rightChild, value: value) } return node } }Copy the codepractice
LeetCode- Validate binary search tree
Given a binary tree, determine whether it is a valid binary search tree.
Suppose a binary search tree has the following characteristics:
The left subtree of a node contains only numbers less than the current node.
The right subtree of a node only contains numbers greater than the current node.
All left and right subtrees must themselves also be binary search trees.
Implementation code:
extension BinaryNode where Element: Comparable { var isBinarySearchTree: Bool { return isBST(self, min: nil, max: nil) } private func isBST(_ tree: BinaryNode<Element>? , min: Element? , max: Element?) -> Bool { guard let tree = tree else { return true } if let min = min, min >= tree.value { return false } else if let max = max, max < tree.value { return false } return isBST(tree.leftChild, min: min, max: tree.value) && isBST(tree.rightChild, min: tree.value, max: max) } }Copy the codeSupplementary binary search
As mentioned earlier, the query operation time for an element in an array is order n. But if the array is already sorted, the query can actually be binary search, and the time of the query operation is order log n.
The idea is:
- Find the intermediate coordinates;
- Compare whether the values of the intermediate coordinates are equal. If so, return the coordinates; otherwise, go to Step 3.
- Recursive binary search, which compares the size of the query value with the middle coordinate value, if less than the middle coordinate value, the search starts from the left range, otherwise from the right range.
The following is the implementation of binary search:
extension RandomAccessCollection where Element: Comparable { // O(log n) func binarySearch(for value: Element, in range: Range<Index>? = nil) -> Index? {// let range = range?? startIndex.. <endIndex guard range.lowerBound < range.upperBound else { return nil } let size = distance(from: range.lowerBound, to: range.upperBound) let middle = index(range.lowerBound, offsetBy: If self[middle] == value {return middle} else if self[middle] > value {// recursive, Return binarySearch(for: value, in: range.lowerbound.. <middle)} else {return binarySearch(for: value, in: middle.. <range.upperBound) } } }Copy the codeTesting:
class ViewController: UIViewController { override func viewDidLoad() { super.viewDidLoad() let items = [1, 4, 5, 9, 21, 35, 40, 100, 200, 230, 300] let search100 = items.firstIndex(of: 100) // Let binarySearch100 = items.firstIndex(of: 100) O(log n) print("search100 = \(String(describing: search100))") print("binarySearch100 = \(String(describing: binarySearch100))") } }Copy the codeOutput:
search100 = Optional(7)
binarySearch100 = Optional(7)
Copy the code