document_html:
<!DOCTYPE html>
<HTML class="client-js ve-not-available" lang="en" dir="ltr"><HEAD>

<TITLE>Red–black tree - Wikipedia</TITLE>

<LINK rel="stylesheet" href="/w/load.php?debug=false&lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.pygments%2CwikimediaBadges%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cmediawiki.legacy.commonPrint%2Cshared%7Cmediawiki.sectionAnchor%7Cmediawiki.skinning.interface%7Cskins.vector.styles%7Cwikibase.client.init&only=styles&skin=vector" />

<STYLE>
.referencetooltip{position:absolute;list-style:none;list-style-image:none;opacity:0;font-size:10px;margin:0;z-index:5;padding:0}.referencetooltip li{border:#080086 2px solid;max-width:260px;padding:10px 8px 13px 8px;margin:0px;background-color:#F7F7F7;-webkit-box-shadow:2px 4px 2px rgba(0,0,0,0.3);-moz-box-shadow:2px 4px 2px rgba(0,0,0,0.3);box-shadow:2px 4px 2px rgba(0,0,0,0.3)}.referencetooltip li+li{margin-left:7px;margin-top:-2px;border:0;padding:0;height:3px;width:0px;background-color:transparent;-webkit-box-shadow:none;-moz-box-shadow:none;box-shadow:none;border-top:12px #080086 solid;border-right:7px transparent solid;border-left:7px transparent solid}.referencetooltip>li+li::after{content:'';border-top:8px #F7F7F7 solid;border-right:5px transparent solid;border-left:5px transparent solid;margin-top:-12px;margin-left:-5px;z-index:1;height:0px;width:0px;display:block}.client-js body .referencetooltip li li{border:none;-webkit-box-shadow:none;-moz-box-shadow:none;box-shadow:none;height:auto;width:auto;margin:auto;padding:0;position:static}.RTflipped{padding-top:13px}.referencetooltip.RTflipped li+li{position:absolute;top:2px;border-top:0;border-bottom:12px #080086 solid}.referencetooltip.RTflipped li+li::after{border-top:0;border-bottom:8px #F7F7F7 solid;position:absolute;margin-top:7px}.RTsettings{float:right;height:24px;width:24px;cursor:pointer;background-image:url(//upload.wikimedia.org/wikipedia/commons/thumb/0/05/OOjs_UI_icon_advanced.svg/24px-OOjs_UI_icon_advanced.svg.png);background-image:linear-gradient(transparent,transparent),url(//upload.wikimedia.org/wikipedia/commons/0/05/OOjs_UI_icon_advanced.svg);margin-top:-9px;margin-right:-7px;-webkit-transition:opacity 0.15s;-moz-transition:opacity 0.15s;-ms-transition:opacity 0.15s;-o-transition:opacity 0.15s;transition:opacity 0.15s;opacity:0.6;filter:alpha(opacity=60)}.RTsettings:hover{opacity:1;filter:alpha(opacity=100)}.RTTarget{border:#080086 2px solid}
.wp-teahouse-question-form{position:absolute;margin-left:auto;margin-right:auto;background-color:#f4f3f0;border:1px solid #a7d7f9;padding:1em}#wp-th-question-ask{float:right}.wp-teahouse-ask a.external{background-image:none !important}.wp-teahouse-respond-form{position:absolute;margin-left:auto;margin-right:auto;background-color:#f4f3f0;border:1px solid #a7d7f9;padding:1em}.wp-th-respond{float:right}.wp-teahouse-respond a.external{background-image:none !important}
.cite-accessibility-label{ top:-99999px;clip:rect( 1px 1px 1px 1px ); clip:rect( 1px,1px,1px,1px ); position:absolute !important;padding:0 !important;border:0 !important;height:1px !important;width:1px !important; overflow:hidden}
.mw-ui-icon-popups-settings:before{background-image:url(/w/load.php?modules=ext.popups.images&image=popups-settings&format=rasterized&lang=en&skin=vector&version=16dhzob);background-image:linear-gradient(transparent,transparent),url("data:image/svg+xml,%3C%3Fxml version=%221.0%22 encoding=%22utf-8%22%3F%3E%0A%3Csvg xmlns=%22http://www.w3.org/2000/svg%22 viewBox=%220 0 24 24%22%3E%0A %3Cpath fill=%22%2354595d%22 d=%22M20 14.5v-2.9l-1.8-.3c-.1-.4-.3-.8-.6-1.4l1.1-1.5-2.1-2.1-1.5 1.1c-.5-.3-1-.5-1.4-.6L13.5 5h-2.9l-.3 1.8c-.5.1-.9.3-1.4.6L7.4 6.3 5.3 8.4l1 1.5c-.3.5-.4.9-.6 1.4l-1.7.2v2.9l1.8.3c.1.5.3.9.6 1.4l-1 1.5 2.1 2.1 1.5-1c.4.2.9.4 1.4.6l.3 1.8h3l.3-1.8c.5-.1.9-.3 1.4-.6l1.5 1.1 2.1-2.1-1.1-1.5c.3-.5.5-1 .6-1.4l1.5-.3zM12 16c-1.7 0-3-1.3-3-3s1.3-3 3-3 3 1.3 3 3-1.3 3-3 3z%22/%3E%0A%3C/svg%3E%0A")}.mw-ui-icon-popups-close:before{background-image:url(/w/load.php?modules=ext.popups.images&image=popups-close&format=rasterized&lang=en&skin=vector&version=16dhzob);background-image:linear-gradient(transparent,transparent),url("data:image/svg+xml,%3C%3Fxml version=%221.0%22 encoding=%22UTF-8%22%3F%3E%0A%3Csvg xmlns=%22http://www.w3.org/2000/svg%22 width=%2220%22 height=%2220%22 viewBox=%220 0 20 20%22%3E%0A%09%3Cpath d=%22M3.636 2.222l14.142 14.142-1.414 1.414L2.222 3.636z%22/%3E%0A%09%3Cpath d=%22M17.778 3.636L3.636 17.778l-1.414-1.414L16.364 2.222z%22/%3E%0A%3C/svg%3E%0A")}
.suggestions{overflow:hidden;position:absolute;top:0;left:0;width:0;border:0;z-index:1099;padding:0;margin:-1px 0 0 0}.suggestions-special{position:relative;background-color:#fff;cursor:pointer;border:1px solid #a2a9b1;margin:0;margin-top:-2px;display:none;padding:0.25em 0.25em;line-height:1.25em}.suggestions-results{background-color:#fff;cursor:pointer;border:1px solid #a2a9b1;padding:0;margin:0}.suggestions-result{color:#000;margin:0;line-height:1.5em;padding:0.01em 0.25em;text-align:left; overflow:hidden;text-overflow:ellipsis;white-space:nowrap}.suggestions-result-current{background-color:#2a4b8d;color:#fff}.suggestions-special .special-label{color:#72777d;text-align:left}.suggestions-special .special-query{color:#000;font-style:italic;text-align:left}.suggestions-special .special-hover{background-color:#c8ccd1}.suggestions-result-current .special-label,.suggestions-result-current .special-query{color:#fff}.highlight{font-weight:bold}
@media screen {
	.tochidden,.toctoggle{-moz-user-select:none;-webkit-user-select:none;-ms-user-select:none;user-select:none}.toctoggle{font-size:94%}}
@media print {
	#toc.tochidden,.toc.tochidden,.toctoggle{display:none}}
.uls-menu{border-radius:2px; font-size:medium}.uls-search,.uls-language-settings-close-block{border-top-right-radius:2px;border-top-left-radius:2px}.uls-language-list{border-bottom-right-radius:2px;border-bottom-left-radius:2px}.uls-menu.callout:before,.uls-menu.callout:after{border-top:10px solid transparent;border-bottom:10px solid transparent;display:inline-block; top:17px;position:absolute;content:''}.uls-menu.callout.selector-right:before{ border-left:10px solid #c8ccd1; right:-11px}.uls-menu.callout.selector-right:after{ border-left:10px solid #f8f9fa; right:-10px}.uls-menu.callout.selector-left:before{ border-right:10px solid #c8ccd1; left:-11px}.uls-menu.callout.selector-left:after{ border-right:10px solid #f8f9fa; left:-10px}.uls-ui-languages button{margin:5px 15px 5px 0;white-space:nowrap;overflow:hidden}.uls-search-wrapper-wrapper{position:relative;padding-left:40px;margin-top:5px;margin-bottom:5px}.uls-icon-back{background:transparent url(/w/extensions/UniversalLanguageSelector/resources/images/back-grey-ltr.png?90e9b) no-repeat scroll center center;background-image:-webkit-linear-gradient(transparent,transparent),url(/w/extensions/UniversalLanguageSelector/resources/images/back-grey-ltr.svg?e226b);background-image:linear-gradient(transparent,transparent),url("data:image/svg+xml,%3C%3Fxml version=%221.0%22 encoding=%22UTF-8%22%3F%3E%0A%3Csvg xmlns=%22http://www.w3.org/2000/svg%22 width=%2224%22 height=%2224%22 viewBox=%220 0 24 24%22%3E%0A%09%3Cpath fill=%22%2354595d%22 d=%22M7 13.1l8.9 8.9c.8-.8.8-2 0-2.8l-6.1-6.1 6-6.1c.8-.8.8-2 0-2.8L7 13.1z%22/%3E%0A%3C/svg%3E%0A");background-size:28px;background-position:center center;height:32px;width:40px;display:block;position:absolute;left:0;border-right:1px solid #c8ccd1;opacity:0.8}.uls-icon-back:hover{opacity:1;cursor:pointer}  .skin-vector .uls-menu{border-color:#c8ccd1;-webkit-box-shadow:0 2px 2px 0 rgba(0,0,0,0.25);box-shadow:0 2px 2px 0 rgba(0,0,0,0.25);font-size:0.875em}.skin-vector .uls-search{border-bottom-color:#c8ccd1}.skin-vector .uls-filtersuggestion{color:#72777d}.skin-vector .uls-lcd-region-title{color:#54595d}
@-webkit-keyframes centralAuthPPersonalAnimation{0%{opacity:0;-webkit-transform:translateY( -20px )}100%{opacity:1;-webkit-transform:translateY( 0 )}}@-moz-keyframes centralAuthPPersonalAnimation{0%{opacity:0;-moz-transform:translateY( -20px )}100%{opacity:1;-moz-transform:translateY( 0 )}}@-o-keyframes centralAuthPPersonalAnimation{0%{opacity:0;-o-transform:translateY( -20px )}100%{opacity:1;-o-transform:translateY( 0 )}}@keyframes centralAuthPPersonalAnimation{0%{opacity:0;transform:translateY( -20px )}100%{opacity:1;transform:translateY( 0 )}}.centralAuthPPersonalAnimation{-webkit-animation-duration:1s;-moz-animation-duration:1s;-o-animation-duration:1s;animation-duration:1s;-webkit-animation-fill-mode:both;-moz-animation-fill-mode:both;-o-animation-fill-mode:both;animation-fill-mode:both;-webkit-animation-name:centralAuthPPersonalAnimation;-moz-animation-name:centralAuthPPersonalAnimation;-o-animation-name:centralAuthPPersonalAnimation;animation-name:centralAuthPPersonalAnimation}
@media print{#centralNotice{display:none}}.cn-closeButton{display:inline-block;zoom:1;background:url(data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABMAAAATCAYAAAByUDbMAAACeklEQVR4Aa1UM3jkcRBN6qS//tTFttPHqmI359VZ5dm2L1zFtr02YlRx5sX2ft/7ed7O/w1M5ufnt8NZQjCBQXhG+IYZe5zjfju7xcHc3NzEzMwM6xOEqNnZ2ZeVlZW827dv1ycmJnbGx8d3Yr5582Z9eXk5D/d4h/empqYm+K0nw3yKcF4sFmdzOJzGgIAAhb29vc7Ozk6/Atrr/fz8lCwWq6m3tzcb72G3nmzFo/NNTU354eHhIltbW72Tk5M2IyND9P79+8ZPnz7VvXnzpoHBYPS4uLhobGxsDMHBwaLa2tp82MF+PVmUUqnMioiI6LOysjLQLCcPS2ZmZn7Ozc39oPtFYG80GgWpqakSS0tLY1hYmEgikWTBfoXsLD16BT3gUWhoqEKtVheREZ+Qu0IEjI+PZ2k0GqFer+cnJSWJra2tDWw2u2FqauoVeEAW3NzcnBcYGCh3dHTUtba2ltNjLvRJSEiQEQEPRENDQzkMBqPXwsKiXyqVFsFDNzc3LWmoqKmp4YIHZIyHDx9WOzg46GJiYmTk5e/h4eHstLQ0CX2ykXST4JPJ8y7sSVM5/QGMf9y4caMHf3r//v1a8IDsGRm04/D58+dtpNFPPNRqtflXrlzpI8G15IEGc2xsrFSlUglwD+Tk5NRBmuTk5A7wgOxbXFxcF8iysrIa1mskEolKvL29Ne7u7mpXV1dNaWlp9fr7X79+VYMMeQieY/dsv5p1r2g2Nja2vWZ7RXNiYuIA0dwlzwYGBjbkGXmURXeLeUa1ul2ebV8BEH+7CiAiASTYvgJ2qc3MzMzF2vz8+XPd27dvG5hMZg+CsV1tHmfXOP5+dqyddgHOI7v1srTdcwAAAABJRU5ErkJggg==);background:url(/w/extensions/CentralNotice/resources/subscribing/CloseWindow19x19.png?7596b)!ie;width:19px;height:19px;text-indent:19px;white-space:nowrap;overflow:hidden}
.ve-activated #toc,.ve-activated #siteNotice,.ve-activated .mw-indicators,.ve-activated #t-print,.ve-activated #t-permalink,.ve-activated #p-coll-print_export,.ve-activated #t-cite,.ve-deactivating .ve-ui-surface,.ve-active .ve-init-mw-desktopArticleTarget-editableContent{display:none} .ve-activating .ve-ui-surface{height:0;padding:0 !important; overflow:hidden} .ve-loading #content > :not( .ve-init-mw-desktopArticleTarget-loading-overlay ), .ve-activated .ve-init-mw-desktopArticleTarget-uneditableContent{ pointer-events:none;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;opacity:0.5}.ve-activated #catlinks{cursor:pointer}.ve-activated #catlinks a{opacity:1} .ve-activated #content{position:relative} .ve-init-mw-desktopArticleTarget-loading-overlay{position:absolute;left:0;right:0;z-index:1;margin-top:-0.5em}.ve-init-mw-desktopArticleTarget-progress{height:1em;overflow:hidden;margin:0 25%}.ve-init-mw-desktopArticleTarget-progress-bar{height:1em;width:0} .mw-editsection{white-space:nowrap; unicode-bidi:-moz-isolate;unicode-bidi:-webkit-isolate;unicode-bidi:isolate}.mw-editsection-divider{color:#54595d} .ve-init-mw-desktopArticleTarget-progress{height:0.75em;border:1px solid #36c;background:#fff;border-radius:2px;box-shadow:0 0.1em 0 0 rgba( 0,0,0,0.15 )}.ve-init-mw-desktopArticleTarget-progress-bar{height:0.75em;background:#36c}
.mw-ui-button{font-family:inherit;font-size:1em;display:inline-block;min-width:4em;max-width:28.75em;padding:0.546875em 1em;line-height:1.286;margin:0;border-radius:2px;-webkit-box-sizing:border-box;-moz-box-sizing:border-box;box-sizing:border-box;-webkit-appearance:none;*display:inline; zoom:1;vertical-align:middle;background-color:#f8f9fa;color:#222222;border:1px solid #a2a9b1;text-align:center;font-weight:bold;cursor:pointer}.mw-ui-button:visited{color:#222222}.mw-ui-button:hover{background-color:#ffffff;color:#444444;border-color:#a2a9b1}.mw-ui-button:focus{background-color:#ffffff;color:#222222;border-color:#3366cc;box-shadow:inset 0 0 0 1px #3366cc,inset 0 0 0 2px #ffffff}.mw-ui-button:active,.mw-ui-button.is-on,.mw-ui-button.mw-ui-checked{background-color:#d9d9d9;color:#000000;border-color:#72777d;box-shadow:none}.mw-ui-button:disabled{background-color:#c8ccd1;color:#fff;border-color:#c8ccd1}.mw-ui-button:disabled:hover,.mw-ui-button:disabled:active{background-color:#c8ccd1;color:#fff;box-shadow:none;border-color:#c8ccd1}.mw-ui-button:focus{outline-width:0}.mw-ui-button:focus::-moz-focus-inner{border-color:transparent;padding:0}.mw-ui-button:not( :disabled ){-webkit-transition:background-color 100ms,color 100ms,border-color 100ms,box-shadow 100ms;-moz-transition:background-color 100ms,color 100ms,border-color 100ms,box-shadow 100ms;transition:background-color 100ms,color 100ms,border-color 100ms,box-shadow 100ms}.mw-ui-button:disabled{text-shadow:none;cursor:default}.mw-ui-button.mw-ui-big{font-size:1.3em}.mw-ui-button.mw-ui-block{display:block;width:100%;margin-left:auto;margin-right:auto}.mw-ui-button.mw-ui-progressive{background-color:#3366cc;color:#fff;border:1px solid #3366cc}.mw-ui-button.mw-ui-progressive:hover{background-color:#447ff5;border-color:#447ff5}.mw-ui-button.mw-ui-progressive:focus{box-shadow:inset 0 0 0 1px #3366cc,inset 0 0 0 2px #ffffff}.mw-ui-button.mw-ui-progressive:active,.mw-ui-button.mw-ui-progressive.is-on,.mw-ui-button.mw-ui-progressive.mw-ui-checked{background-color:#2a4b8d;border-color:#2a4b8d;box-shadow:none}.mw-ui-button.mw-ui-progressive:disabled{background-color:#c8ccd1;color:#fff;border-color:#c8ccd1}.mw-ui-button.mw-ui-progressive:disabled:hover,.mw-ui-button.mw-ui-progressive:disabled:active,.mw-ui-button.mw-ui-progressive:disabled.mw-ui-checked{background-color:#c8ccd1;color:#fff;border-color:#c8ccd1;box-shadow:none}.mw-ui-button.mw-ui-progressive.mw-ui-quiet{color:#222222}.mw-ui-button.mw-ui-progressive.mw-ui-quiet:hover{background-color:transparent;color:#447ff5}.mw-ui-button.mw-ui-progressive.mw-ui-quiet:active,.mw-ui-button.mw-ui-progressive.mw-ui-quiet.mw-ui-checked{color:#2a4b8d}.mw-ui-button.mw-ui-progressive.mw-ui-quiet:focus{background-color:transparent;color:#3366cc}.mw-ui-button.mw-ui-progressive.mw-ui-quiet:disabled{color:#c8ccd1}.mw-ui-button.mw-ui-destructive{background-color:#dd3333;color:#fff;border:1px solid #dd3333}.mw-ui-button.mw-ui-destructive:hover{background-color:#ff4242;border-color:#ff4242}.mw-ui-button.mw-ui-destructive:focus{box-shadow:inset 0 0 0 1px #dd3333,inset 0 0 0 2px #ffffff}.mw-ui-button.mw-ui-destructive:active,.mw-ui-button.mw-ui-destructive.is-on,.mw-ui-button.mw-ui-destructive.mw-ui-checked{background-color:#b32424;border-color:#b32424;box-shadow:none}.mw-ui-button.mw-ui-destructive:disabled{background-color:#c8ccd1;color:#fff;border-color:#c8ccd1}.mw-ui-button.mw-ui-destructive:disabled:hover,.mw-ui-button.mw-ui-destructive:disabled:active,.mw-ui-button.mw-ui-destructive:disabled.mw-ui-checked{background-color:#c8ccd1;color:#fff;border-color:#c8ccd1;box-shadow:none}.mw-ui-button.mw-ui-destructive.mw-ui-quiet{color:#222222}.mw-ui-button.mw-ui-destructive.mw-ui-quiet:hover{background-color:transparent;color:#ff4242}.mw-ui-button.mw-ui-destructive.mw-ui-quiet:active,.mw-ui-button.mw-ui-destructive.mw-ui-quiet.mw-ui-checked{color:#b32424}.mw-ui-button.mw-ui-destructive.mw-ui-quiet:focus{background-color:transparent;color:#dd3333}.mw-ui-button.mw-ui-destructive.mw-ui-quiet:disabled{color:#c8ccd1}.mw-ui-button.mw-ui-quiet{background:transparent;border:0;text-shadow:none;color:#222222}.mw-ui-button.mw-ui-quiet:hover{background-color:transparent;color:#444444}.mw-ui-button.mw-ui-quiet:active,.mw-ui-button.mw-ui-quiet.mw-ui-checked{color:#000000}.mw-ui-button.mw-ui-quiet:focus{background-color:transparent;color:#222222}.mw-ui-button.mw-ui-quiet:disabled{color:#c8ccd1}.mw-ui-button.mw-ui-quiet:hover,.mw-ui-button.mw-ui-quiet:focus{box-shadow:none}.mw-ui-button.mw-ui-quiet:active,.mw-ui-button.mw-ui-quiet:disabled{background:transparent}input.mw-ui-button::-moz-focus-inner,button.mw-ui-button::-moz-focus-inner{margin-top:-1px;margin-bottom:-1px}a.mw-ui-button{text-decoration:none}a.mw-ui-button:hover,a.mw-ui-button:focus{text-decoration:none}.mw-ui-button-group > *{min-width:48px;border-radius:0;float:left}.mw-ui-button-group > *:first-child{border-top-left-radius:2px;border-bottom-left-radius:2px}.mw-ui-button-group > *:not( :first-child ){border-left:0}.mw-ui-button-group > *:last-child{border-top-right-radius:2px;border-bottom-right-radius:2px}.mw-ui-button-group .is-on .button{cursor:default}
.mw-ui-icon{position:relative;line-height:1.5em;min-height:1.5em;min-width:1.5em}.mw-ui-icon.mw-ui-icon-element{text-indent:-999px;overflow:hidden;width:3.5em;min-width:3.5em;max-width:3.5em}.mw-ui-icon.mw-ui-icon-element:before{left:0;right:0;position:absolute;margin:0 1em}.mw-ui-icon.mw-ui-icon-element.mw-ui-icon-large{width:4.625em;min-width:4.625em;max-width:4.625em;line-height:4.625em;min-height:4.625em}.mw-ui-icon.mw-ui-icon-element.mw-ui-icon-large:before{min-height:4.625em}.mw-ui-icon.mw-ui-icon-before:before,.mw-ui-icon.mw-ui-icon-element:before{background-position:50% 50%;background-repeat:no-repeat;background-size:100% auto;float:left;display:block;min-height:1.5em;content:''}.mw-ui-icon.mw-ui-icon-before:before{position:relative;width:1.5em;margin-right:1em}.mw-ui-icon.mw-ui-icon-small:before{background-size:66.67% auto}</STYLE><STYLE>
.suggestions a.mw-searchSuggest-link,.suggestions a.mw-searchSuggest-link:hover,.suggestions a.mw-searchSuggest-link:active,.suggestions a.mw-searchSuggest-link:focus{color:#000;text-decoration:none}.suggestions-result-current a.mw-searchSuggest-link,.suggestions-result-current a.mw-searchSuggest-link:hover,.suggestions-result-current a.mw-searchSuggest-link:active,.suggestions-result-current a.mw-searchSuggest-link:focus{color:#fff}.suggestions a.mw-searchSuggest-link .special-query{ overflow:hidden;text-overflow:ellipsis;white-space:nowrap}
#uls-settings-block{background-color:#f8f9fa;border-top:1px solid #c8ccd1;padding-left:10px;line-height:1.2em;border-radius:0 0 2px 2px}#uls-settings-block div.display-settings-block,#uls-settings-block div.input-settings-block{display:inline-block;margin:8px 15px;color:#54595d}#uls-settings-block div.display-settings-block:hover,#uls-settings-block div.input-settings-block:hover{color:#222}
.mw-mmv-overlay{position:fixed;top:0;left:0;right:0;bottom:0;z-index:1000;background-color:#000}body.mw-mmv-lightbox-open{overflow-y:auto;  }body.mw-mmv-lightbox-open #mw-page-base,body.mw-mmv-lightbox-open #mw-head-base,body.mw-mmv-lightbox-open #mw-navigation,body.mw-mmv-lightbox-open #content,body.mw-mmv-lightbox-open #footer,body.mw-mmv-lightbox-open #globalWrapper{ display:none}body.mw-mmv-lightbox-open > *{ display:none}body.mw-mmv-lightbox-open > .mw-mmv-overlay,body.mw-mmv-lightbox-open > .mw-mmv-wrapper{display:block}.mw-mmv-filepage-buttons{margin-top:5px}.mw-mmv-filepage-buttons .mw-mmv-view-expanded,.mw-mmv-filepage-buttons .mw-mmv-view-config{display:block;line-height:inherit}.mw-mmv-filepage-buttons .mw-mmv-view-expanded.mw-ui-icon:before{background-image:url("data:image/svg+xml,%3C%3Fxml version=%221.0%22 encoding=%22UTF-8%22 standalone=%22no%22%3F%3E%0A%3Csvg xmlns=%22http://www.w3.org/2000/svg%22 viewBox=%220 0 1024 768%22%3E%0A %3Cg fill=%22%2372777d%22%3E%0A %3Cpath d=%22M851.2 71.6L690.7 232.1l-40.1-40.3-9.6 164.8 164.8-9.3-40.3-40.4L926 146.4l58.5 58.5L997.6 0 792.7 13.1%22/%3E%0A %3Cpath d=%22M769.6 89.3H611.9l70.9 70.8 7.9 7.5m-47.1 234.6l-51.2 3 3-51.2 9.4-164.4 5.8-100.3H26.4V768h883.1V387l-100.9 5.8-165 9.4zM813.9 678H113.6l207.2-270.2 31.5-12.9L548 599.8l105.9-63.2 159.8 140.8.2.6zm95.6-291.9V228l-79.1 78.9 7.8 7.9%22/%3E%0A %3C/g%3E%0A%3C/svg%3E%0A")}.mw-mmv-filepage-buttons .mw-mmv-view-config.mw-ui-icon:before{background-image:url("data:image/svg+xml,%3C%3Fxml version=%221.0%22 encoding=%22UTF-8%22 standalone=%22no%22%3F%3E%0A%3Csvg xmlns=%22http://www.w3.org/2000/svg%22 viewBox=%220 0 1024 768%22%3E%0A %3Cpath d=%22M897 454.6V313.4L810.4 299c-6.4-23.3-16-45.7-27.3-65.8l50.5-71.4-99.4-100.2-71.4 50.5c-20.9-11.2-42.5-20.9-65.8-27.3L582.6-1H441.4L427 85.6c-23.3 6.4-45.7 16-65.8 27.3l-71.4-50.5-100.3 99.5 50.5 71.4c-11.2 20.9-20.9 42.5-27.3 66.6L127 313.4v141.2l85.8 14.4c6.4 23.3 16 45.7 27.3 66.6L189.6 607l99.5 99.5 71.4-50.5c20.9 11.2 42.5 20.9 66.6 27.3l14.4 85.8h141.2l14.4-86.6c23.3-6.4 45.7-16 65.8-27.3l71.4 50.5 99.5-99.5-50.5-71.4c11.2-20.9 20.9-42.5 27.3-66.6l86.4-13.6zm-385 77c-81.8 0-147.6-66.6-147.6-147.6 0-81.8 66.6-147.6 147.6-147.6S659.6 302.2 659.6 384 593.8 531.6 512 531.6z%22 fill=%22%2372777d%22/%3E%0A%3C/svg%3E%0A");opacity:0.75}.mw-mmv-filepage-buttons .mw-mmv-view-config.mw-ui-icon:before:hover{opacity:1}
#mwe-popups-svg{position:absolute;top:-1000px}.mwe-popups-settings-icon{border-radius:2px;font-size:16px; margin-right:-0.75em}.mwe-popups-settings-icon:hover{background-color:#eaecf0}.mwe-popups-settings-icon:active{background-color:#c8ccd1}.mwe-popups-sade-face-icon{display:block;width:37px;height:27px;margin:16px 16px 0;background-position:center center;background-repeat:no-repeat;background-image:url(/w/extensions/Popups/resources/ext.popups/images/sad-face.png?3984d);background-image:linear-gradient(transparent,transparent),url("data:image/svg+xml,%3C%3Fxml version=%221.0%22 encoding=%22UTF-8%22%3F%3E%0A%3Csvg xmlns=%22http://www.w3.org/2000/svg%22 width=%2237%22 height=%2227%22 viewBox=%220 0 37 27%22%3E%0A%09%3Ctitle%3Esad face%3C/title%3E%0A%09%3Cpath fill=%22%23c8ccd1%22 fill-rule=%22evenodd%22 d=%22M5.475.7v20.075L0 26.25h31.025c3.102 0 5.475-2.372 5.475-5.475V.7H5.475zm20.44 4.562c1.277 0 2.19 1.095 2.19 2.19 0 1.096-.913 2.373-2.19 2.373-1.278 0-2.19-1.095-2.19-2.19s1.095-2.373 2.19-2.373zm-9.855 0c1.277 0 2.19 1.095 2.19 2.19 0 1.096-1.095 2.373-2.19 2.373s-2.19-1.095-2.19-2.19.913-2.373 2.19-2.373zm4.928 8.213c-7.153 0-8.415 7.012-8.415 7.012s2.805-1.403 8.415-1.403c5.61 0 8.414 1.403 8.414 1.403S28 13.475 20.988 13.475z%22/%3E%0A%3C/svg%3E%0A")}.mwe-popups{background:#fff;position:absolute;z-index:110;-webkit-box-shadow:0 30px 90px -20px rgba(0,0,0,0.3),0 0 1px #a2a9b1;box-shadow:0 30px 90px -20px rgba(0,0,0,0.3),0 0 1px #a2a9b1;padding:0;display:none;font-size:14px;line-height:20px;min-width:300px;border-radius:2px; }.mwe-popups .mwe-popups-container{color:#222222;margin-top:-9px;padding-top:9px;text-decoration:none}.mwe-popups .mwe-popups-container footer{padding:16px;margin:0;font-size:10px;position:absolute;bottom:0; left:0}.mwe-popups .mwe-popups-container footer .mwe-popups-settings-icon{float:right}.mwe-popups .mwe-popups-extract{margin:16px;display:block;color:#222222;text-decoration:none;position:relative;   }.mwe-popups .mwe-popups-extract:hover{text-decoration:none}.mwe-popups .mwe-popups-extract:after{content:' ';position:absolute;bottom:0;width:25%;height:20px;background-color:transparent}.mwe-popups .mwe-popups-extract[dir='ltr']:after{ right:0; background-image:-webkit-linear-gradient(to right,rgba(255,255,255,0),#ffffff 50%); background-image:-moz-linear-gradient(to right,rgba(255,255,255,0),#ffffff 50%); background-image:-o-linear-gradient(to right,rgba(255,255,255,0),#ffffff 50%); background-image:linear-gradient(to right,rgba(255,255,255,0),#ffffff 50%)}.mwe-popups .mwe-popups-extract[dir='rtl']:after{ left:0; background-image:-webkit-linear-gradient(to left,rgba(255,255,255,0),#ffffff 50%); background-image:-moz-linear-gradient(to left,rgba(255,255,255,0),#ffffff 50%); background-image:-o-linear-gradient(to left,rgba(255,255,255,0),#ffffff 50%); background-image:linear-gradient(to left,rgba(255,255,255,0),#ffffff 50%)}.mwe-popups .mwe-popups-extract p{margin:0}.mwe-popups .mwe-popups-extract ul,.mwe-popups .mwe-popups-extract ol,.mwe-popups .mwe-popups-extract li,.mwe-popups .mwe-popups-extract dl,.mwe-popups .mwe-popups-extract dd,.mwe-popups .mwe-popups-extract dt{margin-top:0;margin-bottom:0}.mwe-popups svg{overflow:hidden}.mwe-popups.mwe-popups-is-tall{width:450px}.mwe-popups.mwe-popups-is-tall > div > a > svg{vertical-align:middle}.mwe-popups.mwe-popups-is-tall .mwe-popups-extract{width:215px;height:180px;overflow:hidden; float:left}.mwe-popups.mwe-popups-is-tall footer{width:215px}.mwe-popups.mwe-popups-is-not-tall{width:320px}.mwe-popups.mwe-popups-is-not-tall .mwe-popups-extract{max-height:140px;overflow:hidden;margin-bottom:47px;padding-bottom:0}.mwe-popups.mwe-popups-is-not-tall footer{width:290px}.mwe-popups.mwe-popups-is-empty .mwe-popups-extract{padding-top:4px;margin-bottom:60px}.mwe-popups.mwe-popups-is-empty .mwe-popups-read-link{font-weight:bold;font-size:12px}.mwe-popups.mwe-popups-is-empty .mwe-popups-extract:hover + footer .mwe-popups-read-link{text-decoration:underline}.mwe-popups.mwe-popups-no-image-tri:after{content:'';position:absolute;border:11px solid transparent;border-top:0;border-bottom:11px solid #ffffff;top:-7px; left:7px}.mwe-popups.mwe-popups-no-image-tri:before{content:'';position:absolute;border:8px solid transparent;border-top:0;border-bottom:8px solid #a2a9b1;top:-8px; left:10px}.mwe-popups.flipped_x.mwe-popups-no-image-tri:after{ left:auto; right:7px}.mwe-popups.flipped_x.mwe-popups-no-image-tri:before{ left:auto; right:10px}.mwe-popups.mwe-popups-image-tri:before{z-index:111;content:'';position:absolute;border:9px solid transparent;border-top:0;border-bottom:9px solid #a2a9b1;top:-9px; left:9px}.mwe-popups.mwe-popups-image-tri:after{content:'';position:absolute;border:12px solid transparent;border-top:0;border-bottom:12px solid #ffffff;top:-8px; left:6px;z-index:112}.mwe-popups.mwe-popups-image-tri.flipped_x:before{z-index:111;content:'';position:absolute;border:9px solid transparent;border-top:0;border-bottom:9px solid #a2a9b1;top:-9px; left:273px}.mwe-popups.mwe-popups-image-tri.flipped_x:after{content:'';position:absolute;border:12px solid transparent;border-top:0;border-bottom:12px solid #ffffff;top:-8px; left:269px;z-index:112}.mwe-popups.mwe-popups-image-tri .mwe-popups-extract{padding-top:32px;margin-top:190px}.mwe-popups.mwe-popups-image-tri > div > a > svg{margin-top:-8px;position:absolute;z-index:113; left:0}.mwe-popups.flipped_x.mwe-popups-is-tall{min-height:242px}.mwe-popups.flipped_x.mwe-popups-is-tall:before{z-index:111;content:'';position:absolute;border:9px solid transparent;border-top:0;border-bottom:9px solid #a2a9b1;top:-9px; left:420px}.mwe-popups.flipped_x.mwe-popups-is-tall > div > a > svg{margin:0;margin-top:-8px;margin-bottom:-7px;position:absolute;z-index:113; right:0}.mwe-popups.flipped_x_y:before{z-index:111;content:'';position:absolute;border:9px solid transparent;border-bottom:0;border-top:9px solid #a2a9b1;bottom:-9px; left:272px}.mwe-popups.flipped_x_y:after{content:'';position:absolute;border:12px solid transparent;border-bottom:0;border-top:12px solid #ffffff;bottom:-8px; left:269px;z-index:112}.mwe-popups.flipped_x_y.mwe-popups-is-tall{min-height:242px}.mwe-popups.flipped_x_y.mwe-popups-is-tall:after{z-index:112;content:'';position:absolute;border:12px solid transparent;border-bottom:0;border-top:12px solid #ffffff;bottom:-8px; left:417px}.mwe-popups.flipped_x_y.mwe-popups-is-tall:before{z-index:111;content:'';position:absolute;border:9px solid transparent;border-bottom:0;border-top:9px solid #a2a9b1;bottom:-9px; left:420px}.mwe-popups.flipped_x_y.mwe-popups-is-tall > div > a > svg{position:absolute;z-index:113;margin:0;margin-bottom:-9px; right:0}.mwe-popups.flipped_y:after{content:'';position:absolute;border:11px solid transparent;border-bottom:0;border-top:11px solid #ffffff;bottom:-7px; left:7px}.mwe-popups.flipped_y:before{content:'';position:absolute;border:8px solid transparent;border-bottom:0;border-top:8px solid #a2a9b1;bottom:-8px; left:10px} @-webkit-keyframes mwe-popups-fade-in-up{0%{opacity:0;-webkit-transform:translate(0,20px);-moz-transform:translate(0,20px);-ms-transform:translate(0,20px);transform:translate(0,20px)}100%{opacity:1;-webkit-transform:translate(0,0);-moz-transform:translate(0,0);-ms-transform:translate(0,0);transform:translate(0,0)}}@-moz-keyframes mwe-popups-fade-in-up{0%{opacity:0;-webkit-transform:translate(0,20px);-moz-transform:translate(0,20px);-ms-transform:translate(0,20px);transform:translate(0,20px)}100%{opacity:1;-webkit-transform:translate(0,0);-moz-transform:translate(0,0);-ms-transform:translate(0,0);transform:translate(0,0)}}@keyframes mwe-popups-fade-in-up{0%{opacity:0;-webkit-transform:translate(0,20px);-moz-transform:translate(0,20px);-ms-transform:translate(0,20px);transform:translate(0,20px)}100%{opacity:1;-webkit-transform:translate(0,0);-moz-transform:translate(0,0);-ms-transform:translate(0,0);transform:translate(0,0)}}@-webkit-keyframes mwe-popups-fade-in-down{0%{opacity:0;-webkit-transform:translate(0,-20px);-moz-transform:translate(0,-20px);-ms-transform:translate(0,-20px);transform:translate(0,-20px)}100%{opacity:1;-webkit-transform:translate(0,0);-moz-transform:translate(0,0);-ms-transform:translate(0,0);transform:translate(0,0)}}@-moz-keyframes mwe-popups-fade-in-down{0%{opacity:0;-webkit-transform:translate(0,-20px);-moz-transform:translate(0,-20px);-ms-transform:translate(0,-20px);transform:translate(0,-20px)}100%{opacity:1;-webkit-transform:translate(0,0);-moz-transform:translate(0,0);-ms-transform:translate(0,0);transform:translate(0,0)}}@keyframes mwe-popups-fade-in-down{0%{opacity:0;-webkit-transform:translate(0,-20px);-moz-transform:translate(0,-20px);-ms-transform:translate(0,-20px);transform:translate(0,-20px)}100%{opacity:1;-webkit-transform:translate(0,0);-moz-transform:translate(0,0);-ms-transform:translate(0,0);transform:translate(0,0)}}@-webkit-keyframes mwe-popups-fade-out-down{0%{opacity:1;-webkit-transform:translate(0,0);-moz-transform:translate(0,0);-ms-transform:translate(0,0);transform:translate(0,0)}100%{opacity:0;-webkit-transform:translate(0,20px);-moz-transform:translate(0,20px);-ms-transform:translate(0,20px);transform:translate(0,20px)}}@-moz-keyframes mwe-popups-fade-out-down{0%{opacity:1;-webkit-transform:translate(0,0);-moz-transform:translate(0,0);-ms-transform:translate(0,0);transform:translate(0,0)}100%{opacity:0;-webkit-transform:translate(0,20px);-moz-transform:translate(0,20px);-ms-transform:translate(0,20px);transform:translate(0,20px)}}@keyframes mwe-popups-fade-out-down{0%{opacity:1;-webkit-transform:translate(0,0);-moz-transform:translate(0,0);-ms-transform:translate(0,0);transform:translate(0,0)}100%{opacity:0;-webkit-transform:translate(0,20px);-moz-transform:translate(0,20px);-ms-transform:translate(0,20px);transform:translate(0,20px)}}@-webkit-keyframes mwe-popups-fade-out-up{0%{opacity:1;-webkit-transform:translate(0,0);-moz-transform:translate(0,0);-ms-transform:translate(0,0);transform:translate(0,0)}100%{opacity:0;-webkit-transform:translate(0,-20px);-moz-transform:translate(0,-20px);-ms-transform:translate(0,-20px);transform:translate(0,-20px)}}@-moz-keyframes mwe-popups-fade-out-up{0%{opacity:1;-webkit-transform:translate(0,0);-moz-transform:translate(0,0);-ms-transform:translate(0,0);transform:translate(0,0)}100%{opacity:0;-webkit-transform:translate(0,-20px);-moz-transform:translate(0,-20px);-ms-transform:translate(0,-20px);transform:translate(0,-20px)}}@keyframes mwe-popups-fade-out-up{0%{opacity:1;-webkit-transform:translate(0,0);-moz-transform:translate(0,0);-ms-transform:translate(0,0);transform:translate(0,0)}100%{opacity:0;-webkit-transform:translate(0,-20px);-moz-transform:translate(0,-20px);-ms-transform:translate(0,-20px);transform:translate(0,-20px)}}.mwe-popups-fade-in-up{-webkit-animation:mwe-popups-fade-in-up 0.2s ease forwards;-moz-animation:mwe-popups-fade-in-up 0.2s ease forwards;animation:mwe-popups-fade-in-up 0.2s ease forwards}.mwe-popups-fade-in-down{-webkit-animation:mwe-popups-fade-in-down 0.2s ease forwards;-moz-animation:mwe-popups-fade-in-down 0.2s ease forwards;animation:mwe-popups-fade-in-down 0.2s ease forwards}.mwe-popups-fade-out-down{-webkit-animation:mwe-popups-fade-out-down 0.2s ease forwards;-moz-animation:mwe-popups-fade-out-down 0.2s ease forwards;animation:mwe-popups-fade-out-down 0.2s ease forwards}.mwe-popups-fade-out-up{-webkit-animation:mwe-popups-fade-out-up 0.2s ease forwards;-moz-animation:mwe-popups-fade-out-up 0.2s ease forwards;animation:mwe-popups-fade-out-up 0.2s ease forwards}  #mwe-popups-settings{position:fixed;z-index:1000;background:#fff;width:420px;border:1px solid #a2a9b1;box-shadow:0 2px 2px 0 rgba(0,0,0,0.25);border-radius:2px}#mwe-popups-settings header{-webkit-box-sizing:border-box;-moz-box-sizing:border-box;box-sizing:border-box;border-bottom:1px solid #c8ccd1;position:relative;display:table;width:100%;padding:5px 7px 5px 0}#mwe-popups-settings header > div{display:table-cell;width:3.5em;vertical-align:middle;cursor:pointer}#mwe-popups-settings header h1{border:0;width:100%;font-family:sans-serif;font-size:18px;font-weight:bold;text-align:center}#mwe-popups-settings .mwe-ui-icon-popups-close{opacity:0.87;-webkit-transition:opacity 100ms;-moz-transition:opacity 100ms;transition:opacity 100ms}#mwe-popups-settings .mwe-ui-icon-popups-close:hover{opacity:0.73}#mwe-popups-settings .mwe-ui-icon-popups-close:active{opacity:1}#mwe-popups-settings main{display:block;width:350px;padding:32px 0 24px;margin:0 auto}#mwe-popups-settings main p{color:#54595d;font-size:17px;margin:16px 0 0}#mwe-popups-settings main p:first-child{margin-top:0}#mwe-popups-settings main form img,#mwe-popups-settings main form input,#mwe-popups-settings main form label{vertical-align:top}#mwe-popups-settings main form img{margin-right:60px}#mwe-popups-settings main form input{display:inline-block;margin:0 10px 0 0;padding:0}#mwe-popups-settings main form label{font-size:13px;display:inline-block;line-height:16px;width:300px}#mwe-popups-settings main form label > span{color:#000;font-size:18px;font-weight:bold;display:block;margin-bottom:5px;line-height:18px}.mwe-popups-settings-help{background-image:url(/w/extensions/Popups/resources/ext.popups/images/footer-ltr.png?3533c);background-image:linear-gradient(transparent,transparent),url("data:image/svg+xml,%3C%3Fxml version=%221.0%22 encoding=%22UTF-8%22%3F%3E%0A%3Csvg xmlns=%22http://www.w3.org/2000/svg%22 width=%22230%22 height=%22179%22 xmlns:xlink=%22http://www.w3.org/1999/xlink%22 viewBox=%220 0 230 179%22%3E%0A%09%3Cdefs%3E%0A%09%09%3Crect id=%22a%22 width=%22201%22 height=%2213%22 rx=%222%22/%3E%0A%09%09%3Crect id=%22b%22 width=%22201%22 height=%22169%22 y=%2210%22 rx=%222%22/%3E%0A%09%09%3Crect id=%22c%22 width=%2230%22 height=%222%22 x=%22135%22 y=%22158%22 rx=%221%22/%3E%0A%09%3C/defs%3E%0A%09%3Cg fill=%22none%22 fill-rule=%22evenodd%22%3E%0A%09%09%3Cg transform=%22matrix%281 0 0 -1 0 13%29%22%3E%0A%09%09%09%3Cuse fill=%22%23f8f9fa%22 xlink:href=%22%23a%22/%3E%0A%09%09%09%3Crect width=%22199%22 height=%2211%22 x=%221%22 y=%221%22 stroke=%22%23a2a9b1%22 stroke-width=%222%22 rx=%222%22/%3E%0A%09%09%3C/g%3E%0A%09%09%3Cuse fill=%22%23fff%22 xlink:href=%22%23b%22/%3E%0A%09%09%3Crect width=%22199%22 height=%22167%22 x=%221%22 y=%2211%22 stroke=%22%23a2a9b1%22 stroke-width=%222%22 rx=%222%22/%3E%0A%09%09%3Cg opacity=%22.4%22 transform=%22translate%2867 35%29%22%3E%0A%09%09%09%3Crect width=%2273%22 height=%222%22 y=%227%22 fill=%22%23c8ccd1%22 rx=%221%22/%3E%0A%09%09%09%3Crect width=%2281%22 height=%222%22 y=%2231%22 fill=%22%2372777d%22 rx=%221%22/%3E%0A%09%09%09%3Crect width=%2232%22 height=%222%22 y=%2285%22 fill=%22%2372777d%22 rx=%221%22/%3E%0A%09%09%09%3Crect width=%2273%22 height=%222%22 x=%2235%22 y=%2285%22 fill=%22%2372777d%22 rx=%221%22/%3E%0A%09%09%09%3Crect width=%2217%22 height=%222%22 y=%2245%22 fill=%22%2372777d%22 rx=%221%22/%3E%0A%09%09%09%3Crect width=%2217%22 height=%222%22 x=%2291%22 y=%2245%22 fill=%22%2372777d%22 rx=%221%22/%3E%0A%09%09%09%3Crect width=%2268%22 height=%222%22 x=%2220%22 y=%2245%22 fill=%22%2372777d%22 rx=%221%22/%3E%0A%09%09%09%3Crect width=%2217%22 height=%222%22 y=%2278%22 fill=%22%2372777d%22 rx=%221%22/%3E%0A%09%09%09%3Crect width=%2237%22 height=%222%22 x=%2272%22 y=%2278%22 fill=%22%2372777d%22 rx=%221%22/%3E%0A%09%09%09%3Crect width=%2249%22 height=%222%22 x=%2220%22 y=%2278%22 fill=%22%2372777d%22 rx=%221%22/%3E%0A%09%09%09%3Crect width=%2224%22 height=%222%22 x=%2284%22 y=%2231%22 fill=%22%2372777d%22 rx=%221%22 transform=%22matrix%28-1 0 0 1 192 0%29%22/%3E%0A%09%09%09%3Crect width=%2281%22 height=%222%22 y=%2266%22 fill=%22%2372777d%22 rx=%221%22/%3E%0A%09%09%09%3Crect width=%2214%22 height=%222%22 x=%2254%22 y=%2224%22 fill=%22%2372777d%22 rx=%221%22/%3E%0A%09%09%09%3Crect width=%2237%22 height=%222%22 x=%2271%22 y=%2224%22 fill=%22%2372777d%22 rx=%221%22/%3E%0A%09%09%09%3Crect width=%2251%22 height=%222%22 y=%2224%22 fill=%22%2372777d%22 rx=%221%22/%3E%0A%09%09%09%3Crect width=%22108%22 height=%222%22 y=%2259%22 fill=%22%2372777d%22 rx=%221%22/%3E%0A%09%09%09%3Crect width=%22108%22 height=%222%22 y=%2252%22 fill=%22%2372777d%22 rx=%221%22/%3E%0A%09%09%09%3Crect width=%22108%22 height=%222%22 y=%2292%22 fill=%22%2372777d%22 rx=%221%22/%3E%0A%09%09%09%3Crect width=%22108%22 height=%222%22 y=%2238%22 fill=%22%2372777d%22 rx=%221%22/%3E%0A%09%09%09%3Crect width=%2251%22 height=%222%22 fill=%22%2372777d%22 rx=%221%22/%3E%0A%09%09%3C/g%3E%0A%09%09%3Crect width=%2230%22 height=%222%22 x=%2267%22 y=%22158%22 fill=%22%2372777d%22 opacity=%22.4%22 rx=%221%22/%3E%0A%09%09%3Crect width=%2230%22 height=%222%22 x=%2299%22 y=%22158%22 fill=%22%2372777d%22 opacity=%22.4%22 rx=%221%22/%3E%0A%09%09%3Cuse fill=%22%2336c%22 xlink:href=%22%23c%22/%3E%0A%09%09%3Crect width=%2233%22 height=%225%22 x=%22133.5%22 y=%22156.5%22 stroke=%22%23ffc057%22 stroke-opacity=%22.447%22 stroke-width=%223%22 rx=%222.5%22/%3E%0A%09%09%3Ccircle cx=%2234%22 cy=%2249%22 r=%2219%22 fill=%22%23eaecf0%22/%3E%0A%09%09%3Cg fill=%22%23a2a9b1%22 transform=%22translate%285 5%29%22%3E%0A%09%09%09%3Ccircle cx=%221.5%22 cy=%221.5%22 r=%221.5%22/%3E%0A%09%09%09%3Ccircle cx=%226%22 cy=%221.5%22 r=%221.5%22/%3E%0A%09%09%09%3Ccircle cx=%2210.5%22 cy=%221.5%22 r=%221.5%22/%3E%0A%09%09%3C/g%3E%0A%09%09%3Cpath stroke=%22%23ff00af%22 d=%22M174.5 159.5h54.01%22 stroke-linecap=%22square%22/%3E%0A%09%3C/g%3E%0A%3C/svg%3E%0A");background-position:top left;background-repeat:no-repeat;background-size:180px 140px;font-size:13px;font-weight:800;height:140px;margin:40px;position:relative}.mwe-popups-settings-help p{left:180px;bottom:20px;position:absolute}.mwe-popups-overlay{background-color:rgba(255,255,255,0.9);z-index:999;position:fixed;height:100%;width:100%;top:0;bottom:0;left:0;right:0}#mwe-popups-settings{font-size:0.875em}</STYLE><META name="ResourceLoaderDynamicStyles" content="" />
<LINK rel="stylesheet" href="/w/load.php?debug=false&lang=en&modules=ext.gadget.charinsert-styles&only=styles&skin=vector" />
<LINK rel="stylesheet" href="/w/load.php?debug=false&lang=en&modules=site.styles&only=styles&skin=vector" />
<META name="generator" content="MediaWiki 1.31.0-wmf.12" />
<META name="referrer" content="origin-when-cross-origin" />
<LINK rel="alternate" href="android-app://org.wikipedia/http/en.m.wikipedia.org/wiki/Red%E2%80%93black_tree" />
<LINK rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Red%E2%80%93black_tree&action=edit" />
<LINK rel="edit" title="Edit this page" href="/w/index.php?title=Red%E2%80%93black_tree&action=edit" />
<LINK rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png" />
<LINK rel="shortcut icon" href="/static/favicon/wikipedia.ico" />
<LINK rel="search" type="application/opensearchdescription+xml" href="/w/opensearch_desc.php" title="Wikipedia (en)" />
<LINK rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd" />
<LINK rel="license" href="//creativecommons.org/licenses/by-sa/3.0/" />
<LINK rel="canonical" href="https://en.wikipedia.org/wiki/Red%E2%80%93black_tree" />
<LINK rel="dns-prefetch" href="//login.wikimedia.org" />
<LINK rel="dns-prefetch" href="//meta.wikimedia.org" />
<!--[if lt IE 9]><script src="/w/load.php?debug=false&lang=en&modules=html5shiv&only=scripts&skin=vector&sync=1"></script><![endif]-->
</HEAD>
<BODY class="mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Red–black_tree rootpage-Red–black_tree skin-vector action-view">		<DIV id="mw-page-base" class="noprint"></DIV>
		<DIV id="mw-head-base" class="noprint"></DIV>
		<DIV id="content" class="mw-body" role="main">
			<A id="top"></A>
			<DIV id="siteNotice" class="mw-body-content"><DIV id="centralNotice"></DIV><!-- CentralNotice --></DIV><DIV class="mw-indicators mw-body-content">
</DIV>
<H1 id="firstHeading" class="firstHeading" lang="en">Red–black tree</H1>			<DIV id="bodyContent" class="mw-body-content">
				<DIV id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</DIV>				<DIV id="contentSub"></DIV>
								<DIV id="jump-to-nav" class="mw-jump">
					Jump to:					<A href="#mw-head">navigation</A>, 					<A href="#p-search">search</A>
				</DIV>
				<DIV id="mw-content-text" lang="en" dir="ltr" class="mw-content-ltr"><DIV class="mw-parser-output"><TABLE class="infobox" style="width:22em">
<TBODY><TR>
<TH colspan="2" style="text-align:center;font-size:125%;font-weight:bold">Red–black tree</TH>
</TR>
<TR>
<TH scope="row"><A href="/wiki/List_of_data_structures" title="List of data structures">Type</A></TH>
<TD>tree</TD>
</TR>
<TR>
<TH scope="row">Invented</TH>
<TD>1972</TD>
</TR>
<TR>
<TH scope="row">Invented by</TH>
<TD><A href="/wiki/Rudolf_Bayer" title="Rudolf Bayer">Rudolf Bayer</A></TD>
</TR>
<TR>
<TH colspan="2" style="text-align:center"><A href="/wiki/Time_complexity" title="Time complexity">Time complexity</A> in <A href="/wiki/Big_O_notation" title="Big O notation">big O notation</A></TH>
</TR>
<TR>
<TD colspan="2" style="text-align:center">
<TABLE class="infobox" style="padding:0;border:none;margin:auto;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent">
<TBODY><TR>
<TH scope="row" style="white-space:nowrap;">Algorithm</TH>
<TD></TD>
<TD><B>Average</B></TD>
<TD><B>Worst case</B></TD>
</TR>
<TR>
<TH scope="row" style="white-space:nowrap;">Space</TH>
<TD></TD>
<TD><SPAN class="texhtml">O(<I>n</I>)</SPAN></TD>
<TD><SPAN class="texhtml">O(<I>n</I>)</SPAN></TD>
</TR>
<TR>
<TH scope="row" style="white-space:nowrap;">Search</TH>
<TD></TD>
<TD><SPAN class="texhtml">O(log <I>n</I>)</SPAN><SUP id="cite_ref-wiscurl_1-0" class="reference"><A href="#cite_note-wiscurl-1">[1]</A></SUP></TD>
<TD><SPAN class="texhtml">O(log <I>n</I>)</SPAN><SUP id="cite_ref-wiscurl_1-1" class="reference"><A href="#cite_note-wiscurl-1">[1]</A></SUP></TD>
</TR>
<TR>
<TH scope="row" style="white-space:nowrap;">Insert</TH>
<TD></TD>
<TD><SPAN class="texhtml">O(log <I>n</I>)</SPAN><SUP id="cite_ref-wiscurl_1-2" class="reference"><A href="#cite_note-wiscurl-1">[1]</A></SUP></TD>
<TD><SPAN class="texhtml">O(log <I>n</I>)</SPAN><SUP id="cite_ref-wiscurl_1-3" class="reference"><A href="#cite_note-wiscurl-1">[1]</A></SUP></TD>
</TR>
<TR>
<TH scope="row" style="white-space:nowrap;">Delete</TH>
<TD></TD>
<TD><SPAN class="texhtml">O(log <I>n</I>)</SPAN><SUP id="cite_ref-wiscurl_1-4" class="reference"><A href="#cite_note-wiscurl-1">[1]</A></SUP></TD>
<TD><SPAN class="texhtml">O(log <I>n</I>)</SPAN><SUP id="cite_ref-wiscurl_1-5" class="reference"><A href="#cite_note-wiscurl-1">[1]</A></SUP></TD>
</TR>
</TBODY></TABLE>
</TD>
</TR>
</TBODY></TABLE>
<P>A <B>red–black tree</B> is a kind of <A href="/wiki/Self-balancing_binary_search_tree" title="Self-balancing binary search tree">self-balancing binary search tree</A> in <A href="/wiki/Computer_science" title="Computer science">computer science</A>. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.<SUP id="cite_ref-:0_2-0" class="reference"><A href="#cite_note-:0-2">[2]</A></SUP></P>
<P>Balance is preserved by painting each node of the tree with one of two colors in a way that satisfies certain properties, which collectively constrain how unbalanced the tree can become in the worst case. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently.</P>
<P>The balancing of the tree is not perfect, but it is good enough to allow it to guarantee searching in <A href="/wiki/Big-O_notation" class="mw-redirect" title="Big-O notation"><SPAN class="texhtml">O(log <I>n</I>)</SPAN></A> time, where <I>n</I> is the total number of elements in the tree. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in <SPAN class="texhtml">O(log <I>n</I>)</SPAN> time.<SUP id="cite_ref-3" class="reference"><A href="#cite_note-3">[3]</A></SUP></P>
<P>Tracking the color of each node requires only 1 bit of information per node because there are only two colors. The tree does not contain any other data specific to its being a red–black tree so its memory footprint is almost identical to a classic (uncolored) <A href="/wiki/Binary_search_tree" title="Binary search tree">binary search tree</A>. In many cases, the additional bit of information can be stored at no additional memory cost.</P>
<P></P>
<DIV id="toc" class="toc">
<DIV class="toctitle">
<H2>Contents</H2>
<SPAN class="toctoggle"> [<A role="button" tabindex="0" class="togglelink">hide</A>] </SPAN></DIV>
<UL>
<LI class="toclevel-1 tocsection-1"><A href="#History"><SPAN class="tocnumber">1</SPAN> <SPAN class="toctext">History</SPAN></A></LI>
<LI class="toclevel-1 tocsection-2"><A href="#Terminology"><SPAN class="tocnumber">2</SPAN> <SPAN class="toctext">Terminology</SPAN></A></LI>
<LI class="toclevel-1 tocsection-3"><A href="#Properties"><SPAN class="tocnumber">3</SPAN> <SPAN class="toctext">Properties</SPAN></A></LI>
<LI class="toclevel-1 tocsection-4"><A href="#Analogy_to_B-trees_of_order_4"><SPAN class="tocnumber">4</SPAN> <SPAN class="toctext">Analogy to B-trees of order 4</SPAN></A></LI>
<LI class="toclevel-1 tocsection-5"><A href="#Applications_and_related_data_structures"><SPAN class="tocnumber">5</SPAN> <SPAN class="toctext">Applications and related data structures</SPAN></A></LI>
<LI class="toclevel-1 tocsection-6"><A href="#Operations"><SPAN class="tocnumber">6</SPAN> <SPAN class="toctext">Operations</SPAN></A>
<UL>
<LI class="toclevel-2 tocsection-7"><A href="#Insertion"><SPAN class="tocnumber">6.1</SPAN> <SPAN class="toctext">Insertion</SPAN></A></LI>
<LI class="toclevel-2 tocsection-8"><A href="#Removal"><SPAN class="tocnumber">6.2</SPAN> <SPAN class="toctext">Removal</SPAN></A></LI>
</UL>
</LI>
<LI class="toclevel-1 tocsection-9"><A href="#Proof_of_asymptotic_bounds"><SPAN class="tocnumber">7</SPAN> <SPAN class="toctext">Proof of asymptotic bounds</SPAN></A></LI>
<LI class="toclevel-1 tocsection-10"><A href="#Set_operations_and_bulk_operations"><SPAN class="tocnumber">8</SPAN> <SPAN class="toctext">Set operations and bulk operations</SPAN></A></LI>
<LI class="toclevel-1 tocsection-11"><A href="#Parallel_algorithms"><SPAN class="tocnumber">9</SPAN> <SPAN class="toctext">Parallel algorithms</SPAN></A></LI>
<LI class="toclevel-1 tocsection-12"><A href="#Popular_culture"><SPAN class="tocnumber">10</SPAN> <SPAN class="toctext">Popular culture</SPAN></A></LI>
<LI class="toclevel-1 tocsection-13"><A href="#See_also"><SPAN class="tocnumber">11</SPAN> <SPAN class="toctext">See also</SPAN></A></LI>
<LI class="toclevel-1 tocsection-14"><A href="#References"><SPAN class="tocnumber">12</SPAN> <SPAN class="toctext">References</SPAN></A></LI>
<LI class="toclevel-1 tocsection-15"><A href="#Further_reading"><SPAN class="tocnumber">13</SPAN> <SPAN class="toctext">Further reading</SPAN></A></LI>
<LI class="toclevel-1 tocsection-16"><A href="#External_links"><SPAN class="tocnumber">14</SPAN> <SPAN class="toctext">External links</SPAN></A></LI>
</UL>
</DIV>
<P></P>
<H2><SPAN class="mw-headline" id="History">History</SPAN><SPAN class="mw-editsection"><SPAN class="mw-editsection-bracket">[</SPAN><A href="/w/index.php?title=Red%E2%80%93black_tree&action=edit&section=1" title="Edit section: History">edit</A><SPAN class="mw-editsection-bracket">]</SPAN></SPAN></H2>
<P>In 1972, <A href="/wiki/Rudolf_Bayer" title="Rudolf Bayer">Rudolf Bayer</A><SUP id="cite_ref-Bayer72_4-0" class="reference"><A href="#cite_note-Bayer72-4">[4]</A></SUP> invented a data structure that was a special order-4 case of a <A href="/wiki/B-tree" title="B-tree">B-tree</A>. These trees maintained all paths from root to leaf with the same number of nodes, creating perfectly balanced trees. However, they were not binary search trees. Bayer called them a "symmetric binary B-tree" in his paper and later they became popular as <A href="/wiki/2%E2%80%933%E2%80%934_tree" title="2–3–4 tree">2-3-4 trees</A> or just 2-4 trees.<SUP id="cite_ref-5" class="reference"><A href="#cite_note-5">[5]</A></SUP></P>
<P>In a 1978 paper, "A Dichromatic Framework for Balanced Trees",<SUP id="cite_ref-GS78_6-0" class="reference"><A href="#cite_note-GS78-6">[6]</A></SUP> <A href="/wiki/Leonidas_J._Guibas" title="Leonidas J. Guibas">Leonidas J. Guibas</A> and <A href="/wiki/Robert_Sedgewick_(computer_scientist)" title="Robert Sedgewick (computer scientist)">Robert Sedgewick</A> derived the red-black tree from the symmetric binary B-tree.<SUP id="cite_ref-7" class="reference"><A href="#cite_note-7">[7]</A></SUP> The color "red" was chosen because it was the best-looking color produced by the color laser printer available to the authors while working at <A href="/wiki/Xerox_PARC" class="mw-redirect" title="Xerox PARC">Xerox PARC</A>.<SUP id="cite_ref-Sedgewick12_8-0" class="reference"><A href="#cite_note-Sedgewick12-8">[8]</A></SUP> Another response from Guibas states that it was because of the red and black pens available to them to draw the trees.<SUP id="cite_ref-9" class="reference"><A href="#cite_note-9">[9]</A></SUP></P>
<P>In 1993, Arne Andersson introduced the idea of right leaning tree to simplify insert and delete operations.<SUP id="cite_ref-10" class="reference"><A href="#cite_note-10">[10]</A></SUP></P>
<P>In 1999, Chris Okasaki showed how to make insert operation purely functional. Its balance function needed to take care of only 4 unbalanced cases and one default balanced case.<SUP id="cite_ref-11" class="reference"><A href="#cite_note-11">[11]</A></SUP></P>
<P>The original algorithm used 8 unbalanced cases, but <A href="#CITEREFCormenLeisersonRivestStein2001">Cormen et al. (2001)</A> reduced that to 6 unbalanced cases.<SUP id="cite_ref-:0_2-1" class="reference"><A href="#cite_note-:0-2">[2]</A></SUP> Sedgewick showed that the insert operation can be implemented in just 46 lines of Java code.<SUP id="cite_ref-Algs1_12-0" class="reference"><A href="#cite_note-Algs1-12">[12]</A></SUP><SUP id="cite_ref-13" class="reference"><A href="#cite_note-13">[13]</A></SUP> In 2008, Sedgewick proposed the <A href="/wiki/Left-leaning_red%E2%80%93black_tree" title="Left-leaning red–black tree">left-leaning red–black tree</A>, leveraging Andersson's idea that simplified algorithms. Sedgewick originally allowed nodes whose two children are red making his trees more like 2-3-4 trees but later this restriction was added making new trees more like 2-3 trees. Sedgewick implemented the insert algorithm in just 33 lines, significantly shortening his original 46 lines of code.<SUP id="cite_ref-14" class="reference"><A href="#cite_note-14">[14]</A></SUP><SUP id="cite_ref-Algs4_15-0" class="reference"><A href="#cite_note-Algs4-15">[15]</A></SUP></P>
<H2><SPAN class="mw-headline" id="Terminology">Terminology</SPAN><SPAN class="mw-editsection"><SPAN class="mw-editsection-bracket">[</SPAN><A href="/w/index.php?title=Red%E2%80%93black_tree&action=edit&section=2" title="Edit section: Terminology">edit</A><SPAN class="mw-editsection-bracket">]</SPAN></SPAN></H2>
<P>A red–black tree is a special type of <A href="/wiki/Binary_tree" title="Binary tree">binary tree</A>, used in <A href="/wiki/Computer_science" title="Computer science">computer science</A> to organize pieces of comparable <A href="/wiki/Data" title="Data">data</A>, such as text fragments or numbers.</P>
<P>The <A href="/wiki/Leaf_node" class="mw-redirect" title="Leaf node">leaf nodes</A> of red–black trees do not contain data. These leaves need not be explicit in computer memory—a null child pointer can encode the fact that this child is a leaf—but it simplifies some algorithms for operating on red–black trees if the leaves really are explicit nodes. To save execution time, sometimes a pointer to a single <A href="/wiki/Sentinel_node" title="Sentinel node">sentinel node</A> (instead of a null pointer) performs the role of all leaf nodes; all references from <A href="/wiki/Tree_(data_structure)#Internal_nodes" title="Tree (data structure)">internal nodes</A> to leaf nodes then point to the sentinel node.</P>
<P>Red–black trees, like all <A href="/wiki/Binary_search_tree" title="Binary search tree">binary search trees</A>, allow efficient <A href="/wiki/In-order_traversal" class="mw-redirect" title="In-order traversal">in-order traversal</A> (that is: in the order Left–Root–Right) of their elements. The search-time results from the traversal from root to leaf, and therefore a balanced tree of <I>n</I> nodes, having the least possible tree height, results in <SPAN class="texhtml">O(log <I>n</I>)</SPAN> search time.</P>
<H2><SPAN class="mw-headline" id="Properties">Properties</SPAN><SPAN class="mw-editsection"><SPAN class="mw-editsection-bracket">[</SPAN><A href="/w/index.php?title=Red%E2%80%93black_tree&action=edit&section=3" title="Edit section: Properties">edit</A><SPAN class="mw-editsection-bracket">]</SPAN></SPAN></H2>
<DIV class="thumb tright">
<DIV class="thumbinner" style="width:502px;"><A href="/wiki/File:Red-black_tree_example.svg" class="image"><IMG alt="Diagram of binary tree. The black root node has two red children and four black grandchildren. The child nodes of the grandchildren are black nil pointers or red nodes with black nil pointers." src="//upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/500px-Red-black_tree_example.svg.png" width="500" height="241" class="thumbimage" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/750px-Red-black_tree_example.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/1000px-Red-black_tree_example.svg.png 2x" data-file-width="1350" data-file-height="650" /></A>
<DIV class="thumbcaption">
<DIV class="magnify"><A href="/wiki/File:Red-black_tree_example.svg" class="internal" title="Enlarge"></A></DIV>
An example of a red–black tree</DIV>
</DIV>
</DIV>
<P>In addition to the requirements imposed on a <A href="/wiki/Binary_search_tree" title="Binary search tree">binary search tree</A> the following must be satisfied by a <SPAN class="nowrap">red–black tree:<SUP id="cite_ref-16" class="reference"><A href="#cite_note-16">[16]</A></SUP></SPAN></P>
<OL>
<LI>Each node is either red or black.</LI>
<LI>The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis.</LI>
<LI>All leaves (NIL) are black.</LI>
<LI>If a node is red, then both its children are black.</LI>
<LI>Every <A href="/wiki/Path_(graph_theory)" title="Path (graph theory)">path</A> from a given node to any of its descendant NIL nodes contains the same number of black nodes. Some definitions: the number of black nodes from the root to a node is the node's <B>black depth</B>; the uniform number of black nodes in all paths from root to the leaves is called the <B>black-height</B> of the red–black tree.<SUP id="cite_ref-17" class="reference"><A href="#cite_note-17">[17]</A></SUP></LI>
</OL>
<P>These constraints enforce a critical property of red–black trees: <I>the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf</I>. The result is that the tree is roughly height-balanced. Since operations such as inserting, deleting, and finding values require worst-case time proportional to the height of the tree, this theoretical upper bound on the height allows red–black trees to be efficient in the worst case, unlike ordinary <A href="/wiki/Binary_search_tree" title="Binary search tree">binary search trees</A>.</P>
<P>To see why this is guaranteed, it suffices to consider the effect of properties 4 and 5 together. For a red–black tree <I>T</I>, let <I>B</I> be the number of black nodes in <I>property 5</I>. Let the shortest possible path from the root of <I>T</I> to any leaf consist of <I>B</I> black nodes. Longer possible paths may be constructed by inserting red nodes. However, property 4 makes it impossible to insert more than one consecutive red node. Therefore, ignoring any black NIL leaves, the longest possible path consists of <I>2*B</I> nodes, alternating black and red (this is the worst case). Counting the black NIL leaves, the longest possible path consists of <I>2*B-1</I> nodes.</P>
<P><I>The shortest possible path has all black nodes, and the longest possible path alternates between red and black nodes</I>. Since all maximal paths have the same number of black nodes, by property 5, this shows that <I>no path is more than twice as long as any other path</I>.</P>
<H2><SPAN class="mw-headline" id="Analogy_to_B-trees_of_order_4">Analogy to B-trees of order 4</SPAN><SPAN class="mw-editsection"><SPAN class="mw-editsection-bracket">[</SPAN><A href="/w/index.php?title=Red%E2%80%93black_tree&action=edit&section=4" title="Edit section: Analogy to B-trees of order 4">edit</A><SPAN class="mw-editsection-bracket">]</SPAN></SPAN></H2>
<DIV class="thumb tright">
<DIV class="thumbinner" style="width:502px;"><A href="/wiki/File:Red-black_tree_example_(B-tree_analogy).svg" class="image"><IMG alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Red-black_tree_example_%28B-tree_analogy%29.svg/500px-Red-black_tree_example_%28B-tree_analogy%29.svg.png" width="500" height="179" class="thumbimage" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Red-black_tree_example_%28B-tree_analogy%29.svg/750px-Red-black_tree_example_%28B-tree_analogy%29.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/72/Red-black_tree_example_%28B-tree_analogy%29.svg/1000px-Red-black_tree_example_%28B-tree_analogy%29.svg.png 2x" data-file-width="702" data-file-height="251" /></A>
<DIV class="thumbcaption">
<DIV class="magnify"><A href="/wiki/File:Red-black_tree_example_(B-tree_analogy).svg" class="internal" title="Enlarge"></A></DIV>
The same red–black tree as in the example above, seen as a B-tree.</DIV>
</DIV>
</DIV>
<P>A red–black tree is similar in structure to a <A href="/wiki/B-tree" title="B-tree">B-tree</A> of order<SUP id="cite_ref-18" class="reference"><A href="#cite_note-18">[note 1]</A></SUP> 4, where each node can contain between 1 and 3 values and (accordingly) between 2 and 4 child pointers. In such a B-tree, each node will contain only one value matching the value in a black node of the red–black tree, with an optional value before and/or after it in the same node, both matching an equivalent red node of the red–black tree.</P>
<P>One way to see this equivalence is to "move up" the red nodes in a graphical representation of the red–black tree, so that they align horizontally with their parent black node, by creating together a horizontal cluster. In the B-tree, or in the modified graphical representation of the red–black tree, all leaf nodes are at the same depth.</P>
<P>The red–black tree is then structurally equivalent to a B-tree of order 4, with a minimum fill factor of 33% of values per cluster with a maximum capacity of 3 values.</P>
<P>This B-tree type is still more general than a red–black tree though, as it allows ambiguity in a red–black tree conversion—multiple red–black trees can be produced from an equivalent B-tree of order 4. If a B-tree cluster contains only 1 value, it is the minimum, black, and has two child pointers. If a cluster contains 3 values, then the central value will be black and each value stored on its sides will be red. If the cluster contains two values, however, either one can become the black node in the red–black tree (and the other one will be red).</P>
<P>So the order-4 B-tree does not maintain which of the values contained in each cluster is the root black tree for the whole cluster and the parent of the other values in the same cluster. Despite this, the operations on red–black trees are more economical in time because you don't have to maintain the vector of values.<SUP id="cite_ref-19" class="reference"><A href="#cite_note-19">[18]</A></SUP> It may be costly if values are stored directly in each node rather than being stored by reference. B-tree nodes, however, are more economical in space because you don't need to store the color attribute for each node. Instead, you have to know which slot in the cluster vector is used. If values are stored by reference, e.g. objects, null references can be used and so the cluster can be represented by a vector containing 3 slots for value pointers plus 4 slots for child references in the tree. In that case, the B-tree can be more compact in memory, improving data locality.</P>
<P>The same analogy can be made with B-trees with larger orders that can be structurally equivalent to a colored binary tree: you just need more colors. Suppose that you add blue, then the blue–red–black tree defined like red–black trees but with the additional constraint that no two successive nodes in the hierarchy will be blue and all blue nodes will be children of a red node, then it becomes equivalent to a B-tree whose clusters will have at most 7 values in the following colors: blue, red, blue, black, blue, red, blue (For each cluster, there will be at most 1 black node, 2 red nodes, and 4 blue nodes).</P>
<P>For moderate volumes of values, insertions and deletions in a colored binary tree are faster compared to B-trees because colored trees don't attempt to maximize the fill factor of each horizontal cluster of nodes (only the minimum fill factor is guaranteed in colored binary trees, limiting the number of splits or junctions of clusters). B-trees will be faster for performing rotations (because rotations will frequently occur within the same cluster rather than with multiple separate nodes in a colored binary tree). For storing large volumes, however, B-trees will be much faster as they will be more compact by grouping several children in the same cluster where they can be accessed locally.</P>
<P>All optimizations possible in B-trees to increase the average fill factors of clusters are possible in the equivalent multicolored binary tree. Notably, maximizing the average fill factor in a structurally equivalent B-tree is the same as reducing the total height of the multicolored tree, by increasing the number of non-black nodes. The worst case occurs when all nodes in a colored binary tree are black, the best case occurs when only a third of them are black (and the other two thirds are red nodes).</P>
<DIV style="color: #000000; background: none; overflow: hidden; page-break-after: avoid; font-size: 1.17em; font-weight: bold; margin-top: 0.3em; margin-bottom: 0; line-height: 1.6; padding-top: 0.5em; padding-bottom: 0;">Notes</DIV>
<DIV class="reflist columns references-column-width" style="-moz-column-width: close; -webkit-column-width: close; column-width: close; list-style-type: decimal;">
<OL class="references">
<LI id="cite_note-18"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-18"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text">Using Knuth's definition of order: the maximum number of children</SPAN></LI>
</OL>
</DIV>
<H2><SPAN class="mw-headline" id="Applications_and_related_data_structures">Applications and related data structures</SPAN><SPAN class="mw-editsection"><SPAN class="mw-editsection-bracket">[</SPAN><A href="/w/index.php?title=Red%E2%80%93black_tree&action=edit&section=5" title="Edit section: Applications and related data structures">edit</A><SPAN class="mw-editsection-bracket">]</SPAN></SPAN></H2>
<P>Red–black trees offer worst-case guarantees for insertion time, deletion time, and search time. Not only does this make them valuable in time-sensitive applications such as <A href="/wiki/Real-time_computing" title="Real-time computing">real-time applications</A>, but it makes them valuable building blocks in other data structures which provide worst-case guarantees; for example, many data structures used in <A href="/wiki/Computational_geometry" title="Computational geometry">computational geometry</A> can be based on red–black trees, and the <A href="/wiki/Completely_Fair_Scheduler" title="Completely Fair Scheduler">Completely Fair Scheduler</A> used in current <A href="/wiki/Linux" title="Linux">Linux</A> kernels uses red–black trees.</P>
<P>The <A href="/wiki/AVL_tree" title="AVL tree">AVL tree</A> is another structure supporting <SPAN class="texhtml">O(log <I>n</I>)</SPAN> search, insertion, and removal. AVL trees can be colored red-black, thus are a subset of RB trees. Worst-case height is 0.720 times the worst-case height of RB trees, so AVL trees are more rigidly balanced. The performance measurements of Ben Pfaff with realistic test cases in 79 runs find AVL to RB ratios between 0.677 and 1.077, median at 0.947, and geometric mean 0.910.<SUP id="cite_ref-20" class="reference"><A href="#cite_note-20">[19]</A></SUP> Kind of in between are the <A href="/wiki/WAVL_tree" title="WAVL tree">WAVL trees</A>.</P>
<P>Red–black trees are also particularly valuable in <A href="/wiki/Functional_programming" title="Functional programming">functional programming</A>, where they are one of the most common <A href="/wiki/Persistent_data_structure" title="Persistent data structure">persistent data structures</A>, used to construct <A href="/wiki/Associative_array" title="Associative array">associative arrays</A> and <A href="/wiki/Set_(computer_science)" class="mw-redirect" title="Set (computer science)">sets</A> which can retain previous versions after mutations. The persistent version of red–black trees requires <SPAN class="texhtml">O(log <I>n</I>)</SPAN> space for each insertion or deletion, in addition to time.</P>
<P>For every <A href="/wiki/2-4_tree" class="mw-redirect" title="2-4 tree">2-4 tree</A>, there are corresponding red–black trees with data elements in the same order. The insertion and deletion operations on 2-4 trees are also equivalent to color-flipping and rotations in red–black trees. This makes 2-4 trees an important tool for understanding the logic behind red–black trees, and this is why many introductory algorithm texts introduce 2-4 trees just before red–black trees, even though 2-4 trees are not often used in practice.</P>
<P>In 2008, <A href="/wiki/Robert_Sedgewick_(computer_scientist)" title="Robert Sedgewick (computer scientist)">Sedgewick</A> introduced a simpler version of the red–black tree called the <A href="/wiki/Left-leaning_red%E2%80%93black_tree" title="Left-leaning red–black tree">left-leaning red–black tree</A><SUP id="cite_ref-cs.princeton.edu_21-0" class="reference"><A href="#cite_note-cs.princeton.edu-21">[20]</A></SUP> by eliminating a previously unspecified degree of freedom in the implementation. The LLRB maintains an additional invariant that all red links must lean left except during inserts and deletes. Red–black trees can be made isometric to either <A href="/wiki/2-3_tree" class="mw-redirect" title="2-3 tree">2-3 trees</A>,<SUP id="cite_ref-22" class="reference"><A href="#cite_note-22">[21]</A></SUP> or 2-4 trees,<SUP id="cite_ref-cs.princeton.edu_21-1" class="reference"><A href="#cite_note-cs.princeton.edu-21">[20]</A></SUP> for any sequence of operations. The 2-4 tree isometry was described in 1978 by Sedgewick.<SUP class="noprint Inline-Template" style="white-space:nowrap;">[<I><A href="/wiki/Wikipedia:MOSQUOTE" class="mw-redirect" title="Wikipedia:MOSQUOTE"><SPAN title="The text near this tag needs citation. (January 2013)">this quote needs a citation</SPAN></A></I>]</SUP> With 2-4 trees, the isometry is resolved by a "color flip," corresponding to a split, in which the red color of two children nodes leaves the children and moves to the parent node.</P>
<P>The original description of the <A href="/wiki/Tango_tree" title="Tango tree">tango tree</A>, a type of tree optimized for fast searches, specifically uses red–black trees as part of its data structure.<SUP id="cite_ref-DHIP_23-0" class="reference"><A href="#cite_note-DHIP-23">[22]</A></SUP></P>
<P>In the version 8 of Java, the Collection <A href="/wiki/Hashtable" class="mw-redirect" title="Hashtable">HashMap</A> has been modified such that instead of using a <A href="/wiki/LinkedList" class="mw-redirect" title="LinkedList">LinkedList</A> to store different elements with <A href="/wiki/Hash_function#Uniformity" title="Hash function">colliding</A> <A href="/wiki/Hashcode" class="mw-redirect" title="Hashcode">hashcodes</A>, a Red-Black tree is used. This results in the improvement of time complexity of searching such an element from O(n) to O(log n).<SUP id="cite_ref-24" class="reference"><A href="#cite_note-24">[23]</A></SUP></P>
<H2><SPAN class="mw-headline" id="Operations">Operations</SPAN><SPAN class="mw-editsection"><SPAN class="mw-editsection-bracket">[</SPAN><A href="/w/index.php?title=Red%E2%80%93black_tree&action=edit&section=6" title="Edit section: Operations">edit</A><SPAN class="mw-editsection-bracket">]</SPAN></SPAN></H2>
<P>Read-only operations on a red–black tree require no modification from those used for <A href="/wiki/Binary_search_tree" title="Binary search tree">binary search trees</A>, because every red–black tree is a special case of a simple binary search tree. However, the immediate result of an insertion or removal may violate the properties of a red–black tree. Restoring the red–black properties requires a small number (<A href="/wiki/Big-O_notation" class="mw-redirect" title="Big-O notation"><SPAN class="texhtml">O(log <I>n</I>)</SPAN></A> or <A href="/wiki/Amortized_analysis" title="Amortized analysis">amortized <SPAN class="texhtml">O(1)</SPAN></A>) of color changes (which are very quick in practice) and no more than three <A href="/wiki/Tree_rotation" title="Tree rotation">tree rotations</A> (two for insertion). Although insert and delete operations are complicated, their times remain <SPAN class="texhtml">O(log <I>n</I>)</SPAN>.</P>
<P>If the example implementation below is not suitable, there are a couple other implementations with explanations found in Ben Pfaff's annotated C library <A rel="nofollow" class="external text" href="http://adtinfo.org/">GNU libavl</A> (currently v2.0.2) and Eternally Confuzzled's <A rel="nofollow" class="external text" href="http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx">tutorial on red-black trees</A>.</P>
<P>The details of the insert and removal operations will be demonstrated with example <A href="/wiki/C_(programming_language)" title="C (programming language)">C</A> code. The example code may call upon the helper functions below to find the parent, sibling, uncle and grandparent nodes and to rotate a node left or right:</P>
<DIV class="mw-highlight mw-content-ltr" dir="ltr">
<PRE><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="nf">parent</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="k">return</SPAN> <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN><SPAN class="p">;</SPAN>
<SPAN class="p">}</SPAN>

<SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="nf">grandparent</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">p</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">parent</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>
 <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">p</SPAN> <SPAN class="o">==</SPAN> <SPAN class="nb">NULL</SPAN><SPAN class="p">)</SPAN>
  <SPAN class="k">return</SPAN> <SPAN class="nb">NULL</SPAN><SPAN class="p">;</SPAN> <SPAN class="c1">// No parent means no grandparent</SPAN>
 <SPAN class="k">return</SPAN> <SPAN class="n">parent</SPAN><SPAN class="p">(</SPAN><SPAN class="n">p</SPAN><SPAN class="p">);</SPAN>
<SPAN class="p">}</SPAN>

<SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="nf">sibling</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">p</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">parent</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>
 <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">p</SPAN> <SPAN class="o">==</SPAN> <SPAN class="nb">NULL</SPAN><SPAN class="p">)</SPAN>
  <SPAN class="k">return</SPAN> <SPAN class="nb">NULL</SPAN><SPAN class="p">;</SPAN> <SPAN class="c1">// No parent means no sibling</SPAN>
 <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">n</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">p</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN><SPAN class="p">)</SPAN>
  <SPAN class="k">return</SPAN> <SPAN class="n">p</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="k">else</SPAN>
  <SPAN class="k">return</SPAN> <SPAN class="n">p</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN><SPAN class="p">;</SPAN>
<SPAN class="p">}</SPAN>

<SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="nf">uncle</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">p</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">parent</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>
 <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">p</SPAN> <SPAN class="o">==</SPAN> <SPAN class="nb">NULL</SPAN><SPAN class="p">)</SPAN>
  <SPAN class="k">return</SPAN> <SPAN class="nb">NULL</SPAN><SPAN class="p">;</SPAN> <SPAN class="c1">// No parent means no uncle</SPAN>
 <SPAN class="k">return</SPAN> <SPAN class="n">sibling</SPAN><SPAN class="p">(</SPAN><SPAN class="n">p</SPAN><SPAN class="p">);</SPAN>
<SPAN class="p">}</SPAN>

<SPAN class="kt">void</SPAN> <SPAN class="nf">rotate_left</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">nnew</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="n">assert</SPAN><SPAN class="p">(</SPAN><SPAN class="n">nnew</SPAN> <SPAN class="o">!=</SPAN> <SPAN class="n">LEAF</SPAN><SPAN class="p">);</SPAN> <SPAN class="c1">// since the leaves of a red-black tree are empty, they cannot become internal nodes</SPAN>
 <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">nnew</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="n">nnew</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">n</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="n">nnew</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">nnew</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="c1">// (the other related parent and child links would also have to be updated)</SPAN>
<SPAN class="p">}</SPAN>

<SPAN class="kt">void</SPAN> <SPAN class="nf">rotate_right</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">nnew</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="n">assert</SPAN><SPAN class="p">(</SPAN><SPAN class="n">nnew</SPAN> <SPAN class="o">!=</SPAN> <SPAN class="n">LEAF</SPAN><SPAN class="p">);</SPAN> <SPAN class="c1">// since the leaves of a red-black tree are empty, they cannot become internal nodes</SPAN>
 <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">nnew</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="n">nnew</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">n</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="n">nnew</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">nnew</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="c1">// (the other related parent and child links would also have to be updated)</SPAN>
<SPAN class="p">}</SPAN>
</PRE></DIV>
<DL>
<DT>Diagram Notes</DT>
</DL>
<OL>
<LI>The label <B>N</B> will be used to denote the current node in each case. At the beginning, this is the insertion node or the replacement node and a leaf, but the entire procedure may also be applied recursively to other nodes (see case 3).</LI>
<LI><B>P</B> will denote <B>N</B>'s parent node, <B>G</B> will denote <B>N</B>'s grandparent, <B>S</B> will denote <B>N</B>'s sibling, and <B>U</B> will denote <B>N</B>'s uncle (i.e., the sibling of a node's parent, as in human family trees).</LI>
<LI>In between some cases, the roles and labels of the nodes are shifted, but within each case, every label continues to represent the same node throughout.</LI>
<LI>In the diagrams a blue border rings the current node <B>N</B> in the left (current) half and rings the node that will become <B>N</B> in the right (target) half. In the next step, the other nodes will be newly assigned relative to it.</LI>
<LI>Red or black shown in the diagram is either assumed in its case or implied by those assumptions. White represents either red or black, but is the same in both halves of the diagram.</LI>
<LI>A numbered triangle represents a subtree of unspecified depth. A black circle atop a triangle means that black-height of that subtree is greater by one compared to a subtree without this circle.</LI>
</OL>
<H3><SPAN class="mw-headline" id="Insertion">Insertion</SPAN><SPAN class="mw-editsection"><SPAN class="mw-editsection-bracket">[</SPAN><A href="/w/index.php?title=Red%E2%80%93black_tree&action=edit&section=7" title="Edit section: Insertion">edit</A><SPAN class="mw-editsection-bracket">]</SPAN></SPAN></H3>
<P>Insertion begins by adding the node in a very similar manner as a standard <A href="/wiki/Binary_search_tree#Insertion" title="Binary search tree">binary search tree insertion</A> and by coloring it red. The big difference is that in the binary search tree a new node is added as a leaf, whereas leaves contain no information in the red–black tree, so instead the new node replaces an existing leaf and then has two black leaves of its own added.</P>
<DIV class="mw-highlight mw-content-ltr" dir="ltr">
<PRE><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="nf">insert</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">root</SPAN><SPAN class="p">,</SPAN> <SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="c1">// insert new node into the current tree</SPAN>
 <SPAN class="n">insert_recurse</SPAN><SPAN class="p">(</SPAN><SPAN class="n">root</SPAN><SPAN class="p">,</SPAN> <SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>

 <SPAN class="c1">// repair the tree in case any of the red-black properties have been violated</SPAN>
 <SPAN class="n">insert_repair_tree</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>

 <SPAN class="c1">// find the new root to return</SPAN>
 <SPAN class="n">root</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">n</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="k">while</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">parent</SPAN><SPAN class="p">(</SPAN><SPAN class="n">root</SPAN><SPAN class="p">)</SPAN> <SPAN class="o">!=</SPAN> <SPAN class="nb">NULL</SPAN><SPAN class="p">)</SPAN>
  <SPAN class="n">root</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">parent</SPAN><SPAN class="p">(</SPAN><SPAN class="n">root</SPAN><SPAN class="p">);</SPAN>
 <SPAN class="k">return</SPAN> <SPAN class="n">root</SPAN><SPAN class="p">;</SPAN>
<SPAN class="p">}</SPAN>

<SPAN class="kt">void</SPAN> <SPAN class="nf">insert_recurse</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">root</SPAN><SPAN class="p">,</SPAN> <SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">){</SPAN>
 <SPAN class="c1">// recursively descend the tree until a leaf is found</SPAN>
 <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">root</SPAN> <SPAN class="o">!=</SPAN> <SPAN class="nb">NULL</SPAN> <SPAN class="o">&&</SPAN> <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">key</SPAN> <SPAN class="o"><</SPAN> <SPAN class="n">root</SPAN><SPAN class="o">-></SPAN><SPAN class="n">key</SPAN><SPAN class="p">)</SPAN> <SPAN class="p">{</SPAN>
  <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">root</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN> <SPAN class="o">!=</SPAN> <SPAN class="n">LEAF</SPAN><SPAN class="p">){</SPAN>
   <SPAN class="n">insert_recurse</SPAN><SPAN class="p">(</SPAN><SPAN class="n">root</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN><SPAN class="p">,</SPAN> <SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>
   <SPAN class="k">return</SPAN><SPAN class="p">;</SPAN>
  <SPAN class="p">}</SPAN>
  <SPAN class="k">else</SPAN>
   <SPAN class="n">root</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">n</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="p">}</SPAN> <SPAN class="k">else</SPAN> <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">root</SPAN> <SPAN class="o">!=</SPAN> <SPAN class="nb">NULL</SPAN><SPAN class="p">)</SPAN> <SPAN class="p">{</SPAN>
  <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">root</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN> <SPAN class="o">!=</SPAN> <SPAN class="n">LEAF</SPAN><SPAN class="p">){</SPAN>
   <SPAN class="n">insert_recurse</SPAN><SPAN class="p">(</SPAN><SPAN class="n">root</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN><SPAN class="p">,</SPAN> <SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>
   <SPAN class="k">return</SPAN><SPAN class="p">;</SPAN>
  <SPAN class="p">}</SPAN>
  <SPAN class="k">else</SPAN>
   <SPAN class="n">root</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">n</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="p">}</SPAN>

 <SPAN class="c1">// insert new node n</SPAN>
 <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">root</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">LEAF</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">LEAF</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">RED</SPAN><SPAN class="p">;</SPAN>
<SPAN class="p">}</SPAN>
</PRE></DIV>
<P>What happens next depends on the color of other nearby nodes. There are several cases of red–black tree insertion to handle:</P>
<OL>
<LI><B>N</B> is the root node, i.e., first node of red–black tree</LI>
<LI><B>N</B>'s parent (<B>P</B>) is black</LI>
<LI><B>P</B> is red (so it can't be the root of the tree) and <B>N</B>'s uncle (<B>U</B>) is red</LI>
<LI><B>P</B> is red and <B>U</B> is black</LI>
</OL>
<DIV class="mw-highlight mw-content-ltr" dir="ltr">
<PRE><SPAN class="kt">void</SPAN> <SPAN class="nf">insert_repair_tree</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">parent</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN> <SPAN class="o">==</SPAN> <SPAN class="nb">NULL</SPAN><SPAN class="p">)</SPAN> <SPAN class="p">{</SPAN>
  <SPAN class="n">insert_case1</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>
 <SPAN class="p">}</SPAN> <SPAN class="k">else</SPAN> <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">parent</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">)</SPAN> <SPAN class="p">{</SPAN>
  <SPAN class="n">insert_case2</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>
 <SPAN class="p">}</SPAN> <SPAN class="k">else</SPAN> <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">uncle</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">RED</SPAN><SPAN class="p">)</SPAN> <SPAN class="p">{</SPAN>
  <SPAN class="n">insert_case3</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>
 <SPAN class="p">}</SPAN> <SPAN class="k">else</SPAN> <SPAN class="p">{</SPAN>
  <SPAN class="n">insert_case4</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>
 <SPAN class="p">}</SPAN>
