tag

#tree-sort

4 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Cartesian Tree Adaptive Sort

Cartesian Tree Adaptive Sort Cartesian tree adaptive sort builds a Cartesian tree from the input sequence and uses its structure to produce sorted output. The tree encodes both the order of elements and their relative values. You use it when input has structure that can be exploited through tree shape. Problem Given an array ( A ), sort it by: constructing a Cartesian tree extracting elements in sorted order A...
algorithms sorting cartesian-tree adaptive tree-sort
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Binary Tree Online Sort

Binary Tree Online Sort Binary tree online sort inserts elements into a binary search tree (BST) as they arrive, then produces sorted output via in-order traversal. You use it when data arrives incrementally and you want ordered queries or final sorted output without a separate sorting phase. Problem Given a stream ( x_1, x_2, \dots, x_n ), maintain a structure such that: insertion is performed online elements can be retrieved...
algorithms sorting binary-search-tree online tree-sort
Wiki › Algorithms › 01. Searching and Sorting › 6. Elementary Sorting ›

Tree Sort

Tree Sort Tree sort sorts a sequence by inserting its elements into a binary search tree, then reading the tree with an inorder traversal. The binary search tree property places smaller values in the left subtree and larger values in the right subtree, so inorder traversal visits values in sorted order. The algorithm is simple when a binary search tree is already available. Its performance depends heavily on tree balance....
algorithms sorting tree-sort binary-search-tree
Wiki › Algorithms › 01. Searching and Sorting › 6. Elementary Sorting ›

Cartesian Tree Sort

Cartesian Tree Sort Cartesian tree sort builds a Cartesian tree from the input array, then uses traversal to produce a sorted sequence. A Cartesian tree is a binary tree that satisfies both: heap property on values inorder traversal reproduces the original sequence For sorting, the tree is typically built as a min-heap, so the root holds the smallest element. Problem Given a sequence $A$ of length $n$, reorder it such...
algorithms sorting cartesian-tree tree-sort