A tree (Trees)

The tree

A tree represents a hierarchical relationship between objects

public class TreeNode<T> {
  public var value: T
  
  public weak var parent: TreeNode?
  public var children = [TreeNode<T>] ()public init(value: T) {
    self.value = value
  }
  
  public func addChild(_ node: TreeNode<T>) {
    children.append(node)
    node.parent = self}}Copy the code

Add the description method so that you can print 🌲

extension TreeNode: CustomStringConvertible {
  public var description: String {
    var s = "\(value)"
    if !children.isEmpty {
      s + = "{" + chilren.map {$0.description}.joined(separator:").") +"}" } return s } }Copy the code

Create a tree

let tree = TreeNode<String>(value: "beverages")

let hotNode = TreeNode<String>(value: "hot")
let coldNode = TreeNode<String>(value: "cold")

let teaNode = TreeNode<String>(value: "tea")
let coffeeNode = TreeNode<String>(value: "coffee")
let chocolateNode = TreeNode<String>(value: "cocoa")

let blackTeaNode = TreeNode<String>(value: "black")
let greenTeaNode = TreeNode<String>(value: "green")
let chaiTeaNode = TreeNode<String>(value: "chai")

let sodaNode = TreeNode<String>(value: "soda")
let milkNode = TreeNode<String>(value: "milk")

let gingerAleNode = TreeNode<String>(value: "ginger ale")
let bitterLemonNode = TreeNode<String>(value: "bitter lemon")

tree.addChild(hotNode)
tree.addChild(coldNode)

hotNode.addChild(teaNode)
hotNode.addChild(coffeeNode)
hotNode.addChild(chocolateNode)

coldNode.addChild(sodaNode)
coldNode.addChild(milkNode)

teaNode.addChild(blackTeaNode)
teaNode.addChild(greenTeaNode)
teaNode.addChild(chaiTeaNode)

sodaNode.addChild(gingerAleNode)
sodaNode.addChild(bitterLemonNode)
Copy the code

  • Tree height: The number of connections between the root node and the lowest leaf node

  • Node depth: The number of connections between this node and the root node

Query whether the tree contains a particular value:

extension TreeNode where T: Equatable {
  func search(_ value: T) -> TreeNode? {
    if value = = self.value {
      return self
    }
    for child in children {
      if let found = child.search(value) {
        return found
      }
    }
    return nil}}Copy the code

Binary tree

public indirect enum BinaryTree<T> {
  case node(BinaryTree<T>, T.BinaryTree<T>)
	case empty
}
Copy the code
// leaf nodes
let node5 = BinaryTree.node(.empty, "5", .empty)
let nodeA = BinaryTree.node(.empty, "a", .empty)
let node10 = BinaryTree.node(.empty, "10", .empty)
let node4 = BinaryTree.node(.empty, "4", .empty)
let node3 = BinaryTree.node(.empty, "3", .empty)
let nodeB = BinaryTree.node(.empty, "b", .empty)

// intermediate nodes on the left
let Aminus10 = BinaryTree.node(nodeA, "-", node10)
let timesLeft = BinaryTee.node(node5, "*".Aminus10)

// intermediate nodes on the right
let minus4 = BinaryTree.node(.empty, "-", node4)
let divide3andB = BinaryTree.node(node3, "/", nodeB)
let timesRight = BinaryTree.node(minus4, "*", divide3andB)

// root node
let tree = BinaryTree.node(timesLeft, "+", timesRight)
Copy the code

Add the description method

extension BinaryTree: CustomStringConvertible {
  public var description: String {
    switch self {
      case let .node(left, value, right):
      	return "value: \(value), left = [\(left.description)], right = [\(right.description)]. ""
      case .empty:
      	return ""}}}Copy the code

Count the number of nodes in the tree

public var count: Int {
  switch self {
    case let .node(left, _, right):
    	return left.count + 1 + right.count
    case .empty:
    	return 0}}Copy the code