<SPAN class="p">}</SPAN>
</PRE></DIV>
<P>Note that:</P>
<UL>
<LI>Property 1 (every node is either red or black) and Property 3 (all leaves are black) always holds.</LI>
<LI>Property 2 (the root is black) is checked and corrected with case 1.</LI>
<LI>Property 4 (red nodes have only black children) is threatened only by adding a red node, repainting a node from black to red, or a <A href="/wiki/Tree_rotation" title="Tree rotation">rotation</A>.</LI>
<LI>Property 5 (all paths from any given node to its leaves have the same number of black nodes) is threatened only by adding a black node, repainting a node, or a <A href="/wiki/Tree_rotation" title="Tree rotation">rotation</A>.</LI>
</UL>
<P><B>Case 1:</B> The current node <B>N</B> is at the root of the tree. In this case, it is repainted black to satisfy property 2 (the root is black). Since this adds one black node to every path at once, property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) is not violated.</P>
<DIV class="mw-highlight mw-content-ltr" dir="ltr">
<PRE><SPAN class="kt">void</SPAN> <SPAN class="nf">insert_case1</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">parent</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN> <SPAN class="o">==</SPAN> <SPAN class="nb">NULL</SPAN><SPAN class="p">)</SPAN>
  <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">;</SPAN>
