درختهای جستوجوی دودویی
Binary Search Trees
مباحث درختهای جستوجوی دودویی (BST).
ساختمان داده کنکور ارشد علوم کامپیوتر
کارتها · 9
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.
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 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) .