A Red/Black Tree is one way to implement a balanced binary search tree. The principles behind how it works make sense to me, but the chosen colors don't. Why red and black, as opposed to any other pair of colors or of attributes in general? When I hear "red and black," the first things that come to mind are checkerboards and Les Misérables, neither of which seems particularly applicable in this context.
Origin of the Term ‘Red/Black Tree’
data structureshistory
Related Solutions
"Single Entry, Single Exit" was written when most programming was done in assembly language, FORTRAN, or COBOL. It has been widely misinterpreted, because modern languages do not support the practices Dijkstra was warning against.
"Single Entry" meant "do not create alternate entry points for functions". In assembly language, of course, it is possible to enter a function at any instruction. FORTRAN supported multiple entries to functions with the ENTRY
statement:
SUBROUTINE S(X, Y)
R = SQRT(X*X + Y*Y)
C ALTERNATE ENTRY USED WHEN R IS ALREADY KNOWN
ENTRY S2(R)
...
RETURN
END
C USAGE
CALL S(3,4)
C ALTERNATE USAGE
CALL S2(5)
"Single Exit" meant that a function should only return to one place: the statement immediately following the call. It did not mean that a function should only return from one place. When Structured Programming was written, it was common practice for a function to indicate an error by returning to an alternate location. FORTRAN supported this via "alternate return":
C SUBROUTINE WITH ALTERNATE RETURN. THE '*' IS A PLACE HOLDER FOR THE ERROR RETURN
SUBROUTINE QSOLVE(A, B, C, X1, X2, *)
DISCR = B*B - 4*A*C
C NO SOLUTIONS, RETURN TO ERROR HANDLING LOCATION
IF DISCR .LT. 0 RETURN 1
SD = SQRT(DISCR)
DENOM = 2*A
X1 = (-B + SD) / DENOM
X2 = (-B - SD) / DENOM
RETURN
END
C USE OF ALTERNATE RETURN
CALL QSOLVE(1, 0, 1, X1, X2, *99)
C SOLUTION FOUND
...
C QSOLVE RETURNS HERE IF NO SOLUTIONS
99 PRINT 'NO SOLUTIONS'
Both these techniques were highly error prone. Use of alternate entries often left some variable uninitialized. Use of alternate returns had all the problems of a GOTO statement, with the additional complication that the branch condition was not adjacent to the branch, but somewhere in the subroutine.
Thanks to Alexey Romanov for finding the original paper. See http://www.cs.utexas.edu/users/EWD/ewd02xx/EWD249.PDF, page 28 (printed page number is 24). Not limited to functions.
Data Structures are, for the most part:
- Memory resident,
- Transient,
- Limited in size,
- Not re-entrant without adding concurrency mechanisms like locks or immutability,
- Not ACID compliant,
- Fast, if chosen carefully.
Databases are, for the most part:
- Disk-bound,
- Persistent,
- Large,
- Safely concurrent,
- ACID compliant, with transactional capabilities,
- Slower than data structures
Data structures are meant to be passed from one place to another, and used internally within a program. When was the last time you sent data from a web page to a web server using a database, or performed a calculation on a database that was entirely resident in memory?
Database systems use data structures as part of their internal implementation. It's a question of size and scope; you use data structures within your program, but a database system is a program in its own right.
Best Answer
EDIT: Answer from Professor Guibas:
I believe the term first appeared in "A dichromatic framework for balanced trees" from Leonidas J. Guibas and Robert Sedgewick in 1978.