트리

트리 Tree
루트, 노드, 리프
add, search 메소드

class Node<T> {
    var value: T
    var children: [Node] = []
    // 옵셔널인 이유: 모든 노드가 부모 노드를 갖고 있지 않기 때문이다(ex 루트),
    // weak인 이유: 사이클을 피하기 위함이다 (컨벤션에 따르면 parent 객체가 child 객체를 strong하게 hold하는 것을 권장)
    weak var parent: Node?
    
    init(value: T) {
        self.value = value
    }
    
    func add(child: Node) {
        children.append(child)
        child.parent = self
    }
}

//A type that can be compared for value equality.
extension Node where T: Equatable {
    
    func search(value: T) -> Node? {
        // 1 현재 노드 체크
        if value == self.value {
            return self
        }
        
        // 2 자식 노드 배열 중 체크
        for child in children {
            if let found = child.search(value: value) {
                return found
            }
        }
        
        // 3 없을 때
        return nil
    }
}

let beverages = Node(value: "beverages")
let hotBeverages = Node(value: "hot")
let coldBeverages = Node(value: "cold")
let hotTea = Node(value: "tea")
let hotCoffee = Node(value: "coffee")
let hotCocoa = Node(value: "cocoa")
let coldSoda = Node(value: "soda")
let coldmilk = Node(value: "milk")

beverages.add(child: hotBeverages)
hotBeverages.add(child: hotTea)
hotBeverages.add(child: hotCoffee)
hotBeverages.add(child: hotCocoa)

beverages.add(child: coldBeverages)
coldBeverages.add(child: coldSoda)
coldBeverages.add(child: coldmilk)

extension Node: CustomStringConvertible {
    var description: String {   //프로토콜
        var text = "\(value)"
        
        if !children.isEmpty {
            text += "{" + children.map{ $0.description }.joined(separator: ", ") + "}"
        }
        return text
    }
}
print(beverages)    //"beverages{hot{tea, coffee, cocoa}, cold{soda, milk}}\n"

beverages.search(value: "cocoa")

---

레드블랙트리

이진탐색트리의 균형잡힌 버전 O(logN)
https://velog.io/@msi753/이진-탐색-트리
이진탐색트리의 아래와 같은 문제(시간복잡도가 O(h))를 예방가능하다

a
  \
   b
    \
     c
      \
       d

1. Every node is either red or black 모든 노드는 빨간색이거나 검정색이다.
2. The root is black 루트노드는 검정색이다
3. Every leaf (nullLeaf) is black 모든 리프노드는 검정색이다
4. If a node is red, then both its children are black 만약 노드가 빨간색이면, 그 노드의 자식노드는 검정색이다 (빨간 노드가 연속으로 나올 수 없다)
5. For each node, all paths from the node to descendant leaves contain the same number of black nodes 모든 각각의 노드에 대해 하위 노드로 가면서 블랙노드의 개수는 같다

메서드

node:

• nodeX.getPredecessor()
  Returns the inorder predecessor of nodeX
• nodeX.getSuccessor()
  Returns the inorder successor of nodeX
• nodeX.minimum()
  Returns the node with the minimum key of the subtree of nodeX
• nodeX.maximum()
  Returns the node with the maximum key of the subtree of nodeX

Tree:

• search(input:)
  Returns the node with the given key value
• minValue()
  Returns the minimum key value of the whole tree
• maxValue()
  Returns the maximum key value of the whole tree
• insert(key:)
  Inserts the key value into the tree
• delete(key:)
  Delete the node with the respective key value from the tree
• verify()
  Verifies that the given tree fulfills the red-black tree properties
• count()
  Returns how many nodes in the tree
• isEmpty()
  Returns if the tree has no nodes
• allElements()
  Returns an array containing all nodes (in-order traversal) in the tree.