Traversal sequence

  1. Middle-order (or depth-first) : look at the left child of A node first, then the node itself, and finally the right child of the node (such as A + B)
  2. Preorder: First look at the node itself, then its left and right byte points (e.g. + A B)
  3. After: first look at the left and right child nodes, then the node itself (such as A, B +)
public func traverseInOrder(process: (T) - >Void) {
  if case let .node(left, value, right) = self {
    left.traversePreOrder(process: process)
    process(value)
    right.traverseInOrder(precess: process)
  }
}

public func traversePreOrder(process: (T) - >Void) {
  if case let .node(left, value, right) = self {
    process(value)
    left.traversePreOrder(process: process)
    right.traversePreOrder(process: process)
  }
}

public func tranversePostOrder(process: (T) - >Void) {
  if case let .node(left, value, right) = self {
    left.traversePostOrder(process: process)
    right.traversePostOrder(process: process)
    process(value)
  }
}
Copy the code

Binary search tree

Each left node is smaller than the parent and each right node is larger than the parent

public class BinarySearchTree<T: Comparable> {
  private(set) public var value: T
  private(set) public var parent: BinarySearchTree?
  private(set) public var left: BinarySearchTree?
  private(set) public var right: BinarySearchTree?
  
  public init(value: T) {
    self.value = value
  }
  
  public var isRoot: Bool {
    return parent = = nil
  }
  
  public var isLeaf: Bool {
    return left = = nil && right = = nil
  }
  
  public var isLeftChild: Bool {
    return parent?.left = = self
  }
  
  public var isRightChild: Bool {
    return parent?.right = = self
  }
  
  public var hasLeftChild: Bool {
    return left ! = nil
  }
  
  public var hasRightChild: Bool {
    return right ! = nil
  }
  
  public var hasAnyChild: Bool {
    return hasLeftChild || hasRightChild
  }
  
  public var hasBothChildren: Bool {
    return hasLeftChild && hasRightChild
  }
  
  public var count: Int {
    return (left?.count ?? 0) + 1 + (right?.count ?? 0)}}Copy the code

Insert the node

public func insert(value: T) {
  if value < self.value {
    if let left = left {
      left.insert(value: value)
    } else {
      left = BinarySearchTree(value: value)
      left?.parent = self}}else {
    if let right = right {
      right.insert(value: value)
    } else {
      right = BinarySearchTree(value: value)
      right?.parent = self}}}Copy the code

For convenience, we add a method that initializes as an array

public convenience init(array: [T]) {
  precondition(array.count > 0)
  self.init(value: arrat.first!)
  for v in array.dropFirst() {
    insert(value: v)
  }
}
Copy the code

search

