Union-find

اصطلاحات مرتبط

• Path compression — در Find هر گره‌ی روی مسیر را مستقیم به ریشه وصل کن تا Findهای بعدی کوتاه‌تر شوند.
• Union by size — هنگام ادغام دو درخت، کوچک‌تر را زیر ریشه‌ی بزرگ‌تر بگذار تا درخت‌ها کم‌عمق بمانند.
• Amortized analysis — هزینه‌ی هر عملیات که روی کل دنباله‌ی عملیات‌ها میانگین گرفته می‌شود. append که گاهی همه‌چیز را کپی می‌کند، اگر کپی‌های گران به‌اندازه‌ی کافی نادر باشند، همچنان O(1) سرشکن‌شده است.

← همه‌ی اصطلاحات