Tree
lastmod 2025-01-03created 2014-09-156 edits
(For the Linux command, see tree (command).)
A tree structure (North Korean standard language: namugujo, "tree structure") is a kind of graph in which multiple nodes cannot point to a single node. Simply put, a graph with no cycles and only one path connecting any two distinct nodes is called a tree.
The topmost node in a tree is called the root node. Also, when node A points to node B, A is called the parent node of B, and B is called a child node of A. A node with no child nodes is called a leaf node. A node that is not a leaf node is called an 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 |