public func search(value: T) -> BinarySearchTree? {
  if value < self.value {
    return left?.search(value)
  } else if value > self.value {
    return right?.search(value)
  } else {
    return self   // found it!}}Copy the code

The version of the iteration implementation

public func search(_ value: T) -> BinarySearchTree? {
  var node: BinarySearchTree? = self
  while let n = node {
    if value < n.value {
      node = n.left
    } else if value > n.value {
      node = n.right
    } else {
      return node
    }
  }
  return nil
}
Copy the code

traverse

public func traverseInOrder(process: (T) - >Void) {
  left?.traverseInOrder(process: process)
  process(value)
  right?.traverseInOrder(process: process)
}

public func traversePreOrder(process: (T) - >Void) {
  process(value)
  left?.traversePreOrder(process: process)
  right.traversePreOrder(process: process)
}

public func traversePostOrder(process: (T) - >Void) {
  left?.traversePostOrder(process: process)
  right?.traversePostOrder(process: process)
  process(value)
}
Copy the code

Tree map implementation

public func map(formula: (T) - >T)- > [T] {
  var a = [T] ()if let left = left { a + = left.map(formula: formula) }
  a.append(formula(value))
  if let right = right { a + = right.map(formula: fomula) }
  return a
}
Copy the code

Changing the parent node

private func reconectParentTo(node: BinarySearchTree?). {
  if let parent = parent {
    if isLeftChild {
      parent.left = node
  	} else {
    	parent.right = node
    }
  }
  node?.parent = parent
}
Copy the code

Minimum && maximum

public func minimum(a) -> BinarySearchTree {
  var node = self
  while let next = node.left {
    node = next
  }
  return node
}

public func maximum(a) -> BinarySearchTree {
  var node = self
  while let next = node.right {
    node = next
  }
  return node
}
Copy the code

Remove nodes

@discardableResult public func remove(a) -> BinarySearchTree? {
  let replacement: BinarySearchTree?
  
  // Replacement for current node can be either bigest one on the left or
  // smallest one on the right, whichever is not nil
  if let right = right {
    replacement = right.minimum()
  } else if let left = left {
    replacement = left.maximum()
  } else {
    replacement = nil
  }
  
  replacement?.remove()
  
  // Place the replacement on current node's position
  replacement?.right = right
  replacement?.left = left
  right?.parent = replacement
  left?.parent = replacement
  reconnectParentTo(node: replacement)
  
  // The current node is no longer part of the tree, so clean it up
  parent = nil
  left = nil
  right = nil
  
  return replacement
}
Copy the code

highly

public func height(a) -> Int {
  if isLeaf {
    return 0
  } else {
    return 1 + max(left?.height() ?? 0, right?.height() ?? 0)}}Copy the code

Node depth

public func depth(a) -> Int {
  var node = self
  var edges = 0
  while let parent = node.parent {
    node = parent
    edges + = 1
  }
  return edges
}
Copy the code

Precursor node

public func predecessor(a) -> BinarySearchTree<T>? {
  if let left = left {
    return left.maximum()
  } else {
    var node = self
    while let parent = node.parent {
      if parent.value < value { return partent }
      node = parent
    }
    return nil}}Copy the code

The subsequent nodes

public func successor(a) -> BinarySearchTree<T>? {
  if let right = right {
    return right.minimum()
  } else {
    var node = self
    while let parent = node.parent {
      if parent.value > value { return parent }
    }
  }
}
Copy the code

Binary search tree is valid

public func isBST(minValue: T.maxValue: T) -> Bool {
  if value < minValue || value > maxValue { return false }
  let leftBST = left?.isBST(minValue: minValue, maxValue: value) ?? true
  let rightBST = right?.isBST(minValue: value, maxValue: maxValue) ?? true
  return leftBST && rightBST
}
Copy the code

Binary tree node implemented with enumeration

public enum BinarySearchTree<T: Comparable> {
  case Empty
  case Leaf(T)
  indirect case Node(BinarySearchTree.T.BinarySearchTree)}Copy the code
public var count: Int {
  switch self {
    case .Empty: return 0
    case .Leaf: return 1
    case let .Node(left, _, right): return left.count + 1 + right.count
  }
}

public var height: Int {
  switch self {
    case .Empty: return -1
    case .Leaf: return 0
    case let .Node(left, _, right): return 1 + max(left.height, right.height)
  }
}
Copy the code

Insert the node

public func insert(newValue: T) -> BinarySearchTree {
  switch self {
    case .Empty:
    	return .Leaf(newValue)
    
    case .Leaf(let value):
    	if newValue < value {
        return .Node(.Leaf(newValue), value, .Empty)}else {
        return .Node(.Empty.Value.Leaf(newValue))
      }
    
    case .Node(let left, let value, let right):
    	if newValue < value {
        return .Node(left.insert(newValue), value, right)
      } else {
        return .Node(left, value, right.insert(newValue))
      }
  }
}
Copy the code

The most important search method

public func search(x: T) -> BinarySearchTree? {
  switch self {
    case .Empty:
    	return nil
   	case .Leaf(let y):
    	return (x = y) ? self : nil
    case let .Node(left, y, right):
    	if x < y {
        return left.search(x)
      } else if y < x {
        return right.search(x)
      } else {
        return self}}}Copy the code

Red and black tree

features

  1. Each node is red or black
  2. The root node is black
  3. The leaves are black
  4. The children of the red node are black
  5. For each node, all paths from the node to the descendant leaf contain the same number of black nodes

Splay Tree

A stretchtree is a data structure that has the same structure as a balanced binary search tree. Each action performed in the stretch tree results in a readjustment to allow quick access to the most recently run values.

There are three types of rotations that can form Splaying

  • ZigZig
  • ZigZag
  • Zig

Clue binary tree

A clue binary tree is a special kind of binary tree that preserves some extra variables for inexpensive and fast in-order traversal.

An in-order traversal of a tree usually looks like this

func traverse(n: Node?). {
  if (n = = nil) { 
    return 
 	} else {
    traverse(n.left)
    visit(n)
    traverse(n.right)
  }
}
Copy the code

There are two types of line binary trees: single cue and double cue:

  • Order prefixes or suffixes in single-clue tree tracing
  • A double – clue tree tracks both prefixes and suffixes
func predecessor(a) -> ThreadedBinaryTree<T>? {
  if let left = left {
    return left.maximum()
  } else {
    return leftThread
  }
}

func successor(a) -> ThreadedBinaryTree<T>? {
	if let right = right {
    return right.minimum()
  } else {
    return rightThread
  }
}
Copy the code
public func traverseInOrderForward(_ visit: (T) - >Void) {
  var n: ThreadedBinaryTree
  n = minimum()
  while true {
    visit(n.value)
    if let successor = n.successor() {
      n = successor
    } else {
      break}}}public func traverseInOrderBackward(_ visit: (T) - >Void) {
  var n: ThreadedBinaryTree
  n = maximum()
  while true {
    visit(n.value)
    if let predecessor = n.predecessor() {
      n = predecessor
    } else {
      break}}}Copy the code

Line segment tree

The main idea of a segment tree is simple: we precompute some segment in the array, and then we can use it without recalculating

public class SegmentTree<T> {
  private var value: T
  private var function: (T.T) - >T
  private var leftBound: Int
  private var rightBoung: Int
  private var leftChild: SegmentTree<T>?
  private var rightChild: SegmentTree<T>?
}
Copy the code
public init(array: [T].leftBound: Int.rightBound: Int.function: @escping (T.T) - >T) {
  self.leftBound = leftBound
  self.rightBound = rightBound
  self.function = function
  
  if leftBound = = rightBound {
    value = array[leftBound]
  } else {
		let middle = (leftBound + rightBound) / 2
    
    leftChild = SegmentTree<T>(array: array, leftBound: leftBound, rightBound: middle, function: function)
    rightChild = SegmentTree<T>(array: array, leftBound: middle+1, rightBound: rightBound, function: function)
    
    value = function(leftChild!.value, rightChild!.value)
  }
}
Copy the code

The query results

public func query(withLeftBound leftBound: Int.rightBound: Int) -> T {
  if self.leftBound = = leftBound && self.rightBound = = rightBound {
    return self.value
  }
  
  guard let leftChild = leftChild else { fatalError("leftChild should not be nil")}guard let rightChild = rightChild else { fatalError("rightChild should not be nil")}if letfChild.rightBound < leftBound {
    return rightChild.query(withLeftBound: leftBound, rightBound: rightBound)
  } else if rightChild.leftBound > rightBound {
    return leftChild.query(withLeftBound: leftBound, rightBound: rightBound)
  } else {
    let leftResult = leftChild.query(withLeftBound: leftBound, rightBound: leftChild.rightBound)
    let rightResult = rightChild.query(withLeftBound: rightChild.leftBound, rightBound: rightBound)
    return function(leftResult, rightResult)
  }
}
Copy the code

Replace the node

The value of a node in the line segment tree depends on the value of its children, so we change the value of the leaf and we also update the value of its parent

public func replaceItem(at index: Int.withItem item: T) {
  if leftBound = = rightBound {
    value = item
  } else if let leftChild = leftChild, rightChild = rightChild {
    if leftChild.rightBound > = index {
      leftChild.replaceItem(at: index, withItem: item)
    } else {
      rightChild.replaceItem(at: index, withItem: item)
    }
   	value = function(leftChild.value, rightChild.value)
  }
}
Copy the code

The sparse table

Similar to the application of Segment Tree, the difference is that the sparse table requires f to be an idempotent binary operator.

A sparse table is a table where table[w][l] contains the answers to [l, L + 2**w).

  • W for width… The number or width of elements is 2**w
  • L is the lower bound… Is the beginning of the interval

Sparse tables can be implemented using two – digit arrays

public class SparseTable<T> {
  private var table: [[T]]
  
  public init(array: [T].function: @escaping (T.T) - >T.defaultT: T) {
    table = [[T]](repeating: [T](repeating: defaultT, count: N), count: W)}// ...
}
Copy the code
public init(array: [T].function: @escaping (T.T) - >T.defaultT: T) {
  let N = array.count
  let W = Int(ceil(log2(Double(N))))
  table = [[T]](repeating: [T](repeating: defaultT, count: N), count: W)
  self.function = function
  self.defaultT = defaultT
  
  for w in 0..<W {
    for l in 0..<N {
      if w = = 0 {
        table[w][l] = array[l]
      } else {
        let first = self.table[w - 1][l]
        let secondIndex = l + (1 << (w - 1))
        let second = ((0..<N).contains(secondIndex)) ? table[w - 1][secondIndex] : defaultT
        table[w][l] = function(first, second)
      }
    }
  }
}
Copy the code

Time complexity of sparse table construction O(NlogN) Extra space O(NlogN)

The query

public func query(from l: Int.until r: Int) -> T {
  let width = r - 1
  let W = Int(floor(log2(Double(width))))
  let lo = table[W][l]
  let hi = table[W][r - (1 << W)]
  return function(lo, hi)
}
Copy the code

The heap

General use of the heap

  • Build priority queues
  • Support for heap sorting
  • Quickly compute the smallest (or largest) element of a set
  • Impress your non-programmer friends

Important operations on the heap

  • shiftUp()
  • shiftDown(): the heap (heapify)

The dictionary tree (Trie)

Tries (also known as prefix trees or cardinal trees in some other implementations) are special types of trees used to store associated data structures.

Storing English is the main purpose of a dictionary tree. Each node in the dictionary tree represents a single character of a word, and a series of nodes makes up a word.

func contains(word: String) -> Bool {
  guard !word.isEmpty else { return false }
  
  var currentNode = root
  
  var characters = Array(word.lowercased())
  var currentIndex = 0
  
  while currentIndex < characters.count,
  	let child = currentNode.children[characters[currentIndex]] {
      
      currentNode = child
      currentIndex + = 1
    }
  
  	if currentIndex = = characters.count && currentNode.isTerminating {
      return true
    } else {
      return false}}Copy the code
func insert(word: String) {
  guard !word.isEmpty else {
    return
  }
  
  var currentNode = root
  
  for character in word.lowercased() {
    if let childNode = currentNode.children[character] {
      currentNode = childNode
    } else {
      currentNode.add(value: character)
      currentNode = currentNode.children[character]!}}// Word already present?
  guard !currentNode.isTerminating else {
    return
  }
  
  wordCount + = 1
  currentNode.isTerminating = true
}
Copy the code
func remove(word: String) {
  guard !word.isEmpty else {
    return
  }
  
  guard let terminalNode = findTerminalNodeOf(word: word) else {
    return
  }
  
 	if terminalNode.isLeaf {
    deleteNodesForwordEndingWith(terminalNode: terminalNode)
  } else {
    terminalNode.isTerminating = false
  }
  wordCount - = 1
}
Copy the code

B tree

A B-tree is a self-balancing search tree where each node can have more than two children

An n-order B-tree has the following properties:

  • Each node has at most 2n keys
  • Each node (except the root node) has at least n keys
  • A non-leaf node with K keys has K +1 children
  • The keys in all nodes are sorted increments
  • The subtree between the k and L keys of non-leaf nodes contains all the keys between K and L
  • All leaf nodes are at the same level
class BTreeNode<Key: Comparable.Value> {
  unowned var owner: BTree<Key.Value>
  
  fileprivate var keys = [Key] ()var children: [BtreeNode]?
  
  .
}
Copy the code

quadtree

Quadtrees are most commonly used to divide two-dimensional space by recursive subdivision into four regions (quadrants).

Each node in the tree represents a rectangular region and stores all the finite number of points located in its region.

class QuadTreeNode {
  enum NodeType {
    case leaf
    case 'internal'(children: Children)}struct Children {
    let leftTop: QuadTreeNode
    let leftBottom: QuadTreeNode
    let rightTop: QuardTreeNode
    let rightBottom: QuadTreeNode
    .
  }
  
  var points: [Point] = []
  let rect: Rect
  var type: NodeType = .leaf
  
  static let maxPointCapacity = 3
  
  init(rect: Rect) {
    self.rect = rect
  }
  .
}
Copy the code

Once the limit of page nodes is reached, four children are added to the node, representing the four quadrants, and each point in recT is passed to one of the children. Therefore, new points are always added to leaf nodes.

extension QuadTreeNode {
  @discardableResult
  func add(point: Point) -> Bool {
    if !rect.contains(point: point) {
      return false
    }
    
    switch type {
    case .internal(let children):
    	// pass the point to one of the children
    	for child in children {
        if child.add(point: point) {
          return true}}return false // should never happen
    case .leaf:
     	points.append(point)
      // if the max capacity was reached, become an internal node
      if points.count = = QuadTreeNode.maxPointCapacity {
        subdivide()
      }
    }
    return true
  }
  
  private func subdivide(a) {
    switch type {
    case .leaf:
      type = .internal(children: Children(parentNode: self))
    case .internal:
      preconditionFailure("Calling subdivide on an internal node")}}}extension Children {
  init(parentNode: QuadTreeNode) {
    leftTop = QuadTreeNode(rect: parentNode.rect.leftTopRect)
    leftBottom = QuadTreeNode(rect: parentNode.rect.leftBottomRect)
    righttop = QuadTreeNode(rect: parentNode.rect.rightTopRect)
    rightBottom = QuardTreeNode(rect: parentNode.rect.rightBottomRect)
  }
}
Copy the code
class QuadTree {
  .
  let root: QuadTreeNode
  public func points(inRect rect: Rect) -> [point] {
    return root.points(inRect: rect)
  }
}

extension QuadTreeNode {
  func points(inRect rect: Rect)- > [Point] {
    // if the node's rect and the given rect don't intersect, return an empty array,
    // because there can't be any points that lie the node's (for its children's) rect and
    // in the given rect
    if !self.rect.intersects(rect: rect) {
      return[]}}var result: [Point] = []
  
  // collect the node's points that lie in the rect
  for point in points {
    if rect.contains(point: point) {
      result.append(point)
    }
  }
  
  switch type {
  case .leaf:
  	break
  case .internal(children: let children):
    // recursively add children's points that lie in the rect
    for childNode in children {
      result.append(contentsOf: childNode.points(inRect: rect))
    }
  }
  
  return result
}
Copy the code

octree

An octree is a tree with eight children for each internal (non-leaf) node and is commonly used for collision detection in games.

Octrees are most commonly used to divide three-dimensional space by recursively subdividing it into eight regions.

Each node in the tree represents a boxed area. A leaf node stores a single point in that region and assigns an array of objects to that point.

Once a point in the same region is added to the leaf, the leaf becomes an internal node and eight child nodes are added. All the points originally contained in the node are legendary to the child nodes for storage. So only the leaves are stored points and values.