<SPAN class="p">}</SPAN>
</PRE></DIV>
<P><B>Case 2:</B> The current node's parent <B>P</B> is black, so property 4 (both children of every red node are black) is not invalidated. In this case, the tree is still valid. Property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) is not threatened, because the current node <B>N</B> has two black leaf children, but because <B>N</B> is red, the paths through each of its children have the same number of black nodes as the path through the leaf it replaced, which was black, and so this property remains satisfied.</P>
<DIV class="mw-highlight mw-content-ltr" dir="ltr">
<PRE><SPAN class="kt">void</SPAN> <SPAN class="nf">insert_case2</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
  <SPAN class="k">return</SPAN><SPAN class="p">;</SPAN> <SPAN class="cm">/* Do nothing since tree is still valid */</SPAN>
<SPAN class="p">}</SPAN>
</PRE></DIV>
<DL>
<DD><I>Note:</I> In the following cases it can be assumed that <B>N</B> has a grandparent node <B>G</B>, because its parent <B>P</B> is red, and if it were the root, it would be black. Thus, <B>N</B> also has an uncle node <B>U</B>, although it may be a leaf in case 4.</DD>
</DL>
<DL>
<DD><I>Note:</I> In the remaining cases, it is shown in the diagram that the parent node <B>P</B> is the left child of its parent even though it is possible for <B>P</B> to be on either side. The code samples already cover both possibilities.</DD>
</DL>
<TABLE>
<TBODY><TR>
<TD>
<DIV class="floatright"><A href="/wiki/File:Red-black_tree_insert_case_3.svg" class="image" title="Diagram of case 3"><IMG alt="Diagram of case 3" src="//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Red-black_tree_insert_case_3.svg/400px-Red-black_tree_insert_case_3.svg.png" width="400" height="117" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Red-black_tree_insert_case_3.svg/600px-Red-black_tree_insert_case_3.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Red-black_tree_insert_case_3.svg/800px-Red-black_tree_insert_case_3.svg.png 2x" data-file-width="813" data-file-height="238" /></A></DIV>
<P><B>Case 3:</B> If both the parent <B>P</B> and the uncle <B>U</B> are red, then both of them can be repainted black and the grandparent <B>G</B> becomes red to maintain property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes). Since any path through the parent or uncle must pass through the grandparent, the number of black nodes on these paths has not changed. However, the grandparent <B>G</B> may now violate Property 2 (The root is black) if it is the root or Property 4 (Both children of every red node are black) if it has a red parent. To fix this, the tree's red-black repair procedure is rerun on <B>G</B>.</P>
<P>Note that this is a tail-recursive call, so it could be rewritten as a loop. Since this is the only loop, and any rotations occur after this loop, this proves that a constant number of rotations occur.</P>
</TD>
</TR>
</TBODY></TABLE>
<DIV class="mw-highlight mw-content-ltr" dir="ltr">
<PRE><SPAN class="kt">void</SPAN> <SPAN class="nf">insert_case3</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="n">parent</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="n">uncle</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="n">grandparent</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">RED</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="n">insert_repair_tree</SPAN><SPAN class="p">(</SPAN><SPAN class="n">grandparent</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">));</SPAN>
<SPAN class="p">}</SPAN>
</PRE></DIV>
<TABLE>
<TBODY><TR>
<TD>
<DIV class="floatright"><A href="/wiki/File:Red-black_tree_insert_case_4.svg" class="image" title="Diagram of case 4"><IMG alt="Diagram of case 4" src="//upload.wikimedia.org/wikipedia/commons/thumb/8/89/Red-black_tree_insert_case_4.svg/400px-Red-black_tree_insert_case_4.svg.png" width="400" height="127" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/8/89/Red-black_tree_insert_case_4.svg/600px-Red-black_tree_insert_case_4.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/8/89/Red-black_tree_insert_case_4.svg/800px-Red-black_tree_insert_case_4.svg.png 2x" data-file-width="774" data-file-height="245" /></A></DIV>
<P><B>Case 4, step 1:</B> The parent <B>P</B> is red but the uncle <B>U</B> is black. The ultimate goal will be to rotate the parent node into the grandparent position, but this will not work if the current node is on the "inside" of the subtree under <B>G</B> (i.e., if <B>N</B> is the left child of the right child of the grandparent or the right child of the left child of the grandparent). In this case, a <A href="/wiki/Tree_rotation" title="Tree rotation">left rotation</A> on <B>P</B> that switches the roles of the current node <B>N</B> and its parent <B>P</B> can be performed. The rotation causes some paths (those in the sub-tree labelled "1") to pass through the node <B>N</B> where they did not before. It also causes some paths (those in the sub-tree labelled "3") not to pass through the node <B>P</B> where they did before. However, both of these nodes are red, so property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) is not violated by the rotation. After this step has been completed, property 4 (both children of every red node are black) is still violated, but now we can resolve this by continuing to step 2.</P>
</TD>
</TR>
</TBODY></TABLE>
<DIV class="mw-highlight mw-content-ltr" dir="ltr">
<PRE><SPAN class="kt">void</SPAN> <SPAN class="nf">insert_case4</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">p</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">parent</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>
 <SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">g</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">grandparent</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>

 <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">n</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">g</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN><SPAN class="p">)</SPAN> <SPAN class="p">{</SPAN>
  <SPAN class="n">rotate_left</SPAN><SPAN class="p">(</SPAN><SPAN class="n">p</SPAN><SPAN class="p">);</SPAN>
  <SPAN class="n">n</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="p">}</SPAN> <SPAN class="k">else</SPAN> <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">n</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">g</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN><SPAN class="p">)</SPAN> <SPAN class="p">{</SPAN>
  <SPAN class="n">rotate_right</SPAN><SPAN class="p">(</SPAN><SPAN class="n">p</SPAN><SPAN class="p">);</SPAN>
  <SPAN class="n">n</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="p">}</SPAN>

 <SPAN class="n">insert_case4step2</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>
