Node ของต้นไม้แดงดำนั้นมีข้อมูลเพิ่มมาจาก Node ของ binary search tree แบบปกติคือจะมีการเพิ่มตัวแปรที่เก็บสี แดงดำ อาจเป็น ตัวเลข หรือค่าความจริง ซึ่งใช้หน่วยจำเพิ่มขึ้นเพียงแค่หนึ่งบิตต่อหนึ่งปมการแสดงสีอาจแสดงด้วย edge แทนที่จะเป็นสีของ nodeซึ่งไม่ได้ทำให้เกิดข้อแตกต่างแต่อย่างใด