자료구조

Binary Tree

motosw3600 2022. 1. 26. 01:17

Binary Tree

  • 아래 두가지를 만족하는 트리
  • 1) 어떠한 노드를 기준으로 왼쪽은 기준이 되는 노드보다 전부다 작아야된다.
  • 2) 어떠한 노드를 기준으로 오른쪽은 기준이 되는 노드보다 전부다 커야된다.
  • 일반 배열에 비해 추가, 제거, 검색의 작업횟수가 크게 줄어든다.
  • Heap은 완전이진트리기 때문에 배열이나 리스트로 구현했지만 이진탐색트리는 완전 이진 트리가 아니기 때문에 Node로 구현

 

 

Search

정렬되지 않은 배열의 탐색은 순차적으로 탐색하기 때문에 O(n)

이진 탐색 트리는 큰값과 작은값을 비교하면서 찾기 때문에 O(log n)

 

  1. 루트노드가 없는경우 nil반환
  2. data와 노드의 왼쪽자식과 오른쪽 자식을 비교해가면서 확인
  3. 노드 반환

 

func search(_ data: T) -> Node<T>? {
    if root == nil { return nil }
    
    var currentNode = root
    while let node = currentNode {
        if data == node.data { return node }
        
        if data < node.data {
            currentNode = node.leftChild
        } else {
            currentNode = node.rightChild
        }
    }
    
    return currentNode
}

 

Insert

배열에선 중간에 요소가 삽입되면 다른 모든 요소가 한 위치만큼 뒤로 이동하기 때문에 O(n)

이진 탐색 트리는 삽입위치를 찾기위해 노드들과의 요소만 비교하면서 탐색하면 되므로 O(log n)

 

  1. root가 비었으면 새로운 노드를 root로 지정
  2. root노드를 currentNode로 지정한 후 왼쪽 자식 노드와 오른쪽 자식노드를 비교해가면서 반복
func insert(_ data: T) {
    guard let root = root else {
        self.root = Node(data)
        return
    }
    var currentNode = root
    while true {
        if currentNode.data == data { return }
        
        if data < currentNode.data {
            guard let nextNode = currentNode.leftChild else {
                return currentNode.leftChild = Node(data)
            }
            currentNode = nextNode
        } else {
            guard let nextNode = currentNode.rightChild else {
                return currentNode.rightChild = Node(data)
            }
            currentNode = nextNode
        }
    }
}

Delete

배열에선 삽입과 마찬가지로 요소들이 이동하기 때문에 O(n)

이진 탐색 트리에선 O(log n)

 

크게 3가지 경우 고려

  1. 지우려는 노드가 자식노드가 하나도 없을 때
    1. 지우려는 노드가 부모의 노드보다 작은 경우 -> 부모의 왼쪽자식 nil
    2. 지우려는 노드가 부모의 노드보다 큰 경우 -> 부모의 오른쪽 자식 nil
  2. 지우려는 노드가 자식이 하나인 노드일 때
    1. 자식이 왼쪽자식인 경우
      1. 지우려는 노드가 부모의 노드보다 작은 경우 -> 부모의 왼쪽자식을 지우는 노드의 왼쪽 자식으로 설정
      2. 지우려는 노드가 부모의 노드보다 큰 경우 -> 부모의 오른쪽 자식을 지우는 노드의 왼쪽 자식으로 설정
    2. 자식이 오른쪽 자식인경우
      1. 지우려는 노드가 부모의 노드보다 작은 경우 -> 부모의 왼쪽자식을 지우는 노드의 오른쪽 자식으로 설정
      2. 지우려는 노드가 부모의 노드보다 큰 경우 -> 부모의 오른쪽 자식을 지우는 노드의 오른쪽 자식으로 설정
  3. 지우려는 노드의 자식이 두개인 노드일 때
    1. 지우려는 노드의 오르쪽 자식노드 기준으로 제일 작은 노드 찾기(Change Node)
      1. ChangeNode의 자식노드가 없는 경우 -> 삭제할 노드를 ChangeNode로 대체
      2. ChangeNode의 오른쪽 자식노드가 있는 경우 -> 삭제할 노드를 ChangeNode로 대체 및 Change Parent Node를 ChangeNode의 오른쪽 자식으로 설정
