इस अनुभाग में हम देखेंगे कि रेड-ब्लैक ट्री (Red-Black Tree) क्या है। रेड-ब्लैक ट्री स्व-संतुलन बाइनरी खोज ट्री (self-balancing binary search tree) हैं। प्रत्येक नोड के लिए कुछ शर्तें हैं। ये नीचे जैसी हैं:
प्रत्येक नोड का एक रंग होता है। जो या तो लाल (Red) या काला (Black) होता है
रूट हमेशा काला होगा
दो आसन्न लाल नोड नहीं होंगे
एक नोड (रूट सहित) से उसके किसी भी वंशज NULL नोड तक के हर पथ में काले नोड्स की संख्या समान होती है।
रेड-ब्लैक ट्री का उदाहरण
पत्ते पर NULL नोड्स के साथ रेड-ब्लैक ट्री
AVL ट्री के साथ तुलना
AVL ट्री रेड-ब्लैक ट्री से अधिक संतुलित होते हैं। लेकिन प्रमुख नुकसान यह है कि सम्मिलन और विलोपन के दौरान अधिक घूर्णन (rotations) होंगे। एकाधिक सम्मिलन और विलोपन के लिए, रेड-ब्लैक ट्री सहायक होगा।
