Tree
It is used to tackle many recurring challenges in software development, such as:
representing hierarchical relationships
managing sorted data
facilitating fast lookup operations
Node
Like the linked list, trees are made up of nodes.
class TreeNode<T> {
var value: T
var children: [TreeNode] = []
init(value: T) {
self.value = value
}
func add(child: TreeNode<T>) {
children.append(child)
}
}
Parent & Child
Every child has only one parent.Root
The topmost node in the tree is called the root of the tree. It is the only node that has no parent.Leaf
A node is a leaf if it has no children
Traversal algorithms
Iterating through linear collections such as arrays or linked lists is straightforward. Linear collections have a clear start and end, iterating through trees is a bit more complicated.
Should nodes on the left have precedence? How should the depth of a node relate to its precedence? Your traversal strategy depends on the problem you’re trying to solve.
- Depth-first traversal
func forEachDepthFirst(visit: (TreeNode)->Void) {
visit(self)
children.forEach{ $0.forEachDepthFirst(visit: visit) }
}
- Level-order traversal
func forEachLevelOrder(visit: (TreeNode)->Void) {
visit(self)
var queue = ArrayQueue<TreeNode>()
children.forEach{ queue.enqueue(element: $0) }
while let node = queue.dequeue() {
visit(node)
node.children.forEach{ queue.enqueue(element: $0) }
}
}
-
Search
underlying Level-order, Depth-first traversal
func searchLevelOrder(value: T) -> TreeNode? {
var result: TreeNode?
forEachLevelOrder { node in
if node.value == value {
result = node
}
}
return result
}
func searchDepthFirst(value: T) -> TreeNode? {
var result: TreeNode?
forEachDepthFirst { node in
if node.value == value {
result = node
}
}
return result
}
If there are multiple matches, the last match will win.
Binary Tree
A binary tree is a tree where each node has at most two children, often referred to as the left and right children.
class BinaryNode<T> {
var value: T
var leftChild: BinaryNode?
var rightChild: BinaryNode?
init(value: T) {
self.value = value
}
}
you’ll look at three traversal algorithms for binary trees: in-order, pre-order, and post-order traversals.
Pre-order traversal 前序
Pre-order traversal always visits the current node first, then recursively visits the left and right child.
func traversePreOrder(visit: (T)->Void) {
visit(value)
leftChild?.traversePreOrder(visit: visit)
rightChild?.traversePreOrder(visit: visit)
}
In-order traversal 中序
- If the current node has a left child, recursively visit this child first.
- Then visit the node itself.
- If the current node has a right child, recursively visit this child.
This prints the tree in ascending order.
func traverseInOrder(visit: (T)->Void) {
leftChild?.traverseInOrder(visit: visit)
visit(value)
rightChild?.traverseInOrder(visit: visit)
}
Post-order traversal 后序
Post-order traversal only visits the current node after the left and right child have been visited recursively.
func traversePostOrder(visit: (T)->Void) {
leftChild?.traversePostOrder(visit: visit)
rightChild?.traversePostOrder(visit: visit)
visit(value)
}
In other words, given any node, you’ll visit its children before visiting itself. An interesting consequence of this is that the root node is always visited last.
Binary Search Tree (BST)
A binary search tree (or BST) is a data structure that facilitates fast lookup, addition, and removal operations.
Each operation has an average time complexity of O(log n), which is considerably faster than linear data structures such as arrays and linked lists.
A binary search tree achieves this performance by imposing two rules on the binary tree:
- The value of a left child must be less than the value of its parent.
- The value of a right child must be greater than or equal to the value of its parent.
Picking a side forfeits all the possibilities of the other side. Binary search trees use this property to save you from performing unnecessary checking.
Lookup
Every time the search algorithm visits a node in the BST, it can safely make these two assumptions:
- If the search value is less than the current value, it must be in the left subtree.
- If the search value value is greater than the current value, it must be in the right subtree.
By leveraging the rules of the BST, you can avoid unnecessary checks and cut the search space in half every time you make a decision. That’s why element lookup in a BST is an O(log n) operation.
Insertion
You only needed to make three traversals to find the location for the insertion, and you didn’t have to shuffle all the elements around! Inserting elements in a BST is again an O(log n) operation.
Removal
There are complications to manage when the node you’re removing has children.Even with those complications, removing an element from a BST is still an O(log n) operation.
Binary search trees drastically reduce the number of steps for add, remove, and lookup operations.
Inserting elements
In accordance with the rules of the BST, nodes of the left child must contain values less than the current node. Nodes of the right child must contain values greater than or equal to the current node.
struct BinarySearchTree<T: Comparable> {
private(set) var root: BinaryNode<T>?
init(){}
}
extension BinarySearchTree {
mutating func insert(value: T) {
root = _insert(from: root, value: value)
}
private mutating func _insert(from node: BinaryNode<T>?, value: T) -> BinaryNode<T> {
guard let node = node else {
return .init(value: value)
}
if value < node.value {
node.leftChild = _insert(from: node.leftChild, value: value)
}
else {
node.rightChild = _insert(from: node.rightChild, value: value)
}
return node
}
}
extension BinarySearchTree: CustomStringConvertible {
var description: String {
root?.description ?? "empty tree"
}
}
var bst = BinarySearchTree<Int>()
[7,1,9,0,5,8].forEach{ bst.insert(value: $0) }
print(bst)
An unbalanced tree affects performance. If you insert 5 into the unbalanced tree you’ve created, it becomes an O(n) operation.
Finding elements
Implement with traversal algorithm:
func contains(_ value: T) -> Bool {
var found = false
root?.traverseInOrder{
if value == $0 {
found = true
}
}
return found
}
In-order traversal has a time complexity of O(n), thus this implementation of contains has the same time complexity as an exhaustive search through an unsorted array.
But you can rely on the rules of the BST to avoid needless comparisons:
func contains(_ value: T) -> Bool {
var found = root
while let node = found {
if value == node.value {
return true
}
if value < node.value {
found = node.leftChild
} else {
found = node.rightChild
}
}
return false
}
Here’s how this works:
- Start off by setting current to the root node.
- While current is not nil, check the current node’s value.
- If the value is equal to what you’re trying to find, return true.
- Otherwise, decide whether you’re going to check the left or the
right child.
In a balanced binary search tree, this implementation of contains is
an O(log n) operation.
Removing elements
Removing a leaf node is straightforward, Simply detaching the leaf node is enough.
When removing nodes with one child, you’ll need to reconnect that
one child with the rest of the tree.When removing a node with two children, replace the node you removed with smallest node in its right subtree. Based on the rules of the BST, this is the leftmost node of the right subtree.
It’s important to note that this produces a valid binary search tree. Because the new node was the smallest node in the right subtree, all nodes in the right subtree will still be greater than or equal to the new node. And because the new node came from the right subtree, all nodes in the left subtree will be less than the new node.
After performing the swap, you can simply remove the value you copied, which is just a leaf node.
extension BinaryNode {
var min: BinaryNode {
leftChild?.min ?? self
}
var isLeaf: Bool {
leftChild == nil && rightChild == nil
}
}
mutating func remove(_ value: T) {
root = _remove(from: root, value: value)
}
private mutating func _remove(from node: BinaryNode<T>?, value: T) -> BinaryNode<T>? {
guard let node = node else {
return nil
}
// if found the node of `value`, handle removal
if value == node.value {
if node.isLeaf {
return nil
}
if node.leftChild == nil {
return node.rightChild
}
if node.rightChild == nil {
return node.leftChild
}
// 1. swap the value with the min value of node in right subtree
node.value = node.rightChild!.min.value
// 2. remove the node with min value in right subtree
node.rightChild = _remove(from: node.rightChild, value: node.value)
}
// else continue to find the left or right child's children nodes
else if value < node.value {
node.leftChild = _remove(from: node.leftChild, value: value)
} else {
node.rightChild = _remove(from: node.rightChild, value: value)
}
return node
}
var bst = BinarySearchTree<Int>()
[3,1,5,4,7,6,8].forEach{ bst.insert(value: $0) }
print(bst)
print(bst.remove(5))
print(bst)
The BST is a powerful data structure that can delivers great performance when managing sorted data.
AVL Tree
In 1962, Georgy Adelson-Velsky and Evgenii Landis came up with the first self-balancing binary search tree: the AVL Tree.
The three main states of balance:
-
Perfect balance
The ideal form of a binary search tree is the perfectly balanced state. In technical terms, this means every level of the tree is filled with nodes, from top to bottom.
Not only is the tree perfectly symmetrical, the nodes at the bottom level are completely filled. This is the requirement for being perfectly balanced.
-
"Good-enough" balance
A perfectly balanced tree has to contain the exact number of nodes to fill every level to the bottom, so it can only be perfect with a particular number of elements.
As an example, a tree with 1, 3, or 7 nodes can be perfectly balanced, but a tree with 2, 4, 5, or 6 cannot be perfectly balanced, since the last level of the tree will not be filled.
-
Unbalanced
Binary search trees in this state suffer from various levels of performance loss, depending on the degree of imbalance.
AVL trees maintain balance by adjusting the structure of the tree when the tree becomes unbalanced.
Binary search trees and AVL trees share much of the same implementation;
Measuring balance
This is a balanced tree, where all levels except the bottom one are filled.
A balanceFactor of 2 or -2 is an indication of an unbalanced tree.
The AVL tree achieves this with a height property in each node. In tree-speak, the height of a node is the longest distance from the current node to a leaf node.
You’ll use the relative heights of a node’s children to determine
whether a particular node is balanced.
The height of the left and right children of each node must differ by at most 1. This is known as the balance factor.
The balanceFactor computes the height difference of the left and right child. If a particular child is nil, its height is considered to be -1.
Although more than one node may have a bad balancing factor, you only need to perform the balancing procedure on the bottom-most node containing the invalid balance factor.
Rotations
The procedures used to balance a binary search tree are known as rotations. There are four rotations in total, for the four different ways that a tree can become unbalanced. These are known as left rotation, left-right rotation, right rotation, and right-left rotation.
- Left rotation
When a series of right children is causing an imbalance, it’s time for a left rotation.
func leftRotate(node: AVLNode<T>) -> AVLNode<T> {
let pivot = node.rightChild!
node.rightChild = pivot.leftChild
pivot.leftChild = node
node.height = max(node.leftHeight, node.rightHeight) + 1
pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
return pivot
}
-
The right child is chosen as the pivot. This node will replace the
rotated node as the root of the subtree (it will move up a level). -
The node to be rotated will become the left child of the pivot (it moves down a level). This means the current left child of the
pivot must be moved elsewhere.
In the generic example shown in the earlier image, this is node b.
Because b is smaller than y but greater than x, it can replace y as
the right child of x. So you update the rotated node’s rightChild
to the pivot’s leftChild. - The pivot’s leftChild can now be set to the rotated node.
- You update the heights of the rotated node and the pivot.
- Finally, you return the pivot so it can replace the rotated node in
the tree.
- Right rotation
Right rotation is the symmetrical opposite of left rotation. When a series of left children is causing an imbalance, it’s time for a right rotation.
func rightRotate(node: AVLNode<T>) -> AVLNode<T> {
let pivot = node.leftChild!
node.leftChild = pivot.rightChild
pivot.rightChild = node // the key step
node.height = max(node.leftHeight, node.rightHeight) + 1 // level up
pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1 // level down
return pivot
}
- Right-left rotation
You may have noticed that the left and right rotations balance nodes that are all left children or all right children.
Doing a left rotation in this case won’t result in a balanced tree. The way to handle cases like this is to perform a right rotation on the right child before doing the left rotation.
func rightLeftRotate(node: AVLNode<T>) -> AVLNode<T> {
guard let rightChild = node.rightChild else {
return node
}
node.rightChild = rightRotate(node: rightChild)
return leftRotate(node: node)
}
- Left-right rotation
func leftRightRotate(node: AVLNode<T>) -> AVLNode<T> {
guard let leftChild = node.leftChild else {
return node
}
node.leftChild = leftRotate(node: leftChild)
return rightRotate(node: node)
}
Balance
Design a method that uses balanceFactor to decide whether a node requires balancing or not.
func balanced(for node: AVLNode<T>) -> AVLNode<T> {
switch node.balanceFactor {
case 2: // lean to `right`, should rotate to `right` or make `left-right` rotation
if let leftChild = node.leftChild, leftChild.balanceFactor == -1 { // only left child
return leftRightRotate(node: node)
} else {
return rightRotate(node: node)
}
case -2: // lean to `left`, should rotate to `left` or make `right-left` rotation
if let rightChild = node.rightChild, rightChild.balanceFactor == 1 { // only right child
return rightLeftRotate(node: node)
} else {
return leftRotate(node: node)
}
default:
return node
}
}
- A balanceFactor of 2 suggests that the left child is “heavier”
(that is, contains more nodes) than the right child. This means
you want to use either right or left-right rotations. - A balanceFactor of -2 suggests that the right child is heavier
than the left child. This means you want to use either left or
right-left rotations. - The default case suggests that the particular node is balanced.
There’s nothing to do here except to return the node.
The balanceFactor to determine the proper course of action.
Revisiting insert
private mutating func _insert(from node: AVLNode<T>?, value: T) -> AVLNode<T> {
guard let node = node else {
return .init(value: value)
}
if value < node.value {
node.leftChild = _insert(from: node.leftChild, value: value)
}
else {
node.rightChild = _insert(from: node.rightChild, value: value)
}
let balancedNode = balanced(for: node)
balancedNode.height = max(balancedNode.leftHeight, balancedNode.rightHeight)
return balancedNode
}
Instead of returning the node directly after inserting, you pass it into balanced. This ensures every node in the call stack is checked for balancing issues. You also update the node’s height.
Revisiting remove
Just rebalance the root node before remove.
let balancedNode = balanced(node)
balancedNode.height = max(balancedNode.leftHeight, balanced
return balancedNode
The self-balancing property guarantees that the insert and remove operations function at optimal performance with an O(log n) time complexity.
While AVL trees were the first self-balancing implementations of a BST, others, such as the red-black tree and splay tree(伸展树), have since joined the party. If you’re interested, you check those out in the Swift Algorithm Club. Find them at at:
