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

이진 탐색 트리란?

이진 트리의 한 종류로

왼쪽 자식 노드에는 부모 노드보다 작은 값, 오른쪽 자식 노드에는 부모 노드보다 큰 값을 저장하여 만든 트리 

 

https://lgphone.tistory.com/90

13-2. 이진 탐색 트리와 자가 균형 이진 탐색 트리 (Binary Search Tree and Self-balancing Binary Tree): 파이썬

https://ejklike.github.io/2018/01/09/traversing-a-binary-tree-2.html

Eunji Kim @ CAU - 파이썬을 사용한 이진 트리와 순회 알고리즘 구현 (2)

트리의 순회방법 두 가지

DFS

BFS

https://www.jiwon.me/binary-tree-traversal/

이진 트리 순회: 전위, 중위, 후위, 레벨

 

이외에도 편향 트리일 경우 균형을 맞추는 자가 균형트리가 있다.

https://pinopino.tistory.com/entry/%ED%8A%B8%EB%A6%AC-%EA%B0%9C%EB%85%90-%EC%A0%95%EB%A6%AC-%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89%ED%8A%B8%EB%A6%ACBST-%EC%9E%90%EA%B0%80%EA%B7%A0%ED%98%95%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89%ED%8A%B8%EB%A6%ACAVL-red-black-tree-Trie-Heap-B-Tree-BTree

트리 개념 정리 - 이진탐색트리(BST), 자가균형이진탐색트리(AVL / red-black tree), Trie, Heap, B-Tree, B+Tree

 

레드블랙트리