<SPAN class="p">}</SPAN>
</PRE></DIV>
<TABLE>
<TBODY><TR>
<TD>
<DIV class="floatright"><A href="/wiki/File:Red-black_tree_insert_case_5.svg" class="image" title="Diagram of case 5"><IMG alt="Diagram of case 5" src="//upload.wikimedia.org/wikipedia/commons/thumb/d/dc/Red-black_tree_insert_case_5.svg/400px-Red-black_tree_insert_case_5.svg.png" width="400" height="117" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/d/dc/Red-black_tree_insert_case_5.svg/600px-Red-black_tree_insert_case_5.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/d/dc/Red-black_tree_insert_case_5.svg/800px-Red-black_tree_insert_case_5.svg.png 2x" data-file-width="841" data-file-height="245" /></A></DIV>
<P><B>Case 4, step 2:</B> The current node <B>N</B> is now certain to be on the "outside" of the subtree under <B>G</B> (left of left child or right of right child). In this case, a <A href="/wiki/Tree_rotation" title="Tree rotation">right rotation</A> on <B>G</B> is performed; the result is a tree where the former parent <B>P</B> is now the parent of both the current node <B>N</B> and the former grandparent <B>G</B>. <B>G</B> is known to be black, since its former child <B>P</B> could not have been red without violating property 4. Once the colors of <B>P</B> and <B>G</B> are switched, the resulting tree satisfies property 4 (both children of every red node are black). Property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) also remains satisfied, since all paths that went through any of these three nodes went through <B>G</B> before, and now they all go through <B>P</B>.</P>
</TD>
</TR>
</TBODY></TABLE>
<DIV class="mw-highlight mw-content-ltr" dir="ltr">
<PRE><SPAN class="kt">void</SPAN> <SPAN class="nf">insert_case4step2</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">p</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">parent</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>
 <SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">g</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">grandparent</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>

 <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">n</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">p</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN><SPAN class="p">)</SPAN>
  <SPAN class="n">rotate_right</SPAN><SPAN class="p">(</SPAN><SPAN class="n">g</SPAN><SPAN class="p">);</SPAN>
 <SPAN class="k">else</SPAN>
  <SPAN class="n">rotate_left</SPAN><SPAN class="p">(</SPAN><SPAN class="n">g</SPAN><SPAN class="p">);</SPAN>
 <SPAN class="n">p</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="n">g</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">RED</SPAN><SPAN class="p">;</SPAN>
<SPAN class="p">}</SPAN>
</PRE></DIV>
<P>Note that inserting is actually <A href="/wiki/In-place_algorithm" title="In-place algorithm">in-place</A>, since all the calls above use <A href="/wiki/Tail_recursion" class="mw-redirect" title="Tail recursion">tail recursion</A>.</P>
<P>In the algorithm above, all cases are called only once, except in Case 3 where it can recurse back to Case 1 with the grandparent node, which is the only case where an iterative implementation will effectively loop. Because the problem of repair in that case is escalated two levels higher each time, it takes maximally <SPAN class="texhtml"><SPAN class="frac nowrap"><SUP>h</SUP>⁄<SUB>2</SUB></SPAN></SPAN> iterations to repair the tree (where <SPAN class="texhtml">h</SPAN> is the height of the tree). Because the probability for escalation decreases exponentially with each iteration the average insertion cost is practically constant.</P>
<H3><SPAN class="mw-headline" id="Removal">Removal</SPAN><SPAN class="mw-editsection"><SPAN class="mw-editsection-bracket">[</SPAN><A href="/w/index.php?title=Red%E2%80%93black_tree&action=edit&section=8" title="Edit section: Removal">edit</A><SPAN class="mw-editsection-bracket">]</SPAN></SPAN></H3>
<P>In a regular binary search tree when deleting a node with two non-leaf children, we find either the maximum element in its left subtree (which is the in-order predecessor) or the minimum element in its right subtree (which is the in-order successor) and move its value into the node being deleted (as shown <A href="/wiki/Binary_search_tree#Deletion" title="Binary search tree">here</A>). We then delete the node we copied the value from, which must have fewer than two non-leaf children. (Non-leaf children, rather than all children, are specified here because unlike normal binary search trees, red–black trees can have leaf nodes anywhere, so that all nodes are either internal nodes with two children or leaf nodes with, by definition, zero children. In effect, internal nodes having two leaf children in a red–black tree are like the leaf nodes in a regular binary search tree.) Because merely copying a value does not violate any red–black properties, this reduces to the problem of deleting a node with at most one non-leaf child. Once we have solved that problem, the solution applies equally to the case where the node we originally want to delete has at most one non-leaf child as to the case just considered where it has two non-leaf children.</P>
<P>Therefore, for the remainder of this discussion we address the deletion of a node with at most one non-leaf child. We use the label <B>M</B> to denote the node to be deleted; <B>C</B> will denote a selected child of <B>M</B>, which we will also call "its child". If <B>M</B> does have a non-leaf child, call that its child, <B>C</B>; otherwise, choose either leaf as its child, <B>C</B>.</P>
<P>If <B>M</B> is a red node, we simply replace it with its child <B>C</B>, which must be black by property 4. (This can only occur when <B>M</B> has two leaf children, because if the red node <B>M</B> had a black non-leaf child on one side but just a leaf child on the other side, then the count of black nodes on both sides would be different, thus the tree would violate property 5.) All paths through the deleted node will simply pass through one fewer red node, and both the deleted node's parent and child must be black, so property 3 (all leaves are black) and property 4 (both children of every red node are black) still hold.</P>
<P>Another simple case is when <B>M</B> is black and <B>C</B> is red. Simply removing a black node could break Properties 4 (“Both children of every red node are black”) and 5 (“All paths from any given node to its leaf nodes contain the same number of black nodes”), but if we repaint <B>C</B> black, both of these properties are preserved.</P>
<P>The complex case is when both <B>M</B> and <B>C</B> are black. (This can only occur when deleting a black node which has two leaf children, because if the black node <B>M</B> had a black non-leaf child on one side but just a leaf child on the other side, then the count of black nodes on both sides would be different, thus the tree would have been an invalid red–black tree by violation of property 5.) We begin by replacing <B>M</B> with its child <B>C</B>. We will <I>relabel</I> this child <B>C</B> (in its new position) <B>N</B>, and its sibling (its new parent's other child) <B>S</B>. (<B>S</B> was previously the sibling of <B>M</B>.) In the diagrams below, we will also use <B>P</B> for <B>N</B>'s new parent (<B>M</B>'s old parent), <B>S<SUB>L</SUB></B> for <B>S</B>'s left child, and <B>S<SUB>R</SUB></B> for <B>S</B>'s right child (<B>S</B> cannot be a leaf because if <B>M</B> and <B>C</B> were black, then <B>P</B>'s one subtree which included <B>M</B> counted two black-height and thus <B>P</B>'s other subtree which includes <B>S</B> must also count two black-height, which cannot be the case if <B>S</B> is a leaf node).</P>
<DL>
<DD><I>Note</I>: In order for the tree to remain well-defined, we need every null leaf to remain a leaf after all transformations (that it will not have any children). If the node we are deleting has a non-leaf (non-null) child <B>N</B>, it is easy to see that the property is satisfied. If, on the other hand, <B>N</B> would be a null leaf, it can be verified from the diagrams (or code) for all the cases that the property is satisfied as well.</DD>
</DL>
<P>We can perform the steps outlined above with the following code, where the function <CODE>replace_node</CODE> substitutes <CODE>child</CODE> into <CODE>n</CODE>'s place in the tree. For convenience, code in this section will assume that null leaves are represented by actual node objects rather than NULL (the code in the <I>Insertion</I> section works with either representation).</P>
<DIV class="mw-highlight mw-content-ltr" dir="ltr">
<PRE><SPAN class="kt">void</SPAN> <SPAN class="nf">delete_one_child</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="cm">/*</SPAN>
<SPAN class="cm">  * Precondition: n has at most one non-leaf child.</SPAN>
<SPAN class="cm">  */</SPAN>
 <SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">child</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">is_leaf</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN><SPAN class="p">)</SPAN> <SPAN class="o">?</SPAN> <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="nl">left</SPAN> <SPAN class="p">:</SPAN> <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN><SPAN class="p">;</SPAN>

 <SPAN class="n">replace_node</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">,</SPAN> <SPAN class="n">child</SPAN><SPAN class="p">);</SPAN>
 <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">)</SPAN> <SPAN class="p">{</SPAN>
  <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">child</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">RED</SPAN><SPAN class="p">)</SPAN>
   <SPAN class="n">child</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">;</SPAN>
  <SPAN class="k">else</SPAN>
   <SPAN class="n">delete_case1</SPAN><SPAN class="p">(</SPAN><SPAN class="n">child</SPAN><SPAN class="p">);</SPAN>
 <SPAN class="p">}</SPAN>
 <SPAN class="n">free</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>
<SPAN class="p">}</SPAN>
</PRE></DIV>
<DL>
<DD><I>Note</I>: If <B>N</B> is a null leaf and we do not want to represent null leaves as actual node objects, we can modify the algorithm by first calling delete_case1() on its parent (the node that we delete, <CODE>n</CODE> in the code above) and deleting it afterwards. We do this if the parent is black (red is trivial), so it behaves in the same way as a null leaf (and is sometimes called a 'phantom' leaf). And we can safely delete it at the end as <CODE>n</CODE> will remain a leaf after all operations, as shown above. In addition, the sibling tests in cases 2 and 3 require updating as it is no longer true that the sibling will have children represented as objects.</DD>
</DL>
<P>If both <B>N</B> and its original parent are black, then deleting this original parent causes paths which proceed through <B>N</B> to have one fewer black node than paths that do not. As this violates property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes), the tree must be rebalanced. There are several cases to consider:</P>
<P><B>Case 1:</B> <B>N</B> is the new root. In this case, we are done. We removed one black node from every path, and the new root is black, so the properties are preserved.</P>
<DIV class="mw-highlight mw-content-ltr" dir="ltr">
<PRE><SPAN class="kt">void</SPAN> <SPAN class="nf">delete_case1</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN> <SPAN class="o">!=</SPAN> <SPAN class="nb">NULL</SPAN><SPAN class="p">)</SPAN>
  <SPAN class="n">delete_case2</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>
<SPAN class="p">}</SPAN>
</PRE></DIV>
<DL>
<DD><I>Note</I>: In cases 2, 5, and 6, we assume <B>N</B> is the left child of its parent <B>P</B>. If it is the right child, <I>left</I> and <I>right</I> should be reversed throughout these three cases. Again, the code examples take both cases into account.</DD>
</DL>
<TABLE>
<TBODY><TR>
<TD>
<DIV class="floatright"><A href="/wiki/File:Red-black_tree_delete_case_2_as_svg.svg" class="image" title="Diagram of case 2"><IMG alt="Diagram of case 2" src="//upload.wikimedia.org/wikipedia/commons/thumb/5/5c/Red-black_tree_delete_case_2_as_svg.svg/337px-Red-black_tree_delete_case_2_as_svg.svg.png" width="337" height="128" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/5/5c/Red-black_tree_delete_case_2_as_svg.svg/506px-Red-black_tree_delete_case_2_as_svg.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/5/5c/Red-black_tree_delete_case_2_as_svg.svg/674px-Red-black_tree_delete_case_2_as_svg.svg.png 2x" data-file-width="619" data-file-height="235" /></A></DIV>
<P><B>Case 2:</B> <B>S</B> is red. In this case we reverse the colors of <B>P</B> and <B>S</B>, and then <A href="/wiki/Tree_rotation" title="Tree rotation">rotate</A> left at <B>P</B>, turning <B>S</B> into <B>N</B>'s grandparent. Note that <B>P</B> has to be black as it had a red child. The resulting subtree has a path short one black node so we are not done. Now <B>N</B> has a black sibling and a red parent, so we can proceed to step 4, 5, or 6. (Its new sibling is black because it was once the child of the red <B>S</B>.) In later cases, we will relabel <B>N</B>'s new sibling as <B>S</B>.</P>
</TD>
</TR>
</TBODY></TABLE>
<DIV class="mw-highlight mw-content-ltr" dir="ltr">
<PRE><SPAN class="kt">void</SPAN> <SPAN class="nf">delete_case2</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">s</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">sibling</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>

 <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">RED</SPAN><SPAN class="p">)</SPAN> <SPAN class="p">{</SPAN>
  <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">RED</SPAN><SPAN class="p">;</SPAN>
  <SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">;</SPAN>
  <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">n</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN><SPAN class="p">)</SPAN>
   <SPAN class="n">rotate_left</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN><SPAN class="p">);</SPAN>
  <SPAN class="k">else</SPAN>
   <SPAN class="n">rotate_right</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN><SPAN class="p">);</SPAN>
 <SPAN class="p">}</SPAN>
 <SPAN class="n">delete_case3</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>
