《swift-algorithm-club》——数据结构/树

树(Trees)

树

树表示对象之间的层次关系

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
  }
}
复制代码

添加 description 方法以便可以打印?

extension TreeNode: CustomStringConvertible {
  public var description: String {
    var s = "\(value)"
    if !children.isEmpty {
      s += " {“ + chilren.map { $0.description }.joined(separator: ", ") + "}"
    }
  	return s
  }
}
复制代码

创建树

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)
复制代码

• 树的高度：根节点与最低叶节点的连接数

• 节点的深度：该节点与根节点之间的连接数

查询树中是否包含某个特定值：

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
  }
}
复制代码

二叉树

public indirect enum BinaryTree<T> {
  case node(BinaryTree<T>, T, BinaryTree<T>)
	case empty
}
复制代码

// 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)
复制代码

添加 description 方法

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 ""
    }
  }
}
复制代码

计算树中的节点数

public var count: Int {
  switch self {
    case let .node(left, _, right):
    	return left.count + 1 + right.count
    case .empty:
    	return 0
  }
}
复制代码

遍历顺序

1. 中序(或者说 深度优先)： 先查看节点的左子节点，然后节点本身，最后节点的右子节点(比如 A + B)
2. 前序：先查看节点本身，然后它的左右字节点(比如 + A B)
3. 后序：先查看左右子节点，然后节点本身(比如 A B +)

public func traverseInOrder(process: (T) -> Void) {
  if case let .node(left, value, right) = self {
    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)
  }
}
复制代码

二叉搜索树

每个左节点小于父节点，每个右节点大于父节点

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)
  }
}
复制代码

插入节点

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
    }
  }
}
复制代码

方便起见，我们添加一个以数组初始化的方法

public convenience init(array: [T]) {
  precondition(array.count > 0)
  self.init(value: arrat.first!)
  for v in array.dropFirst() {
    insert(value: v)
  }
}
复制代码

搜索

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!
  }
}
复制代码

迭代实现的版本

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
}
复制代码

遍历

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)
}
复制代码

树上的 map实现

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
}
复制代码

更改父节点

private func reconectParentTo(node: BinarySearchTree?) {
  if let parent = parent {
    if isLeftChild {
      parent.left = node
  	} else {
    	parent.right = node
    }
  }
  node?.parent = parent
}
复制代码

最小值 && 最大值

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

public func maximum() -> BinarySearchTree {
  var node = self
  while let next = node.right {
    node = next
  }
  return node
}
复制代码

删除节点

@discardableResult public func remove() -> 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
}
复制代码

高度

public func height() -> Int {
  if isLeaf {
    return 0
  } else {
    return 1 + max(left?.height() ?? 0, right?.height() ?? 0)
  }
}
复制代码

节点的深度

public func depth() -> Int {
  var node = self
  var edges = 0
  while let parent = node.parent {
    node = parent
    edges += 1
  }
  return edges
}
复制代码

前驱节点

public func predecessor() -> 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
  }
}
复制代码

后继节点

public func successor() -> BinarySearchTree<T>? {
  if let right = right {
    return right.minimum()
  } else {
    var node = self
    while let parent = node.parent {
      if parent.value > value { return parent }
    }
  }
}
复制代码

二叉搜索树是否有效

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
}
复制代码

用枚举实现的二叉树节点

public enum BinarySearchTree<T: Comparable> {
  case Empty
  case Leaf(T)
  indirect case Node(BinarySearchTree, T, BinarySearchTree)
}
复制代码

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)
  }
}
复制代码

插入节点

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))
      }
  }
}
复制代码

最重要的搜索方法

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
      }
  }
}
复制代码

红黑树

特性

1. 每个节点都是红色或黑色
2. 根节点是黑色的
3. 叶节点是黑的
4. 红色节点的子节点都是黑色的
5. 对每个节点，从节点到后代叶子的所有路径包含相同数量的黑色节点

伸展树(Splay Tree)

伸展树是一种数据结构，在结构上和平衡二叉搜索树相同。在伸展树上执行的每个操作都会导致重新调整，以便快速访问最近运行的值。

有三种类型的旋转可以形成 Splaying

