[자료구조] 덱, 이진탐색트리

1. 덱

• 스택과 큐의 기능을 모두 가진다.
• 포인터 변수가 더 많이 필요하기 때무에 메모리가 상대적으로 더 많이 필요하다.
• python에서 큐의 기능이 필요할때 덱 라이브러리 사용한다.

연결리스트로 덱 구현

• 앞, 뒤 두개의 포인터 구현

 

 

2. 이진탐색트리

• 트리 : 계층적인 구조를 표현할 때 사용하는 자료구조이다.
• 루트 노드 : 부모가 없는 최상위 노드
• 리프 노드 : 자식이 없는 노드
• 깊이 : 루트노드에서 가장 깊은 리프노드까지의 길이
• 이진 트리 : 최대 2개의 자식을 가질 수 있는 트리
• 이진 탐색 트리의 성질 : 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
• 이진 탐색 트리에서 원소 삭제
  1. 왼쪽 자식이 없는 경우 -> 오른쪽 자식으로 대체
  2. 오른쪽 자식이 없는 경우 -> 왼쪽 자식으로 대체
  3. 왼,오른쪽 자식이 모두 있는 경우 -> 오른쪽 서브트리에서 가장 작은 노드로 대체
• 순회 : 트리에 포함되어 있는 정보를 모두 출력할 때 사용한다.
  1. 전위 순회 : 루트 방문 -> 왼쪽 자식 방문 -> 오른쪽 자식 방문
  2. 중위 순회 : 왼쪽 자식 방문 -> 루트 방문 -> 오른쪽 자식 방문
  3. 후위 순회 : 왼쪽 자식 방문 -> 오른쪽 자식 방문 -> 루트 방문
  4. 레벨 순회 : 루트 노드부터 방문하여 레벨별로 방문
• 편향 이진 트리 : 왼쪽 또는 오른쪽으로 한 방향에 대한 서브 트리를 갖는다. 

 

 

 

* 해당 글은 패스트 캠퍼스 강의 수강 내용을 정리한 글입니다.