Red-Black Tree

নিয়ম পাঁচটা: প্রতিটা node red বা black; root black; leaf (NIL) black; red node-এর সন্তান কখনো red নয়; যেকোনো node থেকে descendant leaf পর্যন্ত প্রতিটা path-এ black node-এর সংখ্যা সমান (black-height)।

ফল: height ≤ 2·log₂(n+1)। AVL-এর মতো টানটান balance নয়, কিন্তু insert/delete-এ rotation অনেক কম — write-heavy কাজে জেতে।

ব্যবহার: Linux kernel-এর CFS scheduler ও rbtree, C++ std::map, Java TreeMap — একই structure সবখানে।