ساختمان دادهData Structures
آرایهها، لیستها، درختها، هیپها، جدولهای درهمسازی و پیچیدگی آنها.
کنکور ارشد علوم کامپیوتر
مباحث
کارتها · 13
A plain BST is not balanced, so its height ranges from Θ(log n) down to n-1 and its leaf count from 1 to ⌈ n/2⌉ .
A plain BST has no balance guarantee, so its worst-case height is Θ(n) , making search/min/max O(n) .
BST over n keys with access frequencies that minimizes expected search cost, not height.
Collisions are resolved by chaining or open addressing; with load factor α = n/m kept O(1) , search costs expected Θ(1+α) = O(1) under simple uniform hashing.
A linked list trades the array's O(1) random access for O(1) insert/delete at a known node, but pays Θ(n) to search — so binary search never applies, even on a sorted list.
Push 1… n in order and pop at will: the reachable output orders are exactly the 231-avoiding permutations, and there are C_n = C(2n, n)/(n+1) of them.
A heap orders each node only against its children (vertical, partial); a BST orders each node against whole subtrees (horizontal, total) so an in-order walk is sorted — that gap forces an Ω(nlog n) comparison cost to turn a heap into a BST.
An AVL tree keeps every node's left/right subtree heights within 1; after an insert or delete, a single or double rotation at the lowest unbalanced node restores the invariant in O(log n).
To delete a node with two children, overwrite its key with its in-order predecessor (max of the left subtree) or successor (min of the right subtree), then delete that easier node.
In a complete binary tree of n nodes, the root's left subtree is largest when the last level fills the left side first; its size is then a full tree of height h-1 plus the overflow leaves, capped at 2^h-1.
The height of a tree is one more than the taller of its two subtrees; recurse to the leaves and combine on the way back up.
A multi-dimensional array is flattened into linear memory either row-by-row (row-major) or column-by-column (column-major), and you locate any cell with a base-plus-offset address formula.
A binary heap is a complete binary tree stored in an array; MAX-HEAPIFY repairs one node by sifting it down in Θ(lg n) , while BUILD-MAX-HEAP turns an unordered array into a heap bottom-up in Θ(n) — not Θ(nlg n) .