func delete(_ data: T) {
    guard let root = root else { return }
    
    var parentNode = root
    var currentNode: Node? = root
    
    while let node = currentNode {
        if node.data == data {
            break
        }
        if data < node.data {
            currentNode = node.leftChild
        } else {
            currentNode = node.rightChild
        }
        parentNode = node
    }

    guard let deleteNode = currentNode else { return }

    // 1. 자식이 하나도 없는 노드 삭제
    if deleteNode.leftChild == nil && deleteNode.rightChild == nil {
        if data < parentNode.data {
            parentNode.leftChild = nil
        } else {
            parentNode.rightChild = nil
        }
    }
    
    // 2. 자식이 한개인 노드 삭제
    if deleteNode.leftChild != nil && deleteNode.rightChild == nil {
        if data < parentNode.data {
            parentNode.leftChild = deleteNode.leftChild
        } else {
            parentNode.rightChild = deleteNode.leftChild
        }
    }
    if deleteNode.leftChild == nil && deleteNode.rightChild != nil {
        if data < parentNode.data {
            parentNode.leftChild = deleteNode.rightChild
        } else {
            parentNode.rightChild = deleteNode.rightChild
        }
    }
    
    // 3. 자식이 두개인 노드 삭제
    guard let rightNode = deleteNode.rightChild else { return }
    
    var changeNode = rightNode
    var changeParentNode = rightNode
    
    while let nextNode = changeNode.leftChild {
        changeParentNode = changeNode
        changeNode = nextNode
    }
    
    if let rightNode = changeNode.rightChild {
        changeParentNode.leftChild = rightNode
    } else {
        changeParentNode.leftChild = nil
    }
    
    if data < parentNode.data {
        parentNode.leftChild = changeNode
    } else {
        parentNode.rightChild = changeNode
    }
    
    changeNode.leftChild = deleteNode.leftChild
    changeNode.rightChild = deleteNode.rightChild
}

 

 

최종 코드

더보기 
class Node<T: Comparable> {
    var data: T
    var leftChild: Node?
    var rightChild: Node?
    
    init(_ data: T) {
        self.data = data
    }
}

class BinarySearchTree<T: Comparable> {
    
    var root: Node<T>?
    
    func search(_ data: T) -> Node<T>? {
        if root == nil { return nil }
        
        var currentNode = root
        while let node = currentNode {
            if data == node.data { return node }
            
            if data < node.data {
                currentNode = node.leftChild
            } else {
                currentNode = node.rightChild
            }
        }
        
        return nil
    }
    
    func insert(_ data: T) {
        guard let root = root else {
            self.root = Node(data)
            return
        }

        var currentNode = root
        while true {
            if currentNode.data == data { return }
            
            if data < currentNode.data {
                guard let nextNode = currentNode.leftChild else {
                    return currentNode.leftChild = Node(data)
                }
                currentNode = nextNode
            } else {
                guard let nextNode = currentNode.rightChild else {
                    return currentNode.rightChild = Node(data)
                }
                currentNode = nextNode
            }
        }
    }
    
    func delete(_ data: T) {
        guard let root = root else { return }
        
        var parentNode = root
        var currentNode: Node? = root
        
        while let node = currentNode {
            if node.data == data {
                break
            }
            if data < node.data {
                currentNode = node.leftChild
            } else {
                currentNode = node.rightChild
            }
            parentNode = node
        }
    
        guard let deleteNode = currentNode else { return }
    
        // 1. 자식이 하나도 없는 노드 삭제
        if deleteNode.leftChild == nil && deleteNode.rightChild == nil {
            if data < parentNode.data {
                parentNode.leftChild = nil
            } else {
                parentNode.rightChild = nil
            }
        }
        
        // 2. 자식이 한개인 노드 삭제
        if deleteNode.leftChild != nil && deleteNode.rightChild == nil {
            if data < parentNode.data {
                parentNode.leftChild = deleteNode.leftChild
            } else {
                parentNode.rightChild = deleteNode.leftChild
            }
        }
        if deleteNode.leftChild == nil && deleteNode.rightChild != nil {
            if data < parentNode.data {
                parentNode.leftChild = deleteNode.rightChild
            } else {
                parentNode.rightChild = deleteNode.rightChild
            }
        }
        
        // 3. 자식이 두개인 노드 삭제
        guard let rightNode = deleteNode.rightChild else { return }
        
        var changeNode = rightNode
        var changeParentNode = rightNode
        
        while let nextNode = changeNode.leftChild {
            changeParentNode = changeNode
            changeNode = nextNode
        }
        
        if let rightNode = changeNode.rightChild {
            changeParentNode.leftChild = rightNode
        } else {
            changeParentNode.leftChild = nil
        }
        
        if data < parentNode.data {
            parentNode.leftChild = changeNode
        } else {
            parentNode.rightChild = changeNode
        }
        
        changeNode.leftChild = deleteNode.leftChild
        changeNode.rightChild = deleteNode.rightChild
    }
    
}

extension BinarySearchTree: CustomStringConvertible {
    var description: String {
        return diagram(for: self.root)
    }
        
    private func diagram(for node: Node<T>?,
                            _ 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.data)\n"
        }
        return diagram(for: node.rightChild, top + " ", top + "┌──", top + "│ ")
            + root + "\(node.data)\n"
            + diagram(for: node.leftChild, bottom + "│ ", bottom + "└──", bottom + " ")
    }
}

 

참고

https://babbab2.tistory.com/91

 

 

 

 

 

 

 

'자료구조' 카테고리의 다른 글

Queue  (0) 2021.12.29
Heap  (0) 2021.12.28

'자료구조'의 다른글

  • 현재글Binary Tree

관련글

티스토리툴바