트리

트리 구조가지고 있는 예시들

•  HTML DOM
• 네트워크 라우팅
• 인공지능
• 추상 구문 트리
• 컴퓨터 파일 시스템

 

*추상 구문 트리

-프로그래밍 언어로 작성된 소스코드의 추상 구조

https://ko.wikipedia.org/wiki/%EC%B6%94%EC%83%81_%EA%B5%AC%EB%AC%B8_%ED%8A%B8%EB%A6%AC

추상 구문 트리 - 위키백과, 우리 모두의 백과사전

*이진 탐색 트리는 정렬되어있는 트리

 

이진 탐색 트리

class Node{
  constructor(value){
    this.value=value
    this.left=null
    this.right=null
  }
}

class BinarySearchTree{
  constructor(){
    this.root=null
  }
...

▷ Insert

  insert(value){
    var newNode=new Node(value)
    if(this.root===null){
      this.root=newNode
      return this
    }else{
      var current=this.root
      while(true){
        if(value===current.value) return undefined
        if(value<current.value){
          if(current.left===null){
            current.left=newNode
            return this
          }else{
            current=current.left
          }
        }else if(value>current.value){
          if(current.right===null){
            current.right=newNode
            return this
          }
          else{
            current=current.right
          }
        }
      }
    }

  }

▷ Search

find(value){
    if(this.root===null) return undefined
    var current=this.root;
    found=false
    while(current && !found){
      if(value <current.value){
        current=current.left
      }else if(value>current.value){
        current=current.right
      }else{
        found=true
      }
    }
    if(!found) return undefined
    return current
  }
  
  contains(value){
    if(this.root===null) return undefined
    var current=this.root;
    found=false
    while(current && !found){
      if(value <current.value){
        current=current.left
      }else if(value>current.value){
        current=current.right
      }else{
        return true
      }
    }
    return false
  }
}

 

Big O

Best or Average

Insertion - O(log n)

Searching - O(log n)