<SPAN class="p">}</SPAN>
</PRE></DIV>
<TABLE>
<TBODY><TR>
<TD>
<DIV class="floatleft"><A href="/wiki/File:Red-black_tree_delete_case_3_as_svg.svg" class="image" title="Diagram of case 3"><IMG alt="Diagram of case 3" src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a0/Red-black_tree_delete_case_3_as_svg.svg/337px-Red-black_tree_delete_case_3_as_svg.svg.png" width="337" height="129" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a0/Red-black_tree_delete_case_3_as_svg.svg/506px-Red-black_tree_delete_case_3_as_svg.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a0/Red-black_tree_delete_case_3_as_svg.svg/674px-Red-black_tree_delete_case_3_as_svg.svg.png 2x" data-file-width="623" data-file-height="239" /></A></DIV>
<P><B>Case 3:</B> <B>P</B>, <B>S</B>, and <B>S</B>'s children are black. In this case, we simply repaint <B>S</B> red. The result is that all paths passing through <B>S</B>, which are precisely those paths <I>not</I> passing through <B>N</B>, have one less black node. Because deleting <B>N</B>'s original parent made all paths passing through <B>N</B> have one less black node, this evens things up. However, all paths through <B>P</B> now have one fewer black node than paths that do not pass through <B>P</B>, so property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) is still violated. To correct this, we perform the rebalancing procedure on <B>P</B>, starting at case 1.</P>
</TD>
</TR>
</TBODY></TABLE>
<DIV class="mw-highlight mw-content-ltr" dir="ltr">
<PRE><SPAN class="kt">void</SPAN> <SPAN class="nf">delete_case3</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">s</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">sibling</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>

 <SPAN class="k">if</SPAN> <SPAN class="p">((</SPAN><SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">)</SPAN> <SPAN class="o">&&</SPAN>
     <SPAN class="p">(</SPAN><SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">)</SPAN> <SPAN class="o">&&</SPAN>
     <SPAN class="p">(</SPAN><SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">)</SPAN> <SPAN class="o">&&</SPAN>
     <SPAN class="p">(</SPAN><SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">))</SPAN> <SPAN class="p">{</SPAN>
  <SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">RED</SPAN><SPAN class="p">;</SPAN>
  <SPAN class="n">delete_case1</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN><SPAN class="p">);</SPAN>
 <SPAN class="p">}</SPAN> <SPAN class="k">else</SPAN>
  <SPAN class="n">delete_case4</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>
<SPAN class="p">}</SPAN>
</PRE></DIV>
<TABLE>
<TBODY><TR>
<TD>
<DIV class="floatright"><A href="/wiki/File:Red-black_tree_delete_case_4_as_svg.svg" class="image" title="Diagram of case 4"><IMG alt="Diagram of case 4" src="//upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Red-black_tree_delete_case_4_as_svg.svg/337px-Red-black_tree_delete_case_4_as_svg.svg.png" width="337" height="128" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Red-black_tree_delete_case_4_as_svg.svg/506px-Red-black_tree_delete_case_4_as_svg.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Red-black_tree_delete_case_4_as_svg.svg/674px-Red-black_tree_delete_case_4_as_svg.svg.png 2x" data-file-width="624" data-file-height="237" /></A></DIV>
<P><B>Case 4:</B> <B>S</B> and <B>S</B>'s children are black, but <B>P</B> is red. In this case, we simply exchange the colors of <B>S</B> and <B>P</B>. This does not affect the number of black nodes on paths going through <B>S</B>, but it does add one to the number of black nodes on paths going through <B>N</B>, making up for the deleted black node on those paths.</P>
</TD>
</TR>
</TBODY></TABLE>
<DIV class="mw-highlight mw-content-ltr" dir="ltr">
<PRE><SPAN class="kt">void</SPAN> <SPAN class="nf">delete_case4</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">s</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">sibling</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>

 <SPAN class="k">if</SPAN> <SPAN class="p">((</SPAN><SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">RED</SPAN><SPAN class="p">)</SPAN> <SPAN class="o">&&</SPAN>
     <SPAN class="p">(</SPAN><SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">)</SPAN> <SPAN class="o">&&</SPAN>
     <SPAN class="p">(</SPAN><SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">)</SPAN> <SPAN class="o">&&</SPAN>
     <SPAN class="p">(</SPAN><SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">))</SPAN> <SPAN class="p">{</SPAN>
  <SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">RED</SPAN><SPAN class="p">;</SPAN>
  <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="p">}</SPAN> <SPAN class="k">else</SPAN>
  <SPAN class="n">delete_case5</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>
<SPAN class="p">}</SPAN>
</PRE></DIV>
<TABLE>
<TBODY><TR>
<TD>
<DIV class="floatleft"><A href="/wiki/File:Red-black_tree_delete_case_5_as_svg.svg" class="image" title="Diagram of case 5"><IMG alt="Diagram of case 5" src="//upload.wikimedia.org/wikipedia/commons/thumb/3/36/Red-black_tree_delete_case_5_as_svg.svg/243px-Red-black_tree_delete_case_5_as_svg.svg.png" width="243" height="138" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/36/Red-black_tree_delete_case_5_as_svg.svg/365px-Red-black_tree_delete_case_5_as_svg.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/3/36/Red-black_tree_delete_case_5_as_svg.svg/486px-Red-black_tree_delete_case_5_as_svg.svg.png 2x" data-file-width="453" data-file-height="258" /></A></DIV>
<P><B>Case 5:</B> <B>S</B> is black, <B>S</B>'s left child is red, <B>S</B>'s right child is black, and <B>N</B> is the left child of its parent. In this case we rotate right at <B>S</B>, so that <B>S</B>'s left child becomes <B>S</B>'s parent and <B>N</B>'s new sibling. We then exchange the colors of <B>S</B> and its new parent. All paths still have the same number of black nodes, but now <B>N</B> has a black sibling whose right child is red, so we fall into case 6. Neither <B>N</B> nor its parent are affected by this transformation. (Again, for case 6, we relabel <B>N</B>'s new sibling as <B>S</B>.)</P>
</TD>
</TR>
</TBODY></TABLE>
<DIV class="mw-highlight mw-content-ltr" dir="ltr">
<PRE><SPAN class="kt">void</SPAN> <SPAN class="nf">delete_case5</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">s</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">sibling</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>

 <SPAN class="k">if</SPAN>  <SPAN class="p">(</SPAN><SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">)</SPAN> <SPAN class="p">{</SPAN> <SPAN class="cm">/* this if statement is trivial,</SPAN>
<SPAN class="cm">due to case 2 (even though case 2 changed the sibling to a sibling's child,</SPAN>
<SPAN class="cm">the sibling's child can't be red, since no red parent can have a red child). */</SPAN>
<SPAN class="cm">/* the following statements just force the red to be on the left of the left of the parent,</SPAN>
<SPAN class="cm">   or right of the right, so case six will rotate correctly. */</SPAN>
  <SPAN class="k">if</SPAN> <SPAN class="p">((</SPAN><SPAN class="n">n</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN><SPAN class="p">)</SPAN> <SPAN class="o">&&</SPAN>
      <SPAN class="p">(</SPAN><SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">)</SPAN> <SPAN class="o">&&</SPAN>
      <SPAN class="p">(</SPAN><SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">RED</SPAN><SPAN class="p">))</SPAN> <SPAN class="p">{</SPAN> <SPAN class="cm">/* this last test is trivial too due to cases 2-4. */</SPAN>
   <SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">RED</SPAN><SPAN class="p">;</SPAN>
   <SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">;</SPAN>
   <SPAN class="n">rotate_right</SPAN><SPAN class="p">(</SPAN><SPAN class="n">s</SPAN><SPAN class="p">);</SPAN>
  <SPAN class="p">}</SPAN> <SPAN class="k">else</SPAN> <SPAN class="k">if</SPAN> <SPAN class="p">((</SPAN><SPAN class="n">n</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN><SPAN class="p">)</SPAN> <SPAN class="o">&&</SPAN>
             <SPAN class="p">(</SPAN><SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">)</SPAN> <SPAN class="o">&&</SPAN>
             <SPAN class="p">(</SPAN><SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">RED</SPAN><SPAN class="p">))</SPAN> <SPAN class="p">{</SPAN><SPAN class="cm">/* this last test is trivial too due to cases 2-4. */</SPAN>
   <SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">RED</SPAN><SPAN class="p">;</SPAN>
   <SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">;</SPAN>
   <SPAN class="n">rotate_left</SPAN><SPAN class="p">(</SPAN><SPAN class="n">s</SPAN><SPAN class="p">);</SPAN>
  <SPAN class="p">}</SPAN>
 <SPAN class="p">}</SPAN>
 <SPAN class="n">delete_case6</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>
<SPAN class="p">}</SPAN>
</PRE></DIV>
<TABLE>
<TBODY><TR>
<TD>
<DIV class="floatright"><A href="/wiki/File:Red-black_tree_delete_case_6_as_svg.svg" class="image" title="Diagram of case 6"><IMG alt="Diagram of case 6" src="//upload.wikimedia.org/wikipedia/commons/thumb/9/99/Red-black_tree_delete_case_6_as_svg.svg/337px-Red-black_tree_delete_case_6_as_svg.svg.png" width="337" height="133" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/99/Red-black_tree_delete_case_6_as_svg.svg/506px-Red-black_tree_delete_case_6_as_svg.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/99/Red-black_tree_delete_case_6_as_svg.svg/674px-Red-black_tree_delete_case_6_as_svg.svg.png 2x" data-file-width="622" data-file-height="246" /></A></DIV>
<P><B>Case 6:</B> <B>S</B> is black, <B>S</B>'s right child is red, and <B>N</B> is the left child of its parent <B>P</B>. In this case we rotate left at <B>P</B>, so that <B>S</B> becomes the parent of <B>P</B> and <B>S</B>'s right child. We then exchange the colors of <B>P</B> and <B>S</B>, and make <B>S</B>'s right child black. The subtree still has the same color at its root, so Properties 4 (Both children of every red node are black) and 5 (All paths from any given node to its leaf nodes contain the same number of black nodes) are not violated. However, <B>N</B> now has one additional black ancestor: either <B>P</B> has become black, or it was black and <B>S</B> was added as a black grandparent. Thus, the paths passing through <B>N</B> pass through one additional black node.</P>
<P>Meanwhile, if a path does not go through <B>N</B>, then there are two possibilities:</P>
<OL>
<LI>It goes through <B>N</B>'s new sibling <B>S<SUB>L</SUB></B>, a node with arbitrary color and the root of the subtree labeled <B>3</B> (s. diagram). Then, it must go through <B>S</B> and <B>P</B>, both formerly and currently, as they have only exchanged colors and places. Thus the path contains the same number of black nodes.</LI>
<LI>It goes through <B>N</B>'s new uncle, <B>S</B>'s right child. Then, it formerly went through <B>S</B>, <B>S</B>'s parent, and <B>S</B>'s right child <B>S<SUB>R</SUB></B> (which was red), but now only goes through <B>S</B>, which has assumed the color of its former parent, and <B>S</B>'s right child, which has changed from red to black (assuming <B>S</B>'s color: black). The net effect is that this path goes through the same number of black nodes.</LI>
</OL>
<P>Either way, the number of black nodes on these paths does not change. Thus, we have restored Properties 4 (Both children of every red node are black) and 5 (All paths from any given node to its leaf nodes contain the same number of black nodes). The white node in the diagram can be either red or black, but must refer to the same color both before and after the transformation.</P>
</TD>
</TR>
</TBODY></TABLE>
<DIV class="mw-highlight mw-content-ltr" dir="ltr">
<PRE><SPAN class="kt">void</SPAN> <SPAN class="nf">delete_case6</SPAN><SPAN class="p">(</SPAN><SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">n</SPAN><SPAN class="p">)</SPAN>
<SPAN class="p">{</SPAN>
 <SPAN class="k">struct</SPAN> <SPAN class="n">node</SPAN> <SPAN class="o">*</SPAN><SPAN class="n">s</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">sibling</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="p">);</SPAN>

 <SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN><SPAN class="p">;</SPAN>
 <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">;</SPAN>

 <SPAN class="k">if</SPAN> <SPAN class="p">(</SPAN><SPAN class="n">n</SPAN> <SPAN class="o">==</SPAN> <SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN><SPAN class="p">)</SPAN> <SPAN class="p">{</SPAN>
  <SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">right</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">;</SPAN>
  <SPAN class="n">rotate_left</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN><SPAN class="p">);</SPAN>
 <SPAN class="p">}</SPAN> <SPAN class="k">else</SPAN> <SPAN class="p">{</SPAN>
  <SPAN class="n">s</SPAN><SPAN class="o">-></SPAN><SPAN class="n">left</SPAN><SPAN class="o">-></SPAN><SPAN class="n">color</SPAN> <SPAN class="o">=</SPAN> <SPAN class="n">BLACK</SPAN><SPAN class="p">;</SPAN>
  <SPAN class="n">rotate_right</SPAN><SPAN class="p">(</SPAN><SPAN class="n">n</SPAN><SPAN class="o">-></SPAN><SPAN class="n">parent</SPAN><SPAN class="p">);</SPAN>
 <SPAN class="p">}</SPAN>
<SPAN class="p">}</SPAN>
</PRE></DIV>
<P>Again, the function calls all use <A href="/wiki/Tail_recursion" class="mw-redirect" title="Tail recursion">tail recursion</A>, so the algorithm is <A href="/wiki/In-place_algorithm" title="In-place algorithm">in-place</A>.</P>
<P>In the algorithm above, all cases are chained in order, except in delete case 3 where it can recurse to case 1 back to the parent node: this is the only case where an iterative implementation will effectively loop. No more than <SPAN class="texhtml">h</SPAN> loops back to case 1 will occur (where <SPAN class="texhtml">h</SPAN> is the height of the tree). And because the probability for escalation decreases exponentially with each iteration the average removal cost is constant.</P>
<P>Additionally, no tail recursion ever occurs on a child node, so the tail recursion loop can only move from a child back to its successive ancestors. If a rotation occurs in case 2 (which is the only possibility of rotation within the loop of cases 1–3), then the parent of the node <B>N</B> becomes red after the rotation and we will exit the loop. Therefore, at most one rotation will occur within this loop. Since no more than two additional rotations will occur after exiting the loop, at most three rotations occur in total.</P>
<P><A href="#CITEREFMehlhornSanders2008">Mehlhorn & Sanders (2008)</A> point out: "AVL trees do not support constant <A href="/wiki/Amortized_analysis" title="Amortized analysis"><I>amortized</I></A> deletion costs", but red-black trees do.<SUP id="cite_ref-25" class="reference"><A href="#cite_note-25">[24]</A></SUP></P>
<H2><SPAN class="mw-headline" id="Proof_of_asymptotic_bounds">Proof of asymptotic bounds</SPAN><SPAN class="mw-editsection"><SPAN class="mw-editsection-bracket">[</SPAN><A href="/w/index.php?title=Red%E2%80%93black_tree&action=edit&section=9" title="Edit section: Proof of asymptotic bounds">edit</A><SPAN class="mw-editsection-bracket">]</SPAN></SPAN></H2>
<P>A red black tree which contains <I>n</I> internal nodes has a height of <SPAN class="texhtml">O(log <I>n</I>)</SPAN>.</P>
<P>Definitions:</P>
<UL>
<LI>h(<I>v</I>) = height of subtree rooted at node <I>v</I></LI>
<LI>bh(<I>v</I>) = the number of black nodes from <I>v</I> to any leaf in the subtree, not counting <I>v</I> if it is black - called the black-height</LI>
</UL>
<P><B>Lemma:</B> A subtree rooted at node <I>v</I> has at least <SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <msup>
          <mn>2</mn>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>b</mi>
            <mi>h</mi>
            <mo stretchy="false">(</mo>
            <mi>v</mi>
            <mo stretchy="false">)</mo>
          </mrow>
        </msup>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle 2^{bh(v)}-1}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bd20e4a4bb09ff8a0b1f669e13d80a767fd380dc" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:9.195ex; height:2.843ex;" alt="2^{bh(v)}-1" /></SPAN> internal nodes.</P>
<P>Proof of Lemma (by induction height):</P>
<P>Basis: h(<I>v</I>) = 0</P>
<P>If <I>v</I> has a height of zero then it must be <I>null</I>, therefore bh(<I>v</I>) = 0. So:</P>
<DL>
<DD><SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <msup>
          <mn>2</mn>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>b</mi>
            <mi>h</mi>
            <mo stretchy="false">(</mo>
            <mi>v</mi>
            <mo stretchy="false">)</mo>
          </mrow>
        </msup>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
        <mo>=</mo>
        <msup>
          <mn>2</mn>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>0</mn>
          </mrow>
        </msup>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
        <mo>=</mo>
        <mn>1</mn>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
        <mo>=</mo>
        <mn>0</mn>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle 2^{bh(v)}-1=2^{0}-1=1-1=0}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ff9f9c03b2a1d90a61e2c983de3a4a32859f7a0e" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:31.149ex; height:2.843ex;" alt="2^{bh(v)}-1=2^{0}-1=1-1=0" /></SPAN></DD>
</DL>
<P>Inductive Step: <I>v</I> such that h(<I>v</I>) = k, has at least <SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <msup>
          <mn>2</mn>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>b</mi>
            <mi>h</mi>
            <mo stretchy="false">(</mo>
            <mi>v</mi>
            <mo stretchy="false">)</mo>
          </mrow>
        </msup>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle 2^{bh(v)}-1}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bd20e4a4bb09ff8a0b1f669e13d80a767fd380dc" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:9.195ex; height:2.843ex;" alt="2^{bh(v)}-1" /></SPAN> internal nodes implies that <SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <msup>
          <mi>v</mi>
          <mo>′</mo>
        </msup>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle v'}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19f1c5b0af1f30c41cb8bc0ba3bfea98681da268" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:1.83ex; height:2.509ex;" alt="v'" /></SPAN> such that h(<SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <msup>
          <mi>v</mi>
          <mo>′</mo>
        </msup>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle v'}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19f1c5b0af1f30c41cb8bc0ba3bfea98681da268" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:1.83ex; height:2.509ex;" alt="v'" /></SPAN>) = k+1 has at least <SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <msup>
          <mn>2</mn>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>b</mi>
            <mi>h</mi>
            <mo stretchy="false">(</mo>
            <msup>
              <mi>v</mi>
              <mo>′</mo>
            </msup>
            <mo stretchy="false">)</mo>
          </mrow>
        </msup>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle 2^{bh(v')}-1}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/89836b789850ab1dbccb41765e54847a9734d57a" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:9.732ex; height:2.843ex;" alt="2^{bh(v')}-1" /></SPAN> internal nodes.</P>
<P>Since <SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <msup>
          <mi>v</mi>
          <mo>′</mo>
        </msup>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle v'}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19f1c5b0af1f30c41cb8bc0ba3bfea98681da268" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:1.83ex; height:2.509ex;" alt="v'" /></SPAN> has h(<SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <msup>
          <mi>v</mi>
          <mo>′</mo>
        </msup>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle v'}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19f1c5b0af1f30c41cb8bc0ba3bfea98681da268" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:1.83ex; height:2.509ex;" alt="v'" /></SPAN>) > 0 it is an internal node. As such it has two children each of which have a black-height of either bh(<SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <msup>
          <mi>v</mi>
          <mo>′</mo>
        </msup>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle v'}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19f1c5b0af1f30c41cb8bc0ba3bfea98681da268" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:1.83ex; height:2.509ex;" alt="v'" /></SPAN>) or bh(<SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <msup>
          <mi>v</mi>
          <mo>′</mo>
        </msup>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle v'}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19f1c5b0af1f30c41cb8bc0ba3bfea98681da268" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:1.83ex; height:2.509ex;" alt="v'" /></SPAN>)-1 (depending on whether the child is red or black, respectively). By the inductive hypothesis each child has at least <SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <msup>
          <mn>2</mn>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>b</mi>
            <mi>h</mi>
            <mo stretchy="false">(</mo>
            <msup>
              <mi>v</mi>
              <mo>′</mo>
            </msup>
            <mo stretchy="false">)</mo>
            <mo>−<!-- − --></mo>
            <mn>1</mn>
          </mrow>
        </msup>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle 2^{bh(v')-1}-1}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0216c4028ab1738e9ea784c87a506f1f8d050dd4" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:11.848ex; height:2.843ex;" alt="2^{bh(v')-1}-1" /></SPAN> internal nodes, so <SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <msup>
          <mi>v</mi>
          <mo>′</mo>
        </msup>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle v'}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19f1c5b0af1f30c41cb8bc0ba3bfea98681da268" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:1.83ex; height:2.509ex;" alt="v'" /></SPAN> has at least:</P>
<DL>
<DD><SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <msup>
          <mn>2</mn>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>b</mi>
            <mi>h</mi>
            <mo stretchy="false">(</mo>
            <msup>
              <mi>v</mi>
              <mo>′</mo>
            </msup>
            <mo stretchy="false">)</mo>
            <mo>−<!-- − --></mo>
            <mn>1</mn>
          </mrow>
        </msup>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
        <mo>+</mo>
        <msup>
          <mn>2</mn>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>b</mi>
            <mi>h</mi>
            <mo stretchy="false">(</mo>
            <msup>
              <mi>v</mi>
              <mo>′</mo>
            </msup>
            <mo stretchy="false">)</mo>
            <mo>−<!-- − --></mo>
            <mn>1</mn>
          </mrow>
        </msup>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
        <mo>+</mo>
        <mn>1</mn>
        <mo>=</mo>
        <msup>
          <mn>2</mn>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>b</mi>
            <mi>h</mi>
            <mo stretchy="false">(</mo>
            <msup>
              <mi>v</mi>
              <mo>′</mo>
            </msup>
            <mo stretchy="false">)</mo>
          </mrow>
        </msup>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle 2^{bh(v')-1}-1+2^{bh(v')-1}-1+1=2^{bh(v')}-1}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8a1682e47a748de66e8bbb72355a047216b3ede7" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.505ex; width:43.411ex; height:3.009ex;" alt="2^{bh(v')-1}-1+2^{bh(v')-1}-1+1=2^{bh(v')}-1" /></SPAN></DD>
</DL>
<P>internal nodes.</P>
<P>Using this lemma we can now show that the height of the tree is logarithmic. Since at least half of the nodes on any path from the root to a leaf are black (property 4 of a red–black tree), the black-height of the root is at least h(root)/2. By the lemma we get:</P>
<DL>
<DD><SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mi>n</mi>
        <mo>≥<!-- ≥ --></mo>
        <msup>
          <mn>2</mn>
          <mrow class="MJX-TeXAtom-ORD">
            <mfrac>
              <mrow>
                <mi>h</mi>
                <mo stretchy="false">(</mo>
                <mrow class="MJX-TeXAtom-ORD">
                  <mtext>root</mtext>
                </mrow>
                <mo stretchy="false">)</mo>
              </mrow>
              <mn>2</mn>
            </mfrac>
          </mrow>
        </msup>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
        <mo stretchy="false">↔<!-- ↔ --></mo>
        <mspace width="thickmathspace"></mspace>
        <msub>
          <mi>log</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>2</mn>
          </mrow>
        </msub>
        <mo><!--  --></mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mo stretchy="false">(</mo>
          <mi>n</mi>
          <mo>+</mo>
          <mn>1</mn>
          <mo stretchy="false">)</mo>
        </mrow>
        <mo>≥<!-- ≥ --></mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mfrac>
            <mrow>
              <mi>h</mi>
              <mo stretchy="false">(</mo>
              <mrow class="MJX-TeXAtom-ORD">
                <mtext>root</mtext>
              </mrow>
              <mo stretchy="false">)</mo>
            </mrow>
            <mn>2</mn>
          </mfrac>
        </mrow>
        <mo stretchy="false">↔<!-- ↔ --></mo>
        <mspace width="thickmathspace"></mspace>
        <mi>h</mi>
        <mo stretchy="false">(</mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mtext>root</mtext>
        </mrow>
        <mo stretchy="false">)</mo>
        <mo>≤<!-- ≤ --></mo>
        <mn>2</mn>
        <msub>
          <mi>log</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>2</mn>
          </mrow>
        </msub>
        <mo><!--  --></mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mo stretchy="false">(</mo>
          <mi>n</mi>
          <mo>+</mo>
          <mn>1</mn>
          <mo stretchy="false">)</mo>
        </mrow>
        <mo>.</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle n\geq 2^{h({\text{root}}) \over 2}-1\leftrightarrow \;\log _{2}{(n+1)}\geq {h({\text{root}}) \over 2}\leftrightarrow \;h({\text{root}})\leq 2\log _{2}{(n+1)}.}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9e7e6443819b2fdcaaaf750694cf309017ddcd61" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -1.838ex; width:70.964ex; height:5.676ex;" alt="n\geq 2^{h({\text{root}}) \over 2}-1\leftrightarrow \;\log _{2}{(n+1)}\geq {h({\text{root}}) \over 2}\leftrightarrow \;h({\text{root}})\leq 2\log _{2}{(n+1)}." /></SPAN></DD>
</DL>
<P>Therefore, the height of the root is <SPAN class="texhtml">O(log <I>n</I>)</SPAN>.</P>
<H2><SPAN class="mw-headline" id="Set_operations_and_bulk_operations">Set operations and bulk operations</SPAN><SPAN class="mw-editsection"><SPAN class="mw-editsection-bracket">[</SPAN><A href="/w/index.php?title=Red%E2%80%93black_tree&action=edit&section=10" title="Edit section: Set operations and bulk operations">edit</A><SPAN class="mw-editsection-bracket">]</SPAN></SPAN></H2>
<P>In addition to the single-element insert, delete and lookup operations, several set operations have been defined on red-black trees: <A href="/wiki/Union_(set_theory)" title="Union (set theory)">union</A>, <A href="/wiki/Intersection_(set_theory)" title="Intersection (set theory)">intersection</A> and <A href="/wiki/Set_difference" class="mw-redirect" title="Set difference">set difference</A>. Then fast <I>bulk</I> operations on insertions or deletions can be implemented based on these set functions. These set operations rely on two helper operations, <I>Split</I> and <I>Join</I>. With the new operations, the implementation of red-black trees can be more efficient and highly-parallelizable.<SUP id="cite_ref-join-based_26-0" class="reference"><A href="#cite_note-join-based-26">[25]</A></SUP> This implementation allows a red root.</P>
<UL>
<LI><I>Join</I>: The function <I>Join</I> is on two red-black trees <SPAN class="texhtml"><I>t</I><SUB>1</SUB></SPAN> and <SPAN class="texhtml"><I>t</I><SUB>2</SUB></SPAN> and a key <SPAN class="texhtml mvar" style="font-style:italic;">k</SPAN> and will return a tree containing all elements in <SPAN class="texhtml"><I>t</I><SUB>1</SUB></SPAN>, <SPAN class="texhtml"><I>t</I><SUB>2</SUB></SPAN> as well as <SPAN class="texhtml mvar" style="font-style:italic;">k</SPAN>. It requires <SPAN class="texhtml mvar" style="font-style:italic;">k</SPAN> to be greater than all keys in <SPAN class="texhtml"><I>t</I><SUB>1</SUB></SPAN> and smaller than all keys in <SPAN class="texhtml"><I>t</I><SUB>2</SUB></SPAN>. If the two trees have the same black height, <I>Join</I> simply create a new node with left subtree <SPAN class="texhtml"><I>t</I><SUB>1</SUB></SPAN>, root <SPAN class="texhtml mvar" style="font-style:italic;">k</SPAN> and right subtree <SPAN class="texhtml"><I>t</I><SUB>2</SUB></SPAN>. If both <SPAN class="texhtml"><I>t</I><SUB>1</SUB></SPAN> and <SPAN class="texhtml"><I>t</I><SUB>2</SUB></SPAN> have black root, set <SPAN class="texhtml mvar" style="font-style:italic;">k</SPAN> to be red. Otherwise <SPAN class="texhtml mvar" style="font-style:italic;">k</SPAN> is set black. Suppose that <SPAN class="texhtml"><I>t</I><SUB>1</SUB></SPAN> has larger black height than <SPAN class="texhtml"><I>t</I><SUB>2</SUB></SPAN> (the other case is symmetric). <I>Join</I> follows the right spine of <SPAN class="texhtml"><I>t</I><SUB>1</SUB></SPAN> until a black node <SPAN class="texhtml mvar" style="font-style:italic;">c</SPAN> which is balanced with <SPAN class="texhtml"><I>t</I><SUB>2</SUB></SPAN>. At this point a new node with left child <SPAN class="texhtml mvar" style="font-style:italic;">c</SPAN>, root <SPAN class="texhtml mvar" style="font-style:italic;">k</SPAN> (set to be red) and right child <SPAN class="texhtml"><I>t</I><SUB>1</SUB></SPAN> is created to replace c. The new node may invalidate the red-black invariant because at most three red nodes can appear in a row. This can be fixed with a double rotation. If double red issue propagates to the root, the root is then set to be black, restoring the properties. The cost of this function is the difference of the black heights between the two input trees.</LI>
<LI><I>Split</I>: To split a red-black tree into two smaller trees, those smaller than key <I>x</I>, and those larger than key <I>x</I>, first draw a path from the root by inserting <I>x</I> into the red-black tree. After this insertion, all values less than <I>x</I> will be found on the left of the path, and all values greater than <I>x</I> will be found on the right. By applying <I>Join</I>, all the subtrees on the left side are merged bottom-up using keys on the path as intermediate nodes from bottom to top to form the left tree, and the right part is asymmetric. The cost of <I>Split</I> is order of <SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mi>O</mi>
        <mo stretchy="false">(</mo>
        <mi>log</mi>
        <mo><!--  --></mo>
        <mi>n</mi>
        <mo stretchy="false">)</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aae0f22048ba6b7c05dbae17b056bfa16e21807d" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:8.409ex; height:2.843ex;" alt="O(\log n)" /></SPAN>, the height of the tree.</LI>
</UL>
<P>The union of two red-black trees <SPAN class="texhtml"><I>t</I><SUB>1</SUB></SPAN> and <SPAN class="texhtml"><I>t</I><SUB>2</SUB></SPAN> representing sets <SPAN class="texhtml mvar" style="font-style:italic;">A</SPAN> and <SPAN class="texhtml mvar" style="font-style:italic;">B</SPAN>, is a red-black tree <SPAN class="texhtml mvar" style="font-style:italic;"><I>t</I></SPAN> that represents <SPAN class="texhtml"><I>A</I> ∪ <I>B</I></SPAN>. The following recursive function computes this union:</P>
<PRE><B>function</B> union(t<SUB>1</SUB>, t<SUB>2</SUB>):
    <B>if</B> t<SUB>1</SUB> = nil:
        <B>return</B> t<SUB>2</SUB>
    <B>if</B> t<SUB>2</SUB> = nil:
        <B>return</B> t<SUB>1</SUB>
    t<SUB><</SUB>, t<SUB>></SUB> ← split t<SUB>2</SUB> on t<SUB>1</SUB>.root
    <B>return</B> join(t<SUB>1</SUB>.root, union(left(t<SUB>1</SUB>), t<SUB><</SUB>), union(right(t<SUB>1</SUB>), t<SUB>></SUB>))
</PRE>
<P>Here, <I>Split</I> is presumed to return two trees: one holding the keys less its input key, one holding the greater keys. (The algorithm is <A href="/wiki/Persistent_data_structure" title="Persistent data structure">non-destructive</A>, but an in-place destructive version exists as well.)</P>
<P>The algorithm for intersection or difference is similar, but requires the <I>Join2</I> helper routine that is the same as <I>Join</I> but without the middle key. Based on the new functions for union, intersection or difference, either one key or multiple keys can be inserted to or deleted from the red-black tree. Since <I>Split</I> calls <I>Join</I> but does not deal with the balancing criteria of red-black trees directly, such an implementation is usually called the "join-based" implementation.</P>
<P>The complexity of each of union, intersection and difference is <SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mi>O</mi>
        <mrow>
          <mo>(</mo>
          <mi>m</mi>
          <mi>log</mi>
          <mo><!--  --></mo>
          <mrow>
            <mo>(</mo>
            <mrow class="MJX-TeXAtom-ORD">
              <mfrac>
                <mi>n</mi>
                <mi>m</mi>
              </mfrac>
            </mrow>
            <mo>+</mo>
            <mn>1</mn>
            <mo>)</mo>
          </mrow>
          <mo>)</mo>
        </mrow>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle O\left(m\log \left({n \over m}+1\right)\right)}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0cd2f7cee37ecf49ccaf8ef28ee006cb55f6b95b" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -1.838ex; width:20.115ex; height:4.843ex;" alt="{\displaystyle O\left(m\log \left({n \over m}+1\right)\right)}" /></SPAN> for two red-black trees of sizes <SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mi>m</mi>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle m}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:2.051ex; height:1.676ex;" alt="m" /></SPAN> and <SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mi>n</mi>
        <mo stretchy="false">(</mo>
        <mo>≥<!-- ≥ --></mo>
        <mi>m</mi>
        <mo stretchy="false">)</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle n(\geq m)}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8999105a5cf1555933b40c34c91d4a78a3c9b487" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:7.75ex; height:2.843ex;" alt="{\displaystyle n(\geq m)}" /></SPAN>. This complexity is optimal in terms of the number of comparisons. More importantly, since the recursive calls to union, intersection or difference are independent of each other, they can be executed <A href="/wiki/Parallel_programming" class="mw-redirect" title="Parallel programming">in parallel</A> with a <A href="/wiki/Analysis_of_parallel_algorithms" title="Analysis of parallel algorithms">parallel depth</A> <SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mi>O</mi>
        <mo stretchy="false">(</mo>
        <mi>log</mi>
        <mo><!--  --></mo>
        <mi>m</mi>
        <mi>log</mi>
        <mo><!--  --></mo>
        <mi>n</mi>
        <mo stretchy="false">)</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle O(\log m\log n)}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b79240ec677da2c426ef4db2f50ff29a86cc233c" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:14.237ex; height:2.843ex;" alt="{\displaystyle O(\log m\log n)}" /></SPAN>.<SUP id="cite_ref-join-based_26-1" class="reference"><A href="#cite_note-join-based-26">[25]</A></SUP> When <SPAN class="mwe-math-element"><SPAN class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mi>m</mi>
        <mo>=</mo>
        <mn>1</mn>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle m=1}</annotation>
  </semantics>