• ZigZig
• ZigZag
• Zig

线索二叉树

线索二叉树是一种特殊的二叉树，保留了一些额外的变量，可以进行廉价和快速的中序遍历。

树的中序遍历通常是这样的

func traverse(n: Node?) {
  if (n == nil) { 
    return 
 	} else {
    traverse(n.left)
    visit(n)
    traverse(n.right)
  }
}
复制代码

有2中类型的线二叉树：单线索和双线索：

• 单线索树追踪中序前缀或后缀
• 双线索树同时追踪中序前缀和后缀

func predecessor() -> ThreadedBinaryTree<T>? {
  if let left = left {
    return left.maximum()
  } else {
    return leftThread
  }
}

func successor() -> ThreadedBinaryTree<T>? {
	if let right = right {
    return right.minimum()
  } else {
    return rightThread
  }
}
复制代码

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
    }
  }
}
复制代码

线段树

线段树的主要思想很简单：我们预先计算数组中的一些段，然后我们可以使用它而不重复计算

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>?
}
复制代码

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)
  }
}
复制代码

查询结果

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)
  }
}
复制代码

更换节点

线段树中节点的值取决于它子节点的值，因此，我们改变叶节点的值，同时也要更新它父节点的值

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)
  }
}
复制代码

稀疏表

和 Segment Tree 的应用情况相似，区别是稀疏表要求使用的f是幂等的二元运算符。

稀疏表是一个表，其中 table[w][l] 包含了 [l, l + 2**w) 的答案。

• w表示宽度 … 元素数量或宽度是 2**w
• l表示下界 … 是间隔的起点

稀疏表可以用二位数组实现

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)
  }
  // ...
}
复制代码

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)
      }
    }
  }
}
复制代码

构建稀疏表 时间复杂度O(NlogN) 额外空间O(NlogN)

查询

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)
}
复制代码

堆

堆的一般用途

• 构建优先级队列
• 支持堆排序
• 快速计算集合的最小(或最大)元素
• 给你的非程序员朋友留下深刻印象(艹，日语)

堆的重要操作

• shiftUp()
• shiftDown()：堆化(heapify)

字典树(Trie)

Trie(在某些其他实现中也被称作 前缀树 或者 基数树)是用于存储关联数据结构的特殊类型的树。

存储英语是字典树的主要作用。字典树中的每个节点表示一个单词的单个字符，一系列节点就组成一个单词。

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
    }
}
复制代码

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
}
复制代码

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
}
复制代码

B 树

B 树是一种自平衡搜索树，每个节点可以有多于2个子节点

一个n阶B树具有以下特性：

• 每个节点至多有 2n 个键
• 每个节点(除了根节点)至少有n个键
• 有 k 个键的非叶子节点有 k+1 个子节点
• 所有节点中的键按递增排序
• 非叶子节点的 k 键和 l 键之间的子树包含所有 k 和 l 之间的键
• 所有叶子节点位于同一级

class BTreeNode<Key: Comparable, Value> {
  unowned var owner: BTree<Key, Value>
  
  fileprivate var keys = [Key]()
  var children: [BtreeNode]?
  
  ...
}
复制代码

四叉树

四叉树最常用来划分二维空间，通过递归细分为四个区域(象限)。

树中的每个节点代表一个矩形区域，并存储所有位于其区域的有限数量点。

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
  }
  ...
}
复制代码

一旦达到页节点的限制，就会向节点添加四个子节点，分别代表四个象限，rect中的每个点都会传递给其中一个子节点。因此，总是将新点添加到叶节点。

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() {
    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)
  }
}
复制代码

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
}
复制代码

八叉树

八叉树是指每个内部(非叶子)节点有8个子节点的树，通常用于游戏中的碰撞检测。

八叉树最常用于划分三维空间，通过递归将其细分为8个区域。

树中的每个节点表示一个盒状区域。叶节点存储那个区域的单个点，并将一个对象数组赋予那个点。

一旦叶节点中添加同一区域的一个点，叶节点就变成内部节点了，就会添加8个子节点。节点中原先包含的所有点都被传奇给子节点进行存储。因此只有叶节点是存储点和值的。