Skip to main content

What Is Red-Black Tree

                          Red-Black Tree

What is Red-Black Tree ?

  • Red Black Tree : A Red Black Tree is a kind of Self-Balancing binary search Tree in Computer Science . 
  • Properties : 
                           1)  Root node is always Black if Root Node is red then you have to change into black.
                          2) each node either red or black .
                          3) All leaves ( Nil ) are black .
                          4) if a node is red then it's both children is black .
                          5) every path from a given node to any its descendant nil node contains the same number of black nodes .


red black tree,red-black tree,red-black trees,red–black tree,tree,red black tree deletion,binary search tree,trees,red black trees,red-black,red black tree rotate,red black tree türkçe,red-black tree tutorial,red-black tree deletion,red-black trees - 2 - insertion,red-black trees in javascript,data structure,rb tree,data structures,red black tree code,red black tree intro,what is red black tree



  • Time Complexity : worst case = O( log n )
  • Space Complexity : Worst case = O( n )
  • Insertion : Insertion is very similar manner as a binary search tree . Insertion Follows few's property  
                                                       1) N is the root node , i.e , first node of the red black tree
                                                       2) N is parent (p) is black .
                                                       3) P is red and N is uncle (U) is red
                                                       4) p is red and u is black .
  • Application : Red Black tree Worst case time complexity is O( log n ) for insertion , deletion and searching . that is why many data structure are used in Computational geometry can be based on red black trees and completely Fair Scheduler used in current Linux Kernels. now day's it is used in java 8 .
Labels:

Comments

Post a Comment

Popular posts from this blog

how to Install Numpy, Pandas and matplotlib on ubuntu 18.04 and Linux Mint

Install Python, NumPy,Matplotlib for Python 3 on Ubuntu 18.04, Linux Mint, Debian Linux. This is a short article about installing Numpy, Pandas , Matplotlib, Python3 on the latest Ubuntu 18.04 LTS, Linux Mint, Debian Linux which comes with Python 3.6.5. Let’s start by making sure we have an updated system: 1 sudo apt update 2 sudo apt upgrade Now, let’s install NumPy, Pandas,Matplotlib : sudo apt-get install python-pip sudo pip install numpy sudo pip install pandas sudo pip install matplotlib Test numpy : Open up a Terminal in Your Linux Operating System by running the following: python3 At the Terminal, type the following: >>> import numpy as np >>> np.__version__ '1.13.3'   Test Pandas : Open up a Terminal in Your Linux Operating System by running the following: python3 At the Terminal, type the following: >>> import pandas as pd >>> pd.__version__ '0.22.0'   Test Matpl...
2 comments
Read more

Introduction to SQL and Database with example

            Introduction to SQL and Database What is SQL? SQL is a language used to retrieve and manipulate data in a RDMS. SQL stands for S tructured Q uery L anguage. What is a Database? A database is a place to store data. A relational database system (RDBMS) stores data in tables. Relational Database Tables A relational database stores data in tables. Each table has a number of rows and columns. The table below has 4 rows and 3 columns. SQL and Relational Databases A relational database contains tables which store data that is related in some way. SQL is the language that allows retrieval and manipulation of table data in a relational database.
Post a Comment
Read more

Electronic Data interchange(EDI)

Electronic Data interchange(EDI) : Computer readable forms for business documents such as invoices, purchase orders, delivery notes needed in B2B e-commerce so that e- documents can be exchanged. Essential to eliminate manual data entry, which is error prone Essential to agree on common formats for commonly used forms. Electronic data interchange (EDI) standard gives specifications for commonly used standard business forms. It is possible to adapt these standards for documents which use XML for specification. Electronic Data interchange(EDI) Specification : Defines several hundred transaction sets corresponding to each type of business document such as invoice, purchase order etc. Defines data segments - corresponding to groups of data elements such as purchase order line. Defines data elements - which are individual fields such as price, quantity etc. Electronic Data interchange(EDI)Standards :    ANSI X.12 standard proposed by American National Standard...
Post a Comment
Read more