별의 공부 블로그 🧑🏻‍💻

🗒️ 이진 탐색 트리 (2)

728x90
  1. 2022.06.04 [Python] 이진 트리(Binary Tree)

    이진 트리(Binary Tree) 이진 트리(Binary Tree)의 기본 이진 트리의 개념 트리(Tree) 자료구조는 나무를 거꾸로 뒤집어 놓은 형태이다. 트리의 맨 위를 뿌리(Root, 루트)라고 한다. 루트를 레벨 0으로 두고 나뭇잎(Leaf, 리프)에 해당하는 아래로 내려올 수록 레벨이 1씩 증가한다. 트리에서 각 위치를 노드(Node)라고 한다. 각 노드는 선, 즉 에지(Edge)로 연결되어 있다. 위 노드와 바로 아래 노드의 관계를 부모-자식 관계(Parent-Child Relationship)라고 한다. 자식 노드의 개수를 차수(Degree)라고 한다. 차수가 0인 노드를 리프(Leaf)라고 한다. 트리의 차수는 차수가 가장 높은 노드를 기준으로 정한다. 컴퓨터는 데이터를 0과 1로 표현하므..

  2. 2021.05.16 [C++] 이진 탐색 트리(Binary Search Tree)

    이진 탐색 트리(Binary Search Tree) 이진 탐색 트리(Binary Search Tree) 널리 사용되는 형태의 이진 트리(Binary Tree) BST의 속성 왼쪽 노드 ≤ 부모 노드 ≤ 오른쪽 노드 의 관계를 가짐. 부모 노드의 값 ≥ 왼쪽 자식 노드의 값 부모 노드의 값 ≤ 오른쪽 자식 노드의 값 부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 이고, 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있게 됨. 원소 검색을 위해 루트 노드부터 차례대로 값을 비교하는 경우, 각 단계마다 검색 범위가 절반으로 줄어듦. BST가 마지막 레벨을 제외한 모든 노드에 2개의 자식 노드가 있을 경우 트리의 높이 : log₂N N : 원소의 개수 BST의 검색 및 삽입 동작의 시간 복잡도 : O(l..

728x90
📖 Contents 📖

티스토리툴바