</math></SPAN><IMG src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b6100c5ebd48c6fd848709f2be624465203eb173" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:6.333ex; height:2.176ex;" alt="m=1" /></SPAN>, the join-based implementation has the same computational DAG as single-element insertion and deletion if the root of the larger tree is used to split the smaller tree.</P>
<H2><SPAN class="mw-headline" id="Parallel_algorithms">Parallel algorithms</SPAN><SPAN class="mw-editsection"><SPAN class="mw-editsection-bracket">[</SPAN><A href="/w/index.php?title=Red%E2%80%93black_tree&action=edit&section=11" title="Edit section: Parallel algorithms">edit</A><SPAN class="mw-editsection-bracket">]</SPAN></SPAN></H2>
<P>Parallel algorithms for constructing red–black trees from sorted lists of items can run in constant time or <SPAN class="texhtml">O(log log <I>n</I>)</SPAN> time, depending on the computer model, if the number of processors available is asymptotically proportional to the number <SPAN class="texhtml"><I>n</I></SPAN> of items where <SPAN class="texhtml"><I>n</I>→∞</SPAN>. Fast search, insertion, and deletion parallel algorithms are also known.<SUP id="cite_ref-27" class="reference"><A href="#cite_note-27">[26]</A></SUP></P>
<H2><SPAN class="mw-headline" id="Popular_culture">Popular culture</SPAN><SPAN class="mw-editsection"><SPAN class="mw-editsection-bracket">[</SPAN><A href="/w/index.php?title=Red%E2%80%93black_tree&action=edit&section=12" title="Edit section: Popular culture">edit</A><SPAN class="mw-editsection-bracket">]</SPAN></SPAN></H2>
<P>A red-black-tree was referenced correctly in an episode of <A href="/wiki/Missing_(Canadian_TV_series)" title="Missing (Canadian TV series)">Missing (Canadian TV series)</A><SUP id="cite_ref-28" class="reference"><A href="#cite_note-28">[27]</A></SUP> as noted by <A href="/wiki/Robert_Sedgewick_(computer_scientist)" title="Robert Sedgewick (computer scientist)">Robert Sedgewick</A> in one of his lectures:<SUP id="cite_ref-29" class="reference"><A href="#cite_note-29">[28]</A></SUP></P>
<P><B>Jess</B>: " It was the red door again. "<BR />
<B>Pollock</B>: " I thought the red door was the storage container. "<BR />
<B>Jess</B>: " But it wasn't red anymore, it was black. "<BR />
<B>Antonio</B>: " So red turning to black means what? "<BR />
<B>Pollock</B>: " Budget deficits, red ink, black ink. "<BR />
<B>Antonio</B>: " It could be from a binary search tree. The red-black tree tracks every simple path from a node to a descendant leaf that has the same number of black nodes. "<BR />
<B>Jess</B>: " Does that help you with the ladies? "</P>
<H2><SPAN class="mw-headline" id="See_also">See also</SPAN><SPAN class="mw-editsection"><SPAN class="mw-editsection-bracket">[</SPAN><A href="/w/index.php?title=Red%E2%80%93black_tree&action=edit&section=13" title="Edit section: See also">edit</A><SPAN class="mw-editsection-bracket">]</SPAN></SPAN></H2>
<UL>
<LI><A href="/wiki/List_of_data_structures" title="List of data structures">List of data structures</A></LI>
<LI><A href="/wiki/Tree_data_structure" class="mw-redirect" title="Tree data structure">Tree data structure</A></LI>
<LI><A href="/wiki/Tree_rotation" title="Tree rotation">Tree rotation</A></LI>
<LI><A href="/wiki/AA_tree" title="AA tree">AA tree</A>, a variation of the red-black tree</LI>
<LI><A href="/wiki/AVL_tree" title="AVL tree">AVL tree</A></LI>
<LI><A href="/wiki/B-tree" title="B-tree">B-tree</A> (<A href="/wiki/2-3_tree" class="mw-redirect" title="2-3 tree">2-3 tree</A>, <A href="/wiki/2-3-4_tree" class="mw-redirect" title="2-3-4 tree">2-3-4 tree</A>, <A href="/wiki/B%2B_tree" title="B+ tree">B+ tree</A>, <A href="/wiki/B*-tree" class="mw-redirect" title="B*-tree">B*-tree</A>, <A href="/wiki/UB-tree" title="UB-tree">UB-tree</A>)</LI>
<LI><A href="/wiki/Scapegoat_tree" title="Scapegoat tree">Scapegoat tree</A></LI>
<LI><A href="/wiki/Splay_tree" title="Splay tree">Splay tree</A></LI>
<LI><A href="/wiki/T-tree" title="T-tree">T-tree</A></LI>
<LI><A href="/wiki/WAVL_tree" title="WAVL tree">WAVL tree</A></LI>
</UL>
<H2><SPAN class="mw-headline" id="References">References</SPAN><SPAN class="mw-editsection"><SPAN class="mw-editsection-bracket">[</SPAN><A href="/w/index.php?title=Red%E2%80%93black_tree&action=edit&section=14" title="Edit section: References">edit</A><SPAN class="mw-editsection-bracket">]</SPAN></SPAN></H2>
<DIV class="reflist columns references-column-width" style="-moz-column-width: 37em; -webkit-column-width: 37em; column-width: 37em; list-style-type: decimal;">
<OL class="references">
<LI id="cite_note-wiscurl-1"><SPAN class="mw-cite-backlink">^ <A href="#cite_ref-wiscurl_1-0"><SPAN class="cite-accessibility-label">Jump up to: </SPAN><SUP><I><B>a</B></I></SUP></A> <A href="#cite_ref-wiscurl_1-1"><SUP><I><B>b</B></I></SUP></A> <A href="#cite_ref-wiscurl_1-2"><SUP><I><B>c</B></I></SUP></A> <A href="#cite_ref-wiscurl_1-3"><SUP><I><B>d</B></I></SUP></A> <A href="#cite_ref-wiscurl_1-4"><SUP><I><B>e</B></I></SUP></A> <A href="#cite_ref-wiscurl_1-5"><SUP><I><B>f</B></I></SUP></A></SPAN> <SPAN class="reference-text"><CITE class="citation web">James Paton. <A rel="nofollow" class="external text" href="http://pages.cs.wisc.edu/~paton/readings/Red-Black-Trees/">"Red-Black Trees"</A>.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Red-Black+Trees&rft.au=James+Paton&rft_id=http%3A%2F%2Fpages.cs.wisc.edu%2F~paton%2Freadings%2FRed-Black-Trees%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-:0-2"><SPAN class="mw-cite-backlink">^ <A href="#cite_ref-:0_2-0"><SPAN class="cite-accessibility-label">Jump up to: </SPAN><SUP><I><B>a</B></I></SUP></A> <A href="#cite_ref-:0_2-1"><SUP><I><B>b</B></I></SUP></A></SPAN> <SPAN class="reference-text"><CITE id="CITEREFCormenLeisersonRivestStein2001" class="citation book"><A href="/wiki/Thomas_H._Cormen" title="Thomas H. Cormen">Cormen, Thomas H.</A>; <A href="/wiki/Charles_E._Leiserson" title="Charles E. Leiserson">Leiserson, Charles E.</A>; <A href="/wiki/Ronald_L._Rivest" class="mw-redirect" title="Ronald L. Rivest">Rivest, Ronald L.</A>; <A href="/wiki/Clifford_Stein" title="Clifford Stein">Stein, Clifford</A> (2001). "Red–Black Trees". <I><A href="/wiki/Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms</A></I> (second ed.). MIT Press. pp. 273–301. <A href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</A> <A href="/wiki/Special:BookSources/0-262-03293-7" title="Special:BookSources/0-262-03293-7">0-262-03293-7</A>.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Red%26ndash%3BBlack+Trees&rft.btitle=Introduction+to+Algorithms&rft.pages=273-301&rft.edition=second&rft.pub=MIT+Press&rft.date=2001&rft.isbn=0-262-03293-7&rft.aulast=Cormen&rft.aufirst=Thomas+H.&rft.au=Leiserson%2C+Charles+E.&rft.au=Rivest%2C+Ronald+L.&rft.au=Stein%2C+Clifford&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-3"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-3"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation web">John Morris. <A rel="nofollow" class="external text" href="http://www.cs.auckland.ac.nz/~jmor159/PLDS210/red_black.html">"Red–Black Trees"</A>.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Red%E2%80%93Black+Trees&rft.au=John+Morris&rft_id=http%3A%2F%2Fwww.cs.auckland.ac.nz%2F~jmor159%2FPLDS210%2Fred_black.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-Bayer72-4"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-Bayer72_4-0"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation journal">Rudolf Bayer (1972). <A rel="nofollow" class="external text" href="http://www.springerlink.com/content/qh51m2014673513j/">"Symmetric binary B-Trees: Data structure and maintenance algorithms"</A>. <I>Acta Informatica</I>. <B>1</B> (4): 290–306. <A href="/wiki/Digital_object_identifier" title="Digital object identifier">doi</A>:<A rel="nofollow" class="external text" href="//doi.org/10.1007%2FBF00289509">10.1007/BF00289509</A>.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Acta+Informatica&rft.atitle=Symmetric+binary+B-Trees%3A+Data+structure+and+maintenance+algorithms&rft.volume=1&rft.issue=4&rft.pages=290-306&rft.date=1972&rft_id=info%3Adoi%2F10.1007%2FBF00289509&rft.au=Rudolf+Bayer&rft_id=http%3A%2F%2Fwww.springerlink.com%2Fcontent%2Fqh51m2014673513j%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-5"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-5"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation book">Drozdek, Adam. <I>Data Structures and Algorithms in Java</I> (2 ed.). Sams Publishing. p. 323. <A href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</A> <A href="/wiki/Special:BookSources/0534376681" title="Special:BookSources/0534376681">0534376681</A>.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Data+Structures+and+Algorithms+in+Java&rft.pages=323&rft.edition=2&rft.pub=Sams+Publishing&rft.isbn=0534376681&rft.aulast=Drozdek&rft.aufirst=Adam&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-GS78-6"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-GS78_6-0"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation conference">Leonidas J. Guibas and Robert Sedgewick (1978). <A rel="nofollow" class="external text" href="http://doi.ieeecomputersociety.org/10.1109/SFCS.1978.3">"A Dichromatic Framework for Balanced Trees"</A>. <I>Proceedings of the 19th Annual Symposium on Foundations of Computer Science</I>. pp. 8–21. <A href="/wiki/Digital_object_identifier" title="Digital object identifier">doi</A>:<A rel="nofollow" class="external text" href="//doi.org/10.1109%2FSFCS.1978.3">10.1109/SFCS.1978.3</A>.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=A+Dichromatic+Framework+for+Balanced+Trees&rft.btitle=Proceedings+of+the+19th+Annual+Symposium+on+Foundations+of+Computer+Science&rft.pages=8-21&rft.date=1978&rft_id=info%3Adoi%2F10.1109%2FSFCS.1978.3&rft.au=Leonidas+J.+Guibas+and+Robert+Sedgewick&rft_id=http%3A%2F%2Fdoi.ieeecomputersociety.org%2F10.1109%2FSFCS.1978.3&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-7"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-7"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation web"><A rel="nofollow" class="external text" href="http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx">"Red Black Trees"</A>. <I>eternallyconfuzzled.com</I><SPAN class="reference-accessdate">. Retrieved <SPAN class="nowrap">2015-09-02</SPAN></SPAN>.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=eternallyconfuzzled.com&rft.atitle=Red+Black+Trees&rft_id=http%3A%2F%2Feternallyconfuzzled.com%2Ftuts%2Fdatastructures%2Fjsw_tut_rbtree.aspx&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-Sedgewick12-8"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-Sedgewick12_8-0"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation audio-visual">Robert Sedgewick (2012). <A rel="nofollow" class="external text" href="https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/8acpe/red-black-trees"><I>Red-Black BSTs</I></A>. Coursera. <Q>A lot of people ask why did we use the name red–black. Well, we invented this data structure, this way of looking at balanced trees, at Xerox PARC which was the home of the personal computer and many other innovations that we live with today entering[sic] graphic user interfaces, ethernet and object-oriented programmings[sic] and many other things. But one of the things that was invented there was laser printing and we were very excited to have nearby color laser printer that could print things out in color and out of the colors the red looked the best. So, that’s why we picked the color red to distinguish red links, the types of links, in three nodes. So, that’s an answer to the question for people that have been asking.</Q></CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Red-Black+BSTs&rft.pub=Coursera&rft.date=2012&rft_id=https%3A%2F%2Fwww.coursera.org%2Flearn%2Falgorithms-graphs-data-structures%2Flecture%2F8acpe%2Fred-black-trees&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-9"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-9"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation web"><A rel="nofollow" class="external text" href="http://programmers.stackexchange.com/a/116621/40127">"Where does the term "Red/Black Tree" come from?"</A>. <I>programmers.stackexchange.com</I><SPAN class="reference-accessdate">. Retrieved <SPAN class="nowrap">2015-09-02</SPAN></SPAN>.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=programmers.stackexchange.com&rft.atitle=Where+does+the+term+%22Red%2FBlack+Tree%22+come+from%3F&rft_id=http%3A%2F%2Fprogrammers.stackexchange.com%2Fa%2F116621%2F40127&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-10"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-10"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation journal">Andersson, Arne (1993-08-11). Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola; Whitesides, Sue, eds. <A rel="nofollow" class="external text" href="http://user.it.uu.se/~arnea/ps/simp.pdf">"Balanced search trees made simple"</A> <SPAN style="font-size:85%;">(PDF)</SPAN>. <I>Algorithms and Data Structures</I> (Proceedings). Lecture Notes in Computer Science. Springer-Verlag Berlin Heidelberg. <B>709</B>: 60–71. <A href="/wiki/Digital_object_identifier" title="Digital object identifier">doi</A>:<A rel="nofollow" class="external text" href="//doi.org/10.1007%2F3-540-57155-8_236">10.1007/3-540-57155-8_236</A>. <A href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</A> <A href="/wiki/Special:BookSources/978-3-540-57155-1" title="Special:BookSources/978-3-540-57155-1">978-3-540-57155-1</A>. Archived from <A rel="nofollow" class="external text" href="https://www.springer.com/la/book/9783540571551">the original</A> on 2000-03-17.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Algorithms+and+Data+Structures&rft.atitle=Balanced+search+trees+made+simple&rft.volume=709&rft.pages=60-71&rft.date=1993-08-11&rft_id=info%3Adoi%2F10.1007%2F3-540-57155-8_236&rft.isbn=978-3-540-57155-1&rft.aulast=Andersson&rft.aufirst=Arne&rft_id=https%3A%2F%2Fwww.springer.com%2Fla%2Fbook%2F9783540571551&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-11"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-11"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation journal">Okasaki, Chris (1999-01-01). <A rel="nofollow" class="external text" href="http://www.eecs.usma.edu/webs/people/okasaki/jfp99.ps">"Red-black trees in a functional setting"</A> <SPAN style="font-size:85%;">(PS)</SPAN>. <I>Journal of Functional Programming</I>. <B>9</B> (4): 471–477. <A href="/wiki/Digital_object_identifier" title="Digital object identifier">doi</A>:<A rel="nofollow" class="external text" href="//doi.org/10.1017%2FS0956796899003494">10.1017/S0956796899003494</A>. <A href="/wiki/International_Standard_Serial_Number" title="International Standard Serial Number">ISSN</A> <A rel="nofollow" class="external text" href="//www.worldcat.org/issn/1469-7653">1469-7653</A>.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Functional+Programming&rft.atitle=Red-black+trees+in+a+functional+setting&rft.volume=9&rft.issue=4&rft.pages=471-477&rft.date=1999-01-01&rft_id=info%3Adoi%2F10.1017%2FS0956796899003494&rft.issn=1469-7653&rft.aulast=Okasaki&rft.aufirst=Chris&rft_id=http%3A%2F%2Fwww.eecs.usma.edu%2Fwebs%2Fpeople%2Fokasaki%2Fjfp99.ps&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-Algs1-12"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-Algs1_12-0"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation book">Sedgewick, Robert (1983). <I>Algorithms</I> (1st ed.). <A href="/wiki/Addison-Wesley" title="Addison-Wesley">Addison-Wesley</A>. <A href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</A> <A href="/wiki/Special:BookSources/0-201-06672-6" title="Special:BookSources/0-201-06672-6">0-201-06672-6</A>.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Algorithms&rft.edition=1st&rft.pub=Addison-Wesley&rft.date=1983&rft.isbn=0-201-06672-6&rft.aulast=Sedgewick&rft.aufirst=Robert&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-13"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-13"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><A rel="nofollow" class="external text" href="http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/RedBlackBST.java.html">RedBlackBST code in Java</A></SPAN></LI>
<LI id="cite_note-14"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-14"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation journal"><A href="/wiki/Robert_Sedgewick_(computer_scientist)" title="Robert Sedgewick (computer scientist)">Sedgewick, Robert</A> (2008). <A rel="nofollow" class="external text" href="http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf">"Left-leaning Red-Black Trees"</A> <SPAN style="font-size:85%;">(PDF)</SPAN>.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Left-leaning+Red-Black+Trees&rft.date=2008&rft.aulast=Sedgewick&rft.aufirst=Robert&rft_id=http%3A%2F%2Fwww.cs.princeton.edu%2F~rs%2Ftalks%2FLLRB%2FLLRB.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-Algs4-15"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-Algs4_15-0"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation book">Sedgewick, Robert; Wayne, Kevin (2011). <A rel="nofollow" class="external text" href="http://algs4.cs.princeton.edu"><I>Algorithms</I></A> (4th ed.). Addison-Wesley Professional. <A href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</A> <A href="/wiki/Special:BookSources/978-0-321-57351-3" title="Special:BookSources/978-0-321-57351-3">978-0-321-57351-3</A>.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Algorithms&rft.edition=4th&rft.pub=Addison-Wesley+Professional&rft.date=2011&rft.isbn=978-0-321-57351-3&rft.aulast=Sedgewick&rft.aufirst=Robert&rft.au=Wayne%2C+Kevin&rft_id=http%3A%2F%2Falgs4.cs.princeton.edu&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-16"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-16"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation book"><A href="/wiki/Thomas_H._Cormen" title="Thomas H. Cormen">Cormen, Thomas</A>; <A href="/wiki/Charles_E._Leiserson" title="Charles E. Leiserson">Leiserson, Charles</A>; <A href="/wiki/Ron_Rivest" title="Ron Rivest">Rivest, Ronald</A>; <A href="/wiki/Clifford_Stein" title="Clifford Stein">Stein, Clifford</A> (2009). "13". <I><A href="/wiki/Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms</A></I> (3rd ed.). <A href="/wiki/MIT_Press" title="MIT Press">MIT Press</A>. pp. 308–309. <A href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</A> <A href="/wiki/Special:BookSources/978-0-262-03384-8" title="Special:BookSources/978-0-262-03384-8">978-0-262-03384-8</A>.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=13&rft.btitle=Introduction+to+Algorithms&rft.pages=308-309&rft.edition=3rd&rft.pub=MIT+Press&rft.date=2009&rft.isbn=978-0-262-03384-8&rft.aulast=Cormen&rft.aufirst=Thomas&rft.au=Leiserson%2C+Charles&rft.au=Rivest%2C+Ronald&rft.au=Stein%2C+Clifford&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-17"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-17"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE id="CITEREFMehlhornSanders2008" class="citation book"><A href="/wiki/Kurt_Mehlhorn" title="Kurt Mehlhorn">Mehlhorn, Kurt</A>; <A href="/wiki/Peter_Sanders_(computer_scientist)" title="Peter Sanders (computer scientist)">Sanders, Peter</A> (2008). <A rel="nofollow" class="external text" href="http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/SortedSequences.pdf"><I>Algorithms and Data Structures: The Basic Toolbox</I></A> <SPAN style="font-size:85%;">(PDF)</SPAN>. Springer, Berlin/Heidelberg. pp. 154–165. <A href="/wiki/Digital_object_identifier" title="Digital object identifier">doi</A>:<A rel="nofollow" class="external text" href="//doi.org/10.1007%2F978-3-540-77978-0">10.1007/978-3-540-77978-0</A>. <A href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</A> <A href="/wiki/Special:BookSources/978-3-540-77977-3" title="Special:BookSources/978-3-540-77977-3">978-3-540-77977-3</A>.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Algorithms+and+Data+Structures%3A+The+Basic+Toolbox&rft.pages=154-165&rft.pub=Springer%2C+Berlin%2FHeidelberg&rft.date=2008&rft_id=info%3Adoi%2F10.1007%2F978-3-540-77978-0&rft.isbn=978-3-540-77977-3&rft.aulast=Mehlhorn&rft.aufirst=Kurt&rft.au=Sanders%2C+Peter&rft_id=http%3A%2F%2Fpeople.mpi-inf.mpg.de%2F~mehlhorn%2Fftp%2FToolbox%2FSortedSequences.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN> p. 155.</SPAN></LI>
<LI id="cite_note-19"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-19"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation book">Sedgewick, Robert (1998). <I>Algorithms in C++</I>. Addison-Wesley Professional. pp. 565–575. <A href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</A> <A href="/wiki/Special:BookSources/978-0201350883" title="Special:BookSources/978-0201350883">978-0201350883</A>.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Algorithms+in+C%2B%2B&rft.pages=565-575&rft.pub=Addison-Wesley+Professional&rft.date=1998&rft.isbn=978-0201350883&rft.aulast=Sedgewick&rft.aufirst=Robert&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-20"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-20"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><A href="#Pfaff2004">Pfaff 2004</A></SPAN></LI>
<LI id="cite_note-cs.princeton.edu-21"><SPAN class="mw-cite-backlink">^ <A href="#cite_ref-cs.princeton.edu_21-0"><SPAN class="cite-accessibility-label">Jump up to: </SPAN><SUP><I><B>a</B></I></SUP></A> <A href="#cite_ref-cs.princeton.edu_21-1"><SUP><I><B>b</B></I></SUP></A></SPAN> <SPAN class="reference-text"><A rel="nofollow" class="external free" href="http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf">http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf</A></SPAN></LI>
<LI id="cite_note-22"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-22"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><A rel="nofollow" class="external free" href="http://www.cs.princeton.edu/courses/archive/fall08/cos226/lectures/10BalancedTrees-2x2.pdf">http://www.cs.princeton.edu/courses/archive/fall08/cos226/lectures/10BalancedTrees-2x2.pdf</A></SPAN></LI>
<LI id="cite_note-DHIP-23"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-DHIP_23-0"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation journal">Demaine, E. D.; Harmon, D.; Iacono, J.; Pătraşcu, M. (2007). <A rel="nofollow" class="external text" href="http://erikdemaine.org/papers/Tango_SICOMP/paper.pdf">"Dynamic Optimality—Almost"</A> <SPAN style="font-size:85%;">(PDF)</SPAN>. <I>SIAM Journal on Computing</I>. <B>37</B> (1): 240. <A href="/wiki/Digital_object_identifier" title="Digital object identifier">doi</A>:<A rel="nofollow" class="external text" href="//doi.org/10.1137%2FS0097539705447347">10.1137/S0097539705447347</A>.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=Dynamic+Optimality%E2%80%94Almost&rft.volume=37&rft.issue=1&rft.pages=240&rft.date=2007&rft_id=info%3Adoi%2F10.1137%2FS0097539705447347&rft.aulast=Demaine&rft.aufirst=E.+D.&rft.au=Harmon%2C+D.&rft.au=Iacono%2C+J.&rft.au=P%C4%83tra%C5%9Fcu%2C+M.&rft_id=http%3A%2F%2Ferikdemaine.org%2Fpapers%2FTango_SICOMP%2Fpaper.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-24"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-24"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation web"><A rel="nofollow" class="external text" href="http://coding-geek.com/how-does-a-hashmap-work-in-java/#JAVA_8_improvements">"How does a HashMap work in JAVA"</A>. coding-geek.com.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=How+does+a+HashMap+work+in+JAVA&rft.pub=coding-geek.com&rft_id=http%3A%2F%2Fcoding-geek.com%2Fhow-does-a-hashmap-work-in-java%2F%23JAVA_8_improvements&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-25"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-25"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><A href="#CITEREFMehlhornSanders2008">Mehlhorn & Sanders 2008</A>, pp. 165, 158</SPAN></LI>
<LI id="cite_note-join-based-26"><SPAN class="mw-cite-backlink">^ <A href="#cite_ref-join-based_26-0"><SPAN class="cite-accessibility-label">Jump up to: </SPAN><SUP><I><B>a</B></I></SUP></A> <A href="#cite_ref-join-based_26-1"><SUP><I><B>b</B></I></SUP></A></SPAN> <SPAN class="reference-text"><CITE id="CITEREFBlellochFerizovicSun2016" class="citation">Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets", <A rel="nofollow" class="external text" href="http://arxiv.org/pdf/1602.02120"><I>Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016)</I></A>, ACM, pp. 253–264, <A href="/wiki/Digital_object_identifier" title="Digital object identifier">doi</A>:<A rel="nofollow" class="external text" href="//doi.org/10.1145%2F2935764.2935768">10.1145/2935764.2935768</A>, <A href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</A> <A href="/wiki/Special:BookSources/978-1-4503-4210-0" title="Special:BookSources/978-1-4503-4210-0">978-1-4503-4210-0</A></CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Just+Join+for+Parallel+Ordered+Sets&rft.btitle=Symposium+on+Parallel+Algorithms+and+Architectures%2C+Proc.+of+28th+ACM+Symp.+Parallel+Algorithms+and+Architectures+%28SPAA+2016%29&rft.pages=253-264&rft.pub=ACM&rft.date=2016&rft_id=info%3Adoi%2F10.1145%2F2935764.2935768&rft.isbn=978-1-4503-4210-0&rft.aulast=Blelloch&rft.aufirst=Guy+E.&rft.au=Ferizovic%2C+Daniel&rft.au=Sun%2C+Yihan&rft_id=http%3A%2F%2Farxiv.org%2Fpdf%2F1602.02120&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN>.</SPAN></LI>
<LI id="cite_note-27"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-27"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation journal">Park, Heejin; Park, Kunsoo (2001). <A rel="nofollow" class="external text" href="http://www.sciencedirect.com/science/article/pii/S0304397500002875">"Parallel algorithms for red–black trees"</A>. <I>Theoretical computer science</I>. Elsevier. <B>262</B> (1–2): 415–435. <A href="/wiki/Digital_object_identifier" title="Digital object identifier">doi</A>:<A rel="nofollow" class="external text" href="//doi.org/10.1016%2FS0304-3975%2800%2900287-5">10.1016/S0304-3975(00)00287-5</A>. <Q>Our parallel algorithm for constructing a red–black tree from a sorted list of <I>n</I> items runs in <SPAN class="texhtml">O(1)</SPAN> time with <I>n</I> processors on the CRCW PRAM and runs in <SPAN class="texhtml">O(log log <I>n</I>)</SPAN> time with <I>n</I> / log log <I>n</I> processors on the EREW PRAM.</Q></CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Theoretical+computer+science&rft.atitle=Parallel+algorithms+for+red%E2%80%93black+trees&rft.volume=262&rft.issue=1%E2%80%932&rft.pages=415-435&rft.date=2001&rft_id=info%3Adoi%2F10.1016%2FS0304-3975%2800%2900287-5&rft.aulast=Park&rft.aufirst=Heejin&rft.au=Park%2C+Kunsoo&rft_id=http%3A%2F%2Fwww.sciencedirect.com%2Fscience%2Farticle%2Fpii%2FS0304397500002875&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-28"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-28"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation episode"><I><A href="/wiki/Missing_(Canadian_TV_series)" title="Missing (Canadian TV series)">Missing (Canadian TV series)</A></I>. <A href="/wiki/A_(TV_system)" class="mw-redirect" title="A (TV system)">A</A>, <A href="/wiki/W_Network" title="W Network">W Network</A> (Canada); <A href="/wiki/Lifetime_Television" class="mw-redirect" title="Lifetime Television">Lifetime</A> (United States).</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Missing+%28Canadian+TV+series%29&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
<LI id="cite_note-29"><SPAN class="mw-cite-backlink"><B><A href="#cite_ref-29"><SPAN class="cite-accessibility-label">Jump up </SPAN>^</A></B></SPAN> <SPAN class="reference-text"><CITE class="citation audio-visual"><A href="/wiki/Robert_Sedgewick_(computer_scientist)" title="Robert Sedgewick (computer scientist)">Robert Sedgewick</A> (2012). <A rel="nofollow" class="external text" href="https://www.coursera.org/learn/introduction-to-algorithms/lecture/HIlHd/b-trees-optional"><I>B-Trees</I></A>. <A href="/wiki/Coursera" title="Coursera">Coursera</A>. 10:37 minutes in. <Q>So not only is there some excitement in that dialogue but it's also technically correct which you don't often find with math in popular culture of computer science. A red black tree tracks every simple path from a node to a descendant leaf with the same number of black nodes they got that right.</Q></CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=B-Trees&rft.pub=Coursera&rft.date=2012&rft_id=https%3A%2F%2Fwww.coursera.org%2Flearn%2Fintroduction-to-algorithms%2Flecture%2FHIlHd%2Fb-trees-optional&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></SPAN></LI>
</OL>
</DIV>
<H2><SPAN class="mw-headline" id="Further_reading">Further reading</SPAN><SPAN class="mw-editsection"><SPAN class="mw-editsection-bracket">[</SPAN><A href="/w/index.php?title=Red%E2%80%93black_tree&action=edit&section=15" title="Edit section: Further reading">edit</A><SPAN class="mw-editsection-bracket">]</SPAN></SPAN></H2>
<UL>
<LI><A rel="nofollow" class="external text" href="http://mathworld.wolfram.com/Red-BlackTree.html">Mathworld: Red–Black Tree</A></LI>
<LI><A rel="nofollow" class="external text" href="http://www.eli.sdsu.edu/courses/fall95/cs660/notes/RedBlackTree/RedBlack.html#RTFToC2">San Diego State University: CS 660: Red–Black tree notes</A>, by Roger Whitney</LI>
<LI><SPAN id="Pfaff2004"></SPAN> <CITE class="citation web">Pfaff, Ben (June 2004). <A rel="nofollow" class="external text" href="http://www.stanford.edu/~blp/papers/libavl.pdf">"Performance Analysis of BSTs in System Software"</A> <SPAN style="font-size:85%;">(PDF)</SPAN>. <A href="/wiki/Stanford_university" class="mw-redirect" title="Stanford university">Stanford University</A>.</CITE><SPAN title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Performance+Analysis+of+BSTs+in+System+Software&rft.pub=Stanford+University&rft.date=2004-06&rft.aulast=Pfaff&rft.aufirst=Ben&rft_id=http%3A%2F%2Fwww.stanford.edu%2F~blp%2Fpapers%2Flibavl.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ARed%E2%80%93black+tree" class="Z3988"><SPAN style="display:none;"> </SPAN></SPAN></LI>
</UL>
<H2><SPAN class="mw-headline" id="External_links">External links</SPAN><SPAN class="mw-editsection"><SPAN class="mw-editsection-bracket">[</SPAN><A href="/w/index.php?title=Red%E2%80%93black_tree&action=edit&section=16" title="Edit section: External links">edit</A><SPAN class="mw-editsection-bracket">]</SPAN></SPAN></H2>
<UL>
<LI><A rel="nofollow" class="external text" href="http://en.literateprograms.org/Red-black_tree_(C)">A complete and working implementation in C</A><SUP class="noprint Inline-Template"><SPAN style="white-space: nowrap;">[<I><A href="/wiki/Wikipedia:Link_rot" title="Wikipedia:Link rot"><SPAN title=" Dead link since September 2017">dead link</SPAN></A></I>]</SPAN></SUP></LI>
<LI><A rel="nofollow" class="external text" href="http://www.ece.uc.edu/~franco/C321/html/RedBlack/redblack.html">Red–Black Tree Demonstration</A></LI>
<LI><A rel="nofollow" class="external text" href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-10-red-black-trees-rotations-insertions-deletions/">OCW MIT Lecture by Prof.</A> <A href="/wiki/Erik_Demaine" title="Erik Demaine">Erik Demaine</A> on Red Black Trees -</LI>
<LI><A rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=_VbTnLV8plU"><SPAN class="plainlinks">Binary Search Tree Insertion Visualization</SPAN></A> on <A href="/wiki/YouTube" title="YouTube">YouTube</A> – Visualization of random and pre-sorted data insertions, in elementary binary search trees, and left-leaning red–black trees</LI>
<LI><A rel="nofollow" class="external text" href="https://gist.github.com/pallas/10697727">An intrusive red-black tree written in C++</A></LI>
<LI>Red-black BSTs in <A rel="nofollow" class="external text" href="https://algs4.cs.princeton.edu/33balanced/">3.3 Balanced Search Trees</A></LI>
<LI><A rel="nofollow" class="external text" href="http://algs4.cs.princeton.edu/lectures/33DemoRedBlackBST.mov">Red–black BST Demo</A></LI>
</UL>
<DIV role="navigation" class="navbox" aria-labelledby="Tree_data_structures" style="padding:3px">
<TABLE class="nowraplinks collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit" id="collapsibleTable0">
<TBODY><TR>
<TH scope="col" class="navbox-title" colspan="2"><SPAN class="collapseButton">[<A id="collapseButton0" href="#">show</A>]</SPAN>
<DIV class="plainlinks hlist navbar mini">
<UL>
<LI class="nv-view"><A href="/wiki/Template:CS_trees" title="Template:CS trees"><ABBR title="View this template" style=";;background:none transparent;border:none;-moz-box-shadow:none;-webkit-box-shadow:none;box-shadow:none;">v</ABBR></A></LI>
<LI class="nv-talk"><A href="/wiki/Template_talk:CS_trees" title="Template talk:CS trees"><ABBR title="Discuss this template" style=";;background:none transparent;border:none;-moz-box-shadow:none;-webkit-box-shadow:none;box-shadow:none;">t</ABBR></A></LI>
<LI class="nv-edit"><A class="external text" href="//en.wikipedia.org/w/index.php?title=Template:CS_trees&action=edit"><ABBR title="Edit this template" style=";;background:none transparent;border:none;-moz-box-shadow:none;-webkit-box-shadow:none;box-shadow:none;">e</ABBR></A></LI>
</UL>
</DIV>
<DIV id="Tree_data_structures" style="font-size:114%;margin:0 4em"><A href="/wiki/Tree_(data_structure)" title="Tree (data structure)">Tree data structures</A></DIV>
</TH>
</TR>
<TR style="display: none;">
<TH scope="row" class="navbox-group" style="width:1%"><A href="/wiki/Search_tree" title="Search tree">Search trees</A><BR />
(<A href="/wiki/Set_(abstract_data_type)" title="Set (abstract data type)">dynamic sets</A>/<A href="/wiki/Associative_array" title="Associative array">associative arrays</A>)</TH>
<TD class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px">
<DIV style="padding:0em 0.25em">
<UL>
<LI><A href="/wiki/2%E2%80%933_tree" title="2–3 tree">2–3</A></LI>
<LI><A href="/wiki/2%E2%80%933%E2%80%934_tree" title="2–3–4 tree">2–3–4</A></LI>
<LI><A href="/wiki/AA_tree" title="AA tree">AA</A></LI>
<LI><A href="/wiki/(a,b)-tree" title="(a,b)-tree">(a,b)</A></LI>
<LI><A href="/wiki/AVL_tree" title="AVL tree">AVL</A></LI>
<LI><A href="/wiki/B-tree" title="B-tree">B</A></LI>
<LI><A href="/wiki/B%2B_tree" title="B+ tree">B+</A></LI>
<LI><A href="/wiki/B*-tree" class="mw-redirect" title="B*-tree">B*</A></LI>
<LI><A href="/wiki/Bx-tree" title="Bx-tree">B<SUP>x</SUP></A></LI>
<LI>(<A href="/wiki/Optimal_binary_search_tree" title="Optimal binary search tree">Optimal</A>) <A href="/wiki/Binary_search_tree" title="Binary search tree">Binary search</A></LI>
<LI><A href="/wiki/Dancing_tree" title="Dancing tree">Dancing</A></LI>
<LI><A href="/wiki/HTree" title="HTree">HTree</A></LI>
<LI><A href="/wiki/Interval_tree" title="Interval tree">Interval</A></LI>
<LI><A href="/wiki/Order_statistic_tree" title="Order statistic tree">Order statistic</A></LI>
<LI>(<A href="/wiki/Left-leaning_red%E2%80%93black_tree" title="Left-leaning red–black tree">Left-leaning</A>) <A class="mw-selflink selflink">Red-black</A></LI>
<LI><A href="/wiki/Scapegoat_tree" title="Scapegoat tree">Scapegoat</A></LI>
<LI><A href="/wiki/Splay_tree" title="Splay tree">Splay</A></LI>
<LI><A href="/wiki/T-tree" title="T-tree">T</A></LI>
<LI><A href="/wiki/Treap" title="Treap">Treap</A></LI>
<LI><A href="/wiki/UB-tree" title="UB-tree">UB</A></LI>
<LI><A href="/wiki/Weight-balanced_tree" title="Weight-balanced tree">Weight-balanced</A></LI>
</UL>
</DIV>
</TD>
</TR>
<TR style="display: none;">
<TH scope="row" class="navbox-group" style="width:1%"><A href="/wiki/Heap_(data_structure)" title="Heap (data structure)">Heaps</A></TH>
<TD class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px">
<DIV style="padding:0em 0.25em">
<UL>
<LI><A href="/wiki/Binary_heap" title="Binary heap">Binary</A></LI>
<LI><A href="/wiki/Binomial_heap" title="Binomial heap">Binomial</A></LI>
<LI><A href="/wiki/Brodal_queue" title="Brodal queue">Brodal</A></LI>
<LI><A href="/wiki/Fibonacci_heap" title="Fibonacci heap">Fibonacci</A></LI>
<LI><A href="/wiki/Leftist_tree" title="Leftist tree">Leftist</A></LI>
<LI><A href="/wiki/Pairing_heap" title="Pairing heap">Pairing</A></LI>
<LI><A href="/wiki/Skew_heap" title="Skew heap">Skew</A></LI>
<LI><A href="/wiki/Van_Emde_Boas_tree" title="Van Emde Boas tree">Van Emde Boas</A></LI>
<LI><A href="/wiki/Weak_heap" title="Weak heap">Weak</A></LI>
</UL>
</DIV>
</TD>
</TR>
<TR style="display: none;">
<TH scope="row" class="navbox-group" style="width:1%"><A href="/wiki/Trie" title="Trie">Tries</A></TH>
<TD class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px">
<DIV style="padding:0em 0.25em">
<UL>
<LI><A href="/wiki/Ctrie" title="Ctrie">Ctrie</A></LI>
<LI><A href="/wiki/C-trie" title="C-trie">C-trie (compressed ADT)</A></LI>
<LI><A href="/wiki/Hash_tree_(persistent_data_structure)" title="Hash tree (persistent data structure)">Hash</A></LI>
<LI><A href="/wiki/Radix_tree" title="Radix tree">Radix</A></LI>
<LI><A href="/wiki/Suffix_tree" title="Suffix tree">Suffix</A></LI>
<LI><A href="/wiki/Ternary_search_tree" title="Ternary search tree">Ternary search</A></LI>
<LI><A href="/wiki/X-fast_trie" title="X-fast trie">X-fast</A></LI>
<LI><A href="/wiki/Y-fast_trie" title="Y-fast trie">Y-fast</A></LI>
</UL>
</DIV>
</TD>
</TR>
<TR style="display: none;">
<TH scope="row" class="navbox-group" style="width:1%"><A href="/wiki/Spatial_index" class="mw-redirect" title="Spatial index">Spatial</A> data partitioning trees</TH>
<TD class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px">
<DIV style="padding:0em 0.25em">
<UL>
<LI><A href="/wiki/Ball_tree" title="Ball tree">Ball</A></LI>
<LI><A href="/wiki/BK-tree" title="BK-tree">BK</A></LI>
<LI><A href="/wiki/BSP_tree" class="mw-redirect" title="BSP tree">BSP</A></LI>
<LI><A href="/wiki/Cartesian_tree" title="Cartesian tree">Cartesian</A></LI>
<LI><A href="/wiki/Hilbert_R-tree" title="Hilbert R-tree">Hilbert R</A></LI>
<LI><A href="/wiki/K-d_tree" title="K-d tree"><I>k</I>-d</A> (<A href="/wiki/Implicit_k-d_tree" title="Implicit k-d tree">implicit <I>k</I>-d</A>)</LI>
<LI><A href="/wiki/M-tree" title="M-tree">M</A></LI>
<LI><A href="/wiki/Metric_tree" title="Metric tree">Metric</A></LI>
<LI><A href="/wiki/MVP_tree" class="mw-redirect" title="MVP tree">MVP</A></LI>
<LI><A href="/wiki/Octree" title="Octree">Octree</A></LI>
<LI><A href="/wiki/Priority_R-tree" title="Priority R-tree">Priority R</A></LI>
<LI><A href="/wiki/Quadtree" title="Quadtree">Quad</A></LI>
<LI><A href="/wiki/R-tree" title="R-tree">R</A></LI>
<LI><A href="/wiki/R%2B_tree" title="R+ tree">R+</A></LI>
<LI><A href="/wiki/R*_tree" title="R* tree">R*</A></LI>
<LI><A href="/wiki/Segment_tree" title="Segment tree">Segment</A></LI>
<LI><A href="/wiki/Vantage-point_tree" title="Vantage-point tree">VP</A></LI>
<LI><A href="/wiki/X-tree" title="X-tree">X</A></LI>
</UL>
</DIV>
</TD>
</TR>
<TR style="display: none;">
<TH scope="row" class="navbox-group" style="width:1%">Other trees</TH>
<TD class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px">
<DIV style="padding:0em 0.25em">
<UL>
<LI><A href="/wiki/Cover_tree" title="Cover tree">Cover</A></LI>
<LI><A href="/wiki/Exponential_tree" title="Exponential tree">Exponential</A></LI>
<LI><A href="/wiki/Fenwick_tree" title="Fenwick tree">Fenwick</A></LI>
<LI><A href="/wiki/Finger_tree" title="Finger tree">Finger</A></LI>
<LI><A href="/wiki/Fractal_tree_index" title="Fractal tree index">Fractal tree index</A></LI>
<LI><A href="/wiki/Fusion_tree" title="Fusion tree">Fusion</A></LI>
<LI><A href="/wiki/Hash_calendar" title="Hash calendar">Hash calendar</A></LI>
<LI><A href="/wiki/IDistance" title="IDistance">iDistance</A></LI>
<LI><A href="/wiki/K-ary_tree" title="K-ary tree">K-ary</A></LI>
<LI><A href="/wiki/Left-child_right-sibling_binary_tree" title="Left-child right-sibling binary tree">Left-child right-sibling</A></LI>
<LI><A href="/wiki/Link/cut_tree" title="Link/cut tree">Link/cut</A></LI>
<LI><A href="/wiki/Log-structured_merge-tree" title="Log-structured merge-tree">Log-structured merge</A></LI>
<LI><A href="/wiki/Merkle_tree" title="Merkle tree">Merkle</A></LI>
<LI><A href="/wiki/PQ_tree" title="PQ tree">PQ</A></LI>
<LI><A href="/wiki/Range_tree" title="Range tree">Range</A></LI>
<LI><A href="/wiki/SPQR_tree" title="SPQR tree">SPQR</A></LI>
<LI><A href="/wiki/Top_tree" title="Top tree">Top</A></LI>
</UL>
</DIV>
</TD>
</TR>
</TBODY></TABLE>
</DIV>
<DIV role="navigation" class="navbox" aria-labelledby="Data_structures" style="padding:3px">
<TABLE class="nowraplinks hlist collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit" id="collapsibleTable1">
<TBODY><TR>
<TH scope="col" class="navbox-title" colspan="2"><SPAN class="collapseButton">[<A id="collapseButton1" href="#">show</A>]</SPAN>
<DIV class="plainlinks hlist navbar mini">
<UL>
<LI class="nv-view"><A href="/wiki/Template:Data_structures" title="Template:Data structures"><ABBR title="View this template" style=";;background:none transparent;border:none;-moz-box-shadow:none;-webkit-box-shadow:none;box-shadow:none;">v</ABBR></A></LI>
<LI class="nv-talk"><A href="/wiki/Template_talk:Data_structures" title="Template talk:Data structures"><ABBR title="Discuss this template" style=";;background:none transparent;border:none;-moz-box-shadow:none;-webkit-box-shadow:none;box-shadow:none;">t</ABBR></A></LI>
<LI class="nv-edit"><A class="external text" href="//en.wikipedia.org/w/index.php?title=Template:Data_structures&action=edit"><ABBR title="Edit this template" style=";;background:none transparent;border:none;-moz-box-shadow:none;-webkit-box-shadow:none;box-shadow:none;">e</ABBR></A></LI>
</UL>
</DIV>
<DIV id="Data_structures" style="font-size:114%;margin:0 4em"><A href="/wiki/Data_structure" title="Data structure">Data structures</A></DIV>
</TH>
</TR>
<TR style="display: none;">
<TH scope="row" class="navbox-group" style="width:1%">Types</TH>
<TD class="navbox-list navbox-odd" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px">
<DIV style="padding:0em 0.25em">
<UL>
<LI><A href="/wiki/Collection_(abstract_data_type)" title="Collection (abstract data type)">Collection</A></LI>
<LI><A href="/wiki/Container_(abstract_data_type)" title="Container (abstract data type)">Container</A></LI>
</UL>
</DIV>
</TD>
</TR>
<TR style="display: none;">
<TH scope="row" class="navbox-group" style="width:1%"><A href="/wiki/Abstract_data_type" title="Abstract data type">Abstract</A></TH>
<TD class="navbox-list navbox-even" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px">
<DIV style="padding:0em 0.25em">
<UL>
<LI><A href="/wiki/Associative_array" title="Associative array">Associative array</A>
<UL>
<LI><A href="/wiki/Multimap" title="Multimap">Multimap</A></LI>
</UL>
</LI>
<LI><A href="/wiki/List_(abstract_data_type)" title="List (abstract data type)">List</A></LI>
<LI><A href="/wiki/Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</A></LI>
<LI><A href="/wiki/Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</A>
<UL>
<LI><A href="/wiki/Double-ended_queue" title="Double-ended queue">Double-ended queue</A></LI>
</UL>
</LI>
<LI><A href="/wiki/Priority_queue" title="Priority queue">Priority queue</A>
<UL>
<LI><A href="/wiki/Double-ended_priority_queue" title="Double-ended priority queue">Double-ended priority queue</A></LI>
</UL>
</LI>
<LI><A href="/wiki/Set_(abstract_data_type)" title="Set (abstract data type)">Set</A>
<UL>
<LI><A href="/wiki/Set_(abstract_data_type)#Multiset" title="Set (abstract data type)">Multiset</A></LI>
<LI><A href="/wiki/Disjoint-set_data_structure" title="Disjoint-set data structure">Disjoint-set</A></LI>
</UL>
</LI>
</UL>
</DIV>
</TD>
</TR>
<TR style="display: none;">
<TH scope="row" class="navbox-group" style="width:1%"><A href="/wiki/Array_data_structure" title="Array data structure">Arrays</A></TH>
<TD class="navbox-list navbox-odd" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px">
<DIV style="padding:0em 0.25em">
<UL>
<LI><A href="/wiki/Bit_array" title="Bit array">Bit array</A></LI>
<LI><A href="/wiki/Circular_buffer" title="Circular buffer">Circular buffer</A></LI>
<LI><A href="/wiki/Dynamic_array" title="Dynamic array">Dynamic array</A></LI>
<LI><A href="/wiki/Hash_table" title="Hash table">Hash table</A></LI>
<LI><A href="/wiki/Hashed_array_tree" title="Hashed array tree">Hashed array tree</A></LI>
<LI><A href="/wiki/Sparse_matrix" title="Sparse matrix">Sparse matrix</A></LI>
</UL>
</DIV>
</TD>
</TR>
<TR style="display: none;">
<TH scope="row" class="navbox-group" style="width:1%"><A href="/wiki/Linked_data_structure" title="Linked data structure">Linked</A></TH>
<TD class="navbox-list navbox-even" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px">
<DIV style="padding:0em 0.25em">
<UL>
<LI><A href="/wiki/Association_list" title="Association list">Association list</A></LI>
<LI><A href="/wiki/Linked_list" title="Linked list">Linked list</A></LI>
<LI><A href="/wiki/Skip_list" title="Skip list">Skip list</A></LI>
<LI><A href="/wiki/Unrolled_linked_list" title="Unrolled linked list">Unrolled linked list</A></LI>
<LI><A href="/wiki/XOR_linked_list" title="XOR linked list">XOR linked list</A></LI>
</UL>
</DIV>
</TD>
</TR>
<TR style="display: none;">
<TH scope="row" class="navbox-group" style="width:1%"><A href="/wiki/Tree_(data_structure)" title="Tree (data structure)">Trees</A></TH>
<TD class="navbox-list navbox-odd" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px">
<DIV style="padding:0em 0.25em">
<UL>
<LI><A href="/wiki/B-tree" title="B-tree">B-tree</A></LI>
<LI><A href="/wiki/Binary_search_tree" title="Binary search tree">Binary search tree</A>
<UL>
<LI><A href="/wiki/AA_tree" title="AA tree">AA tree</A></LI>
<LI><A href="/wiki/AVL_tree" title="AVL tree">AVL tree</A></LI>
<LI><A class="mw-selflink selflink">Red–black tree</A></LI>
<LI><A href="/wiki/Self-balancing_binary_search_tree" title="Self-balancing binary search tree">Self-balancing tree</A></LI>
<LI><A href="/wiki/Splay_tree" title="Splay tree">Splay tree</A></LI>
</UL>
</LI>
<LI><A href="/wiki/Heap_(data_structure)" title="Heap (data structure)">Heap</A>
<UL>
<LI><A href="/wiki/Binary_heap" title="Binary heap">Binary heap</A></LI>
<LI><A href="/wiki/Binomial_heap" title="Binomial heap">Binomial heap</A></LI>
<LI><A href="/wiki/Fibonacci_heap" title="Fibonacci heap">Fibonacci heap</A></LI>
</UL>
</LI>
<LI><A href="/wiki/R-tree" title="R-tree">R-tree</A>
<UL>
<LI><A href="/wiki/R*_tree" title="R* tree">R* tree</A></LI>
<LI><A href="/wiki/R%2B_tree" title="R+ tree">R+ tree</A></LI>
<LI><A href="/wiki/Hilbert_R-tree" title="Hilbert R-tree">Hilbert R-tree</A></LI>
</UL>
</LI>
<LI><A href="/wiki/Trie" title="Trie">Trie</A>
<UL>
<LI><A href="/wiki/Hash_tree_(persistent_data_structure)" title="Hash tree (persistent data structure)">Hash tree</A></LI>
</UL>
</LI>
</UL>
</DIV>
</TD>
</TR>
<TR style="display: none;">
<TH scope="row" class="navbox-group" style="width:1%"><A href="/wiki/Graph_(abstract_data_type)" title="Graph (abstract data type)">Graphs</A></TH>
<TD class="navbox-list navbox-even" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px">
<DIV style="padding:0em 0.25em">
<UL>
<LI><A href="/wiki/Binary_decision_diagram" title="Binary decision diagram">Binary decision diagram</A></LI>
<LI><A href="/wiki/Directed_acyclic_graph" title="Directed acyclic graph">Directed acyclic graph</A></LI>
<LI><A href="/wiki/Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">Directed acyclic word graph</A></LI>
</UL>
</DIV>
</TD>
</TR>
<TR style="display: none;">
<TD class="navbox-abovebelow" colspan="2">
<DIV>
<UL>
<LI><A href="/wiki/List_of_data_structures" title="List of data structures">List of data structures</A></LI>
</UL>
</DIV>
</TD>
</TR>
</TBODY></TABLE>
</DIV>

