{"id":27109,"date":"2019-10-10T07:57:33","date_gmt":"2019-10-10T07:57:33","guid":{"rendered":"https:\/\/www.testingdocs.com\/questions\/?p=27109"},"modified":"2025-05-17T07:14:02","modified_gmt":"2025-05-17T07:14:02","slug":"what-is-red-black-tree","status":"publish","type":"post","link":"https:\/\/www.testingdocs.com\/questions\/what-is-red-black-tree\/","title":{"rendered":"What is Red-Black Tree?"},"content":{"rendered":"<h1>Red-Black Tree<\/h1>\n<p>A Red-Black Tree is a self-balancing binary search tree (BST) where each node contains an additional bit of information to maintain balance. This ensures that the tree remains approximately balanced, resulting in efficient operations. The name &#8220;Red-Black&#8221; comes from the fact that each node is colored either red or black.<\/p>\n<h2>Properties of a Red-Black Tree<\/h2>\n<ul>\n<li>Each node is either red or black.<\/li>\n<li>The root node is always black.<\/li>\n<li>Every leaf node (NULL nodes) is black.<\/li>\n<li>If a node is red, its children must be black (no two consecutive red nodes).<\/li>\n<li>Every path from a node to its descendant NULL nodes must have the same number of black nodes.<\/li>\n<\/ul>\n<h2>Operations on Red-Black Tree<\/h2>\n<h4>Insertion<\/h4>\n<p>Insertion in a Red-Black Tree is similar to a Binary Search Tree (BST) insertion. However, after inserting a node, the tree undergoes rebalancing through recoloring and rotations to maintain its properties.<\/p>\n<h4>Deletion<\/h4>\n<p>Deletion involves removing a node like in a BST. If the deleted node is black, rebalancing is required to maintain the Red-Black Tree properties, which may involve rotations and recoloring.<\/p>\n<h4>Searching<\/h4>\n<p>Searching in a Red-Black Tree follows the same approach as in a Binary Search Tree, where we compare values to traverse the tree efficiently.<\/p>\n<h4>Rotations<\/h4>\n<p>Rotations are used to restore balance after insertion or deletion. There are two types:<\/p>\n<ul>\n<li><strong>Left Rotation:<\/strong> Moves a node down and its right child up.<\/li>\n<li><strong>Right Rotation:<\/strong> Moves a node down and its left child up.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-27118\" src=\"https:\/\/www.testingdocs.com\/questions\/wp-content\/uploads\/Red-Black-Tree.png\" alt=\"Red Black Tree\" width=\"1280\" height=\"720\" title=\"\" srcset=\"https:\/\/www.testingdocs.com\/questions\/wp-content\/uploads\/Red-Black-Tree.png 1280w, https:\/\/www.testingdocs.com\/questions\/wp-content\/uploads\/Red-Black-Tree-300x169.png 300w, https:\/\/www.testingdocs.com\/questions\/wp-content\/uploads\/Red-Black-Tree-1024x576.png 1024w, https:\/\/www.testingdocs.com\/questions\/wp-content\/uploads\/Red-Black-Tree-768x432.png 768w\" sizes=\"auto, (max-width: 1280px) 100vw, 1280px\" \/><\/p>\n<h2>Time Complexity<\/h2>\n<table border=\"1\">\n<tbody>\n<tr>\n<th>Operation<\/th>\n<th>Time Complexity (Big O Notation)<\/th>\n<\/tr>\n<tr>\n<td>Insertion<\/td>\n<td>O(log n)<\/td>\n<\/tr>\n<tr>\n<td>Deletion<\/td>\n<td>O(log n)<\/td>\n<\/tr>\n<tr>\n<td>Search<\/td>\n<td>O(log n)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h2>Examples<\/h2>\n<h4>Example 1: Inserting Nodes<\/h4>\n<p>Consider inserting the following sequence of numbers: 10, 20, 30, 15, 25.<\/p>\n<p>After each insertion, rotations and recoloring are applied to maintain balance.<\/p>\n<h4>Example 2: Deletion<\/h4>\n<p>Deleting a node may require rebalancing. If the deleted node is black, additional steps are needed to maintain the Red-Black Tree properties.<\/p>\n<p>Red-Black Trees are widely used in databases, operating systems, and language libraries due to their efficient balancing properties.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Red-Black Tree A Red-Black Tree is a self-balancing binary search tree (BST) where each node contains an additional bit of information to maintain balance. This ensures that the tree remains approximately balanced, resulting in efficient operations. The name &#8220;Red-Black&#8221; comes from the fact that each node is colored either red or black. Properties of a [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[50],"tags":[],"class_list":["post-27109","post","type-post","status-publish","format-standard","hentry","category-testing-questions","has-post-title","has-post-date","has-post-category","has-post-tag","has-post-comment","has-post-author",""],"_links":{"self":[{"href":"https:\/\/www.testingdocs.com\/questions\/wp-json\/wp\/v2\/posts\/27109","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.testingdocs.com\/questions\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.testingdocs.com\/questions\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.testingdocs.com\/questions\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.testingdocs.com\/questions\/wp-json\/wp\/v2\/comments?post=27109"}],"version-history":[{"count":10,"href":"https:\/\/www.testingdocs.com\/questions\/wp-json\/wp\/v2\/posts\/27109\/revisions"}],"predecessor-version":[{"id":27416,"href":"https:\/\/www.testingdocs.com\/questions\/wp-json\/wp\/v2\/posts\/27109\/revisions\/27416"}],"wp:attachment":[{"href":"https:\/\/www.testingdocs.com\/questions\/wp-json\/wp\/v2\/media?parent=27109"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.testingdocs.com\/questions\/wp-json\/wp\/v2\/categories?post=27109"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.testingdocs.com\/questions\/wp-json\/wp\/v2\/tags?post=27109"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}