Tree
(리눅스 명령어는 tree (command) 항목 참조)
트리 구조(tree 構造, 문화어: 나무구조)란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.
트리에서 최상위 노드를 루트 노드(root node; 뿌리 노드)라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node; 리프 노드)라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다.
Table of Tree
| Binary trees | Binary search tree (BST), Cartesian tree, Top tree, T-tree |
| Self-balancing binary search trees | AA tree, AVL tree, LLRB tree, Red-black tree, Scapegoat tree, Splay tree, Treap |
| B+ tree, B*-tree, Bx-tree, ~UB-tree, 2-3 tree, 2-3-4 tree, (a,b)-tree, Dancing tree, Htree | |
| Tries | Suffix tree, Radix tree, Ternary search tree, X-fast trie, Y-fast trie |
| Binary space partitioning (BSP) trees | Quadtree, Octree, k-d tree, Implicit k-d tree, vp-tree |
| Non-binary trees | Exponential tree, Fusion tree, Interval tree, PQ tree, Range tree, SPQR tree, Van Emde Boas tree |
| Spatial data partitioning trees | R-tree, R+tree, R*tree, X-tree, M-tree, Segment tree, Hilbert R-tree, Priority R-tree |
| Other trees | Heap, Hash tree, Finger tree, Order statistic tree, Metric tree, Cover tree, ~BK-tree, Doubly chained tree, iDistance, Link-cut tree, Fenwick tree |