<!--
NewPP limit report
Parsed by mw1288
Cached time: 20180102164025
Cache expiry: 1900800
Dynamic content: false
CPU time usage: 0.420 seconds
Real time usage: 0.595 seconds
Preprocessor visited node count: 3363/1000000
Preprocessor generated node count: 0/1500000
Post‐expand include size: 85919/2097152 bytes
Template argument size: 3512/2097152 bytes
Highest expansion depth: 11/40
Expensive parser function count: 1/500
Lua time usage: 0.159/10.000 seconds
Lua memory usage: 4.59 MB/50 MB
-->
<!--
Transclusion expansion time report (%,ms,calls,template)
100.00%  367.671      1 -total
 45.19%  166.153      2 Template:Reflist
 13.39%   49.219      1 Template:Infobox_data_structure
 12.72%   46.785      1 Template:Citequote
 12.59%   46.280      1 Template:Infobox
 12.51%   46.012      6 Template:Cite_web
 11.96%   43.979      2 Template:Fix
  8.29%   30.489      4 Template:Category_handler
  8.15%   29.948      7 Template:Cite_book
  7.65%   28.123      6 Template:Cite_journal
-->
</DIV>
<!-- Saved in parser cache with key enwiki:pcache:idhash:26397-0!canonical!math=5 and timestamp 20180102164041 and revision id 818272029
 -->
<NOSCRIPT><img src="//en.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;" /></NOSCRIPT></DIV>					<DIV class="printfooter">
						Retrieved from "<A dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Red–black_tree&oldid=818272029">https://en.wikipedia.org/w/index.php?title=Red–black_tree&oldid=818272029</A>"					</DIV>
				<DIV id="catlinks" class="catlinks" data-mw="interface"><DIV id="mw-normal-catlinks" class="mw-normal-catlinks"><A href="/wiki/Help:Category" title="Help:Category">Categories</A>: <UL><LI><A href="/wiki/Category:1972_in_computer_science" title="Category:1972 in computer science">1972 in computer science</A></LI><LI><A href="/wiki/Category:Binary_trees" title="Category:Binary trees">Binary trees</A></LI><LI><A href="/wiki/Category:Search_trees" title="Category:Search trees">Search trees</A></LI></UL></DIV><DIV id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <UL><LI><A href="/wiki/Category:Articles_with_unsourced_quotes" title="Category:Articles with unsourced quotes">Articles with unsourced quotes</A></LI><LI><A href="/wiki/Category:All_articles_with_dead_external_links" title="Category:All articles with dead external links">All articles with dead external links</A></LI><LI><A href="/wiki/Category:Articles_with_dead_external_links_from_September_2017" title="Category:Articles with dead external links from September 2017">Articles with dead external links from September 2017</A></LI><LI><A href="/wiki/Category:Articles_containing_proofs" title="Category:Articles containing proofs">Articles containing proofs</A></LI><LI><A href="/wiki/Category:Articles_with_example_C_code" title="Category:Articles with example C code">Articles with example C code</A></LI></UL></DIV></DIV>				<DIV class="visualClear"></DIV>
							</DIV>
		</DIV>
		<DIV id="mw-navigation">
			<H2>Navigation menu</H2>
			<DIV id="mw-head">
									<DIV id="p-personal" role="navigation" class="" aria-labelledby="p-personal-label">
						<H3 id="p-personal-label">Personal tools</H3>
						<UL>
							<LI id="pt-anonuserpage">Not logged in</LI><LI id="pt-anontalk"><A href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [ctrl-alt-n]" accesskey="n">Talk</A></LI><LI id="pt-anoncontribs"><A href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [ctrl-alt-y]" accesskey="y">Contributions</A></LI><LI id="pt-createaccount"><A href="/w/index.php?title=Special:CreateAccount&returnto=Red%E2%80%93black+tree" title="You are encouraged to create an account and log in; however, it is not mandatory">Create account</A></LI><LI id="pt-login"><A href="/w/index.php?title=Special:UserLogin&returnto=Red%E2%80%93black+tree" title="You're encouraged to log in; however, it's not mandatory. [ctrl-alt-o]" accesskey="o">Log in</A></LI>						</UL>
					</DIV>
									<DIV id="left-navigation">
										<DIV id="p-namespaces" role="navigation" class="vectorTabs" aria-labelledby="p-namespaces-label">
						<H3 id="p-namespaces-label">Namespaces</H3>
						<UL>
							<LI id="ca-nstab-main" class="selected"><SPAN><A href="/wiki/Red%E2%80%93black_tree" title="View the content page [ctrl-alt-c]" accesskey="c">Article</A></SPAN></LI><LI id="ca-talk"><SPAN><A href="/wiki/Talk:Red%E2%80%93black_tree" rel="discussion" title="Discussion about the content page [ctrl-alt-t]" accesskey="t">Talk</A></SPAN></LI>						</UL>
					</DIV>
										<DIV id="p-variants" role="navigation" class="vectorMenu emptyPortlet" aria-labelledby="p-variants-label">
												<H3 id="p-variants-label" tabindex="0">
							<SPAN>Variants</SPAN>
						</H3>
						<DIV class="menu">
							<UL>
															</UL>
						</DIV>
					</DIV>
									</DIV>
				<DIV id="right-navigation">
										<DIV id="p-views" role="navigation" class="vectorTabs" aria-labelledby="p-views-label">
						<H3 id="p-views-label">Views</H3>
						<UL>
							<LI id="ca-view" class="collapsible selected"><SPAN><A href="/wiki/Red%E2%80%93black_tree">Read</A></SPAN></LI><LI id="ca-edit" class="collapsible"><SPAN><A href="/w/index.php?title=Red%E2%80%93black_tree&action=edit" title="Edit this page [ctrl-alt-e]" accesskey="e">Edit</A></SPAN></LI><LI id="ca-history" class="collapsible"><SPAN><A href="/w/index.php?title=Red%E2%80%93black_tree&action=history" title="Past revisions of this page [ctrl-alt-h]" accesskey="h">View history</A></SPAN></LI>						</UL>
					</DIV>
										<DIV id="p-cactions" role="navigation" class="vectorMenu emptyPortlet" aria-labelledby="p-cactions-label">
						<H3 id="p-cactions-label" tabindex="0"><SPAN>More</SPAN></H3>
						<DIV class="menu">
							<UL>
															</UL>
						</DIV>
					</DIV>
										<DIV id="p-search" role="search">
						<H3>
							<LABEL for="searchInput">Search</LABEL>
						</H3>
						<FORM action="/w/index.php" id="searchform">
							<DIV id="simpleSearch">
								<INPUT type="search" name="search" placeholder="Search Wikipedia" title="Search Wikipedia [ctrl-alt-f]" accesskey="f" id="searchInput" tabindex="1" autocomplete="off" /><INPUT type="hidden" value="Special:Search" name="title" /><INPUT type="submit" name="go" value="Go" title="Go to a page with this exact name if it exists" id="searchButton" class="searchButton" />							</DIV>
						</FORM>
					</DIV>
									</DIV>
			</DIV>
			<DIV id="mw-panel">
				<DIV id="p-logo" role="banner"><A class="mw-wiki-logo" href="/wiki/Main_Page" title="Visit the main page"></A></DIV>
						<DIV class="portal" role="navigation" id="p-navigation" aria-labelledby="p-navigation-label">
			<H3 id="p-navigation-label">Navigation</H3>
			<DIV class="body">
								<UL>
					<LI id="n-mainpage-description"><A href="/wiki/Main_Page" title="Visit the main page [ctrl-alt-z]" accesskey="z">Main page</A></LI><LI id="n-contents"><A href="/wiki/Portal:Contents" title="Guides to browsing Wikipedia">Contents</A></LI><LI id="n-featuredcontent"><A href="/wiki/Portal:Featured_content" title="Featured content – the best of Wikipedia">Featured content</A></LI><LI id="n-currentevents"><A href="/wiki/Portal:Current_events" title="Find background information on current events">Current events</A></LI><LI id="n-randompage"><A href="/wiki/Special:Random" title="Load a random article [ctrl-alt-x]" accesskey="x">Random article</A></LI><LI id="n-sitesupport"><A href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" title="Support us">Donate to Wikipedia</A></LI><LI id="n-shoplink"><A href="//shop.wikimedia.org" title="Visit the Wikipedia store">Wikipedia store</A></LI>				</UL>
							</DIV>
		</DIV>
			<DIV class="portal" role="navigation" id="p-interaction" aria-labelledby="p-interaction-label">
			<H3 id="p-interaction-label">Interaction</H3>
			<DIV class="body">
								<UL>
					<LI id="n-help"><A href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia">Help</A></LI><LI id="n-aboutsite"><A href="/wiki/Wikipedia:About" title="Find out about Wikipedia">About Wikipedia</A></LI><LI id="n-portal"><A href="/wiki/Wikipedia:Community_portal" title="About the project, what you can do, where to find things">Community portal</A></LI><LI id="n-recentchanges"><A href="/wiki/Special:RecentChanges" title="A list of recent changes in the wiki [ctrl-alt-r]" accesskey="r">Recent changes</A></LI><LI id="n-contactpage"><A href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia">Contact page</A></LI>				</UL>
							</DIV>
		</DIV>
			<DIV class="portal" role="navigation" id="p-tb" aria-labelledby="p-tb-label">
			<H3 id="p-tb-label">Tools</H3>
			<DIV class="body">
								<UL>
					<LI id="t-whatlinkshere"><A href="/wiki/Special:WhatLinksHere/Red%E2%80%93black_tree" title="List of all English Wikipedia pages containing links to this page [ctrl-alt-j]" accesskey="j">What links here</A></LI><LI id="t-recentchangeslinked"><A href="/wiki/Special:RecentChangesLinked/Red%E2%80%93black_tree" rel="nofollow" title="Recent changes in pages linked from this page [ctrl-alt-k]" accesskey="k">Related changes</A></LI><LI id="t-upload"><A href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [ctrl-alt-u]" accesskey="u">Upload file</A></LI><LI id="t-specialpages"><A href="/wiki/Special:SpecialPages" title="A list of all special pages [ctrl-alt-q]" accesskey="q">Special pages</A></LI><LI id="t-permalink"><A href="/w/index.php?title=Red%E2%80%93black_tree&oldid=818272029" title="Permanent link to this revision of the page">Permanent link</A></LI><LI id="t-info"><A href="/w/index.php?title=Red%E2%80%93black_tree&action=info" title="More information about this page">Page information</A></LI><LI id="t-wikibase"><A href="https://www.wikidata.org/wiki/Special:EntityPage/Q506496" title="Link to connected data repository item [ctrl-alt-g]" accesskey="g">Wikidata item</A></LI><LI id="t-cite"><A href="/w/index.php?title=Special:CiteThisPage&page=Red%E2%80%93black_tree&id=818272029" title="Information on how to cite this page">Cite this page</A></LI>				</UL>
							</DIV>
		</DIV>
			<DIV class="portal" role="navigation" id="p-coll-print_export" aria-labelledby="p-coll-print_export-label">
			<H3 id="p-coll-print_export-label">Print/export</H3>
			<DIV class="body">
								<UL>
					<LI id="coll-create_a_book"><A href="/w/index.php?title=Special:Book&bookcmd=book_creator&referer=Red%E2%80%93black+tree">Create a book</A></LI><LI id="coll-download-as-rdf2latex"><A href="/w/index.php?title=Special:ElectronPdf&page=Red%E2%80%93black+tree&action=show-download-screen">Download as PDF</A></LI><LI id="t-print"><A href="/w/index.php?title=Red%E2%80%93black_tree&printable=yes" title="Printable version of this page [ctrl-alt-p]" accesskey="p">Printable version</A></LI>				</UL>
							</DIV>
		</DIV>
			<DIV class="portal" role="navigation" id="p-wikibase-otherprojects" aria-labelledby="p-wikibase-otherprojects-label">
			<H3 id="p-wikibase-otherprojects-label">In other projects</H3>
			<DIV class="body">
								<UL>
					<LI class="wb-otherproject-link wb-otherproject-commons"><A href="https://commons.wikimedia.org/wiki/Category:Red-black_trees" hreflang="en">Wikimedia Commons</A></LI>				</UL>
							</DIV>
		</DIV>
			<DIV class="portal" role="navigation" id="p-lang" aria-labelledby="p-lang-label"><SPAN class="uls-settings-trigger" title="Language settings" tabindex="0" role="button" aria-haspopup="true"></SPAN>
			<H3 id="p-lang-label">Languages</H3>
			<DIV class="body">
								<UL>
					<LI class="interlanguage-link interwiki-az"><A href="https://az.wikipedia.org/wiki/Qara-q%C4%B1rm%C4%B1z%C4%B1_a%C4%9Fac" title="Qara-qırmızı ağac – Azerbaijani" lang="az" hreflang="az" class="interlanguage-link-target">Azərbaycanca</A></LI><LI class="interlanguage-link interwiki-zh-min-nan"><A href="https://zh-min-nan.wikipedia.org/wiki/%C3%82ng-o%CD%98-chhi%C5%AB" title="Âng-o͘-chhiū – Chinese (Min Nan)" lang="zh-min-nan" hreflang="zh-min-nan" class="interlanguage-link-target">Bân-lâm-gú</A></LI><LI class="interlanguage-link interwiki-bg"><A href="https://bg.wikipedia.org/wiki/%D0%A7%D0%B5%D1%80%D0%B2%D0%B5%D0%BD%D0%BE-%D1%87%D0%B5%D1%80%D0%BD%D0%BE_%D0%B4%D1%8A%D1%80%D0%B2%D0%BE" title="Червено-черно дърво – Bulgarian" lang="bg" hreflang="bg" class="interlanguage-link-target">Български</A></LI><LI class="interlanguage-link interwiki-cs"><A href="https://cs.wikipedia.org/wiki/%C4%8Cerveno-%C4%8Dern%C3%BD_strom" title="Červeno-černý strom – Czech" lang="cs" hreflang="cs" class="interlanguage-link-target">Čeština</A></LI><LI class="interlanguage-link interwiki-da"><A href="https://da.wikipedia.org/wiki/R%C3%B8d-sort_tr%C3%A6" title="Rød-sort træ – Danish" lang="da" hreflang="da" class="interlanguage-link-target">Dansk</A></LI><LI class="interlanguage-link interwiki-de badge-Q17437798 badge-goodarticle" title="good article"><A href="https://de.wikipedia.org/wiki/Rot-Schwarz-Baum" title="Rot-Schwarz-Baum – German" lang="de" hreflang="de" class="interlanguage-link-target">Deutsch</A></LI><LI class="interlanguage-link interwiki-es"><A href="https://es.wikipedia.org/wiki/%C3%81rbol_rojo-negro" title="Árbol rojo-negro – Spanish" lang="es" hreflang="es" class="interlanguage-link-target">Español</A></LI><LI class="interlanguage-link interwiki-fa"><A href="https://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%D8%B3%D8%B1%D8%AE-%D8%B3%DB%8C%D8%A7%D9%87" title="درخت سرخ-سیاه – Persian" lang="fa" hreflang="fa" class="interlanguage-link-target">فارسی</A></LI><LI class="interlanguage-link interwiki-fr"><A href="https://fr.wikipedia.org/wiki/Arbre_bicolore" title="Arbre bicolore – French" lang="fr" hreflang="fr" class="interlanguage-link-target">Français</A></LI><LI class="interlanguage-link interwiki-ko"><A href="https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC" title="레드-블랙 트리 – Korean" lang="ko" hreflang="ko" class="interlanguage-link-target">한국어</A></LI><LI class="interlanguage-link interwiki-hr"><A href="https://hr.wikipedia.org/wiki/Crveno-crno_stablo" title="Crveno-crno stablo – Croatian" lang="hr" hreflang="hr" class="interlanguage-link-target">Hrvatski</A></LI><LI class="interlanguage-link interwiki-id"><A href="https://id.wikipedia.org/wiki/Pohon_merah-hitam" title="Pohon merah-hitam – Indonesian" lang="id" hreflang="id" class="interlanguage-link-target">Bahasa Indonesia</A></LI><LI class="interlanguage-link interwiki-it"><A href="https://it.wikipedia.org/wiki/RB-Albero" title="RB-Albero – Italian" lang="it" hreflang="it" class="interlanguage-link-target">Italiano</A></LI><LI class="interlanguage-link interwiki-he"><A href="https://he.wikipedia.org/wiki/%D7%A2%D7%A5_%D7%90%D7%93%D7%95%D7%9D_%D7%A9%D7%97%D7%95%D7%A8" title="עץ אדום שחור – Hebrew" lang="he" hreflang="he" class="interlanguage-link-target">עברית</A></LI><LI class="interlanguage-link interwiki-lt"><A href="https://lt.wikipedia.org/wiki/Raudonai_juodas_medis" title="Raudonai juodas medis – Lithuanian" lang="lt" hreflang="lt" class="interlanguage-link-target">Lietuvių</A></LI><LI class="interlanguage-link interwiki-hu"><A href="https://hu.wikipedia.org/wiki/Piros-fekete_fa" title="Piros-fekete fa – Hungarian" lang="hu" hreflang="hu" class="interlanguage-link-target">Magyar</A></LI><LI class="interlanguage-link interwiki-nl"><A href="https://nl.wikipedia.org/wiki/Rood-zwartboom" title="Rood-zwartboom – Dutch" lang="nl" hreflang="nl" class="interlanguage-link-target">Nederlands</A></LI><LI class="interlanguage-link interwiki-ja"><A href="https://ja.wikipedia.org/wiki/%E8%B5%A4%E9%BB%92%E6%9C%A8" title="赤黒木 – Japanese" lang="ja" hreflang="ja" class="interlanguage-link-target">日本語</A></LI><LI class="interlanguage-link interwiki-no"><A href="https://no.wikipedia.org/wiki/R%C3%B8d-svart_tre" title="Rød-svart tre – Norwegian" lang="no" hreflang="no" class="interlanguage-link-target">Norsk</A></LI><LI class="interlanguage-link interwiki-pl"><A href="https://pl.wikipedia.org/wiki/Drzewo_czerwono-czarne" title="Drzewo czerwono-czarne – Polish" lang="pl" hreflang="pl" class="interlanguage-link-target">Polski</A></LI><LI class="interlanguage-link interwiki-pt"><A href="https://pt.wikipedia.org/wiki/%C3%81rvore_rubro-negra" title="Árvore rubro-negra – Portuguese" lang="pt" hreflang="pt" class="interlanguage-link-target">Português</A></LI><LI class="interlanguage-link interwiki-ru"><A href="https://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B0%D1%81%D0%BD%D0%BE-%D1%87%D1%91%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Красно-чёрное дерево – Russian" lang="ru" hreflang="ru" class="interlanguage-link-target">Русский</A></LI><LI class="interlanguage-link interwiki-sr"><A href="https://sr.wikipedia.org/wiki/%D0%A6%D1%80%D0%B2%D0%B5%D0%BD%D0%BE-%D1%86%D1%80%D0%BD%D0%BE_%D1%81%D1%82%D0%B0%D0%B1%D0%BB%D0%BE" title="Црвено-црно стабло – Serbian" lang="sr" hreflang="sr" class="interlanguage-link-target">Српски / srpski</A></LI><LI class="interlanguage-link interwiki-fi"><A href="https://fi.wikipedia.org/wiki/Punamusta_puu" title="Punamusta puu – Finnish" lang="fi" hreflang="fi" class="interlanguage-link-target">Suomi</A></LI><LI class="interlanguage-link interwiki-sv"><A href="https://sv.wikipedia.org/wiki/R%C3%B6d-svart_tr%C3%A4d" title="Röd-svart träd – Swedish" lang="sv" hreflang="sv" class="interlanguage-link-target">Svenska</A></LI><LI class="interlanguage-link interwiki-th"><A href="https://th.wikipedia.org/wiki/%E0%B8%95%E0%B9%89%E0%B8%99%E0%B9%84%E0%B8%A1%E0%B9%89%E0%B9%81%E0%B8%94%E0%B8%87%E0%B8%94%E0%B8%B3" title="ต้นไม้แดงดำ – Thai" lang="th" hreflang="th" class="interlanguage-link-target">ไทย</A></LI><LI class="interlanguage-link interwiki-tr"><A href="https://tr.wikipedia.org/wiki/K%C4%B1rm%C4%B1z%C4%B1-siyah_a%C4%9Fa%C3%A7" title="Kırmızı-siyah ağaç – Turkish" lang="tr" hreflang="tr" class="interlanguage-link-target">Türkçe</A></LI><LI class="interlanguage-link interwiki-uk"><A href="https://uk.wikipedia.org/wiki/%D0%A7%D0%B5%D1%80%D0%B2%D0%BE%D0%BD%D0%BE-%D1%87%D0%BE%D1%80%D0%BD%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Червоно-чорне дерево – Ukrainian" lang="uk" hreflang="uk" class="interlanguage-link-target">Українська</A></LI><LI class="interlanguage-link interwiki-vi"><A href="https://vi.wikipedia.org/wiki/C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en" title="Cây đỏ đen – Vietnamese" lang="vi" hreflang="vi" class="interlanguage-link-target">Tiếng Việt</A></LI><LI class="interlanguage-link interwiki-zh"><A href="https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91" title="红黑树 – Chinese" lang="zh" hreflang="zh" class="interlanguage-link-target">中文</A></LI>				</UL>
				<DIV class="after-portlet after-portlet-lang"><SPAN class="wb-langlinks-edit wb-langlinks-link"><A href="https://www.wikidata.org/wiki/Special:EntityPage/Q506496#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</A></SPAN></DIV>			</DIV>
		</DIV>
				</DIV>
		</DIV>
				<DIV id="footer" role="contentinfo">
						<UL id="footer-info">
								<LI id="footer-info-lastmod"> This page was last edited on 2 January 2018, at 16:40.</LI>
								<LI id="footer-info-copyright">Text is available under the <A rel="license" href="//en.wikipedia.org/wiki/Wikipedia:Text_of_Creative_Commons_Attribution-ShareAlike_3.0_Unported_License">Creative Commons Attribution-ShareAlike License</A><A rel="license" href="//creativecommons.org/licenses/by-sa/3.0/" style="display:none;"></A>;
additional terms may apply.  By using this site, you agree to the <A href="//wikimediafoundation.org/wiki/Terms_of_Use">Terms of Use</A> and <A href="//wikimediafoundation.org/wiki/Privacy_policy">Privacy Policy</A>. Wikipedia® is a registered trademark of the <A href="//www.wikimediafoundation.org/">Wikimedia Foundation, Inc.</A>, a non-profit organization.</LI>
							</UL>
						<UL id="footer-places">
								<LI id="footer-places-privacy"><A href="https://wikimediafoundation.org/wiki/Privacy_policy" class="extiw" title="wmf:Privacy policy">Privacy policy</A></LI>
								<LI id="footer-places-about"><A href="/wiki/Wikipedia:About" title="Wikipedia:About">About Wikipedia</A></LI>
								<LI id="footer-places-disclaimer"><A href="/wiki/Wikipedia:General_disclaimer" title="Wikipedia:General disclaimer">Disclaimers</A></LI>
								<LI id="footer-places-contact"><A href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</A></LI>
								<LI id="footer-places-developers"><A href="https://www.mediawiki.org/wiki/Special:MyLanguage/How_to_contribute">Developers</A></LI>
								<LI id="footer-places-cookiestatement"><A href="https://wikimediafoundation.org/wiki/Cookie_statement">Cookie statement</A></LI>
								<LI id="footer-places-mobileview"><A href="//en.m.wikipedia.org/w/index.php?title=Red%E2%80%93black_tree&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</A></LI>
							<LI style=""><A href="#">Enable previews</A></LI></UL>
										<UL id="footer-icons" class="noprint">
										<LI id="footer-copyrightico">
						<A href="https://wikimediafoundation.org/"><IMG src="/static/images/wikimedia-button.png" srcset="/static/images/wikimedia-button-1.5x.png 1.5x, /static/images/wikimedia-button-2x.png 2x" width="88" height="31" alt="Wikimedia Foundation" /></A>					</LI>
										<LI id="footer-poweredbyico">
						<A href="//www.mediawiki.org/"><IMG src="/static/images/poweredby_mediawiki_88x31.png" alt="Powered by MediaWiki" srcset="/static/images/poweredby_mediawiki_132x47.png 1.5x, /static/images/poweredby_mediawiki_176x62.png 2x" width="88" height="31" /></A>					</LI>
									</UL>
						<DIV style="clear: both;"></DIV>
		</DIV>

<DIV class="suggestions" style="display: none; font-size: 13px;"><DIV class="suggestions-results"></DIV><DIV class="suggestions-special"></DIV></DIV><DIV id="mwe-popups-svg"><svg width="0" height="0"><defs><clipPath id="mwe-popups-mask"><polygon points="0 8, 10 8, 18 0, 26 8, 1000 8, 1000 1000, 0 1000"></polygon></clipPath><clipPath id="mwe-popups-mask-flip"><polygon points="0 8, 274 8, 282 0, 290 8, 1000 8, 1000 1000, 0 1000"></polygon></clipPath><clipPath id="mwe-popups-landscape-mask"><polygon points="0 8, 174 8, 182 0, 190 8, 1000 8, 1000 1000, 0 1000"></polygon></clipPath><clipPath id="mwe-popups-landscape-mask-flip"><polygon points="0 0, 1000 0, 1000 242, 190 242, 182 250, 174 242, 0 242"></polygon></clipPath></defs></svg></DIV></BODY></HTML>

document_title: Red–black tree

token: Red

token: black

token: tree

token: wikipedia

token: Jump

token: to

token: navigation

token: search

token: <Table>

token: <Tr>

token: <Th colspan="2">

token: <Th>

token: Type

token: <Td>

token: Invented

token: by

token: Rudolf

token: Bayer

token: Time

token: complexity

token: in

token: big

token: O

token: notation

token: <Td colspan="2">

token: Algorithm

token: Average

token: Worst

token: case

token: Space

token: n

token: Search

token: log

token: Insert

token: Delete

question_text: properties of red black tree in data structure