CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Minimum and maximum ratio of number of red internal nodes to black internal nodes in Red Black tree

by Pawan Jindal, Amit Kumar, Shishir Kumar
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 5 - Number 9
Year of Publication: 2010
Authors: Pawan Jindal, Amit Kumar, Shishir Kumar
10.5120/965-1112

Pawan Jindal, Amit Kumar, Shishir Kumar . Minimum and maximum ratio of number of red internal nodes to black internal nodes in Red Black tree. International Journal of Computer Applications. 5, 9 ( August 2010), 1-3. DOI=10.5120/965-1112

@article{ 10.5120/965-1112,
author = { Pawan Jindal, Amit Kumar, Shishir Kumar },
title = { Minimum and maximum ratio of number of red internal nodes to black internal nodes in Red Black tree },
journal = { International Journal of Computer Applications },
issue_date = { August 2010 },
volume = { 5 },
number = { 9 },
month = { August },
year = { 2010 },
issn = { 0975-8887 },
pages = { 1-3 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume5/number9/965-1112/ },
doi = { 10.5120/965-1112 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T19:53:45.930447+05:30
%A Pawan Jindal
%A Amit Kumar
%A Shishir Kumar
%T Minimum and maximum ratio of number of red internal nodes to black internal nodes in Red Black tree
%J International Journal of Computer Applications
%@ 0975-8887
%V 5
%N 9
%P 1-3
%D 2010
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Data structure is being used for designing of databases, software system etc. Different data structures are being used for different kinds of applications and some data structures are particular used for specific tasks. B-trees are particularly used for implementation of databases. Hash tables are widely used for implementations of compilers. Tree is non linear data structure which is better than array, linked list because the time complexity for different operations like searching, insertion, deletion etc. is less in the case of tree. The time complexity for dynamic operations like searching, insertion, deletion, updating a node etc. is directly proportional to the height of red black tree. As the height(h) of red black tree is directly proportional to the O(lg(n)) where n represents the total number of nodes in a particular red black tree. So the time complexity for different dynamic operations like searching, insertion, deletion, updating a node etc. is directly proportional to the O(lg(n)). In this paper, Minimum and maximum ratio of number of red internal nodes to black internal nodes in Red Black tree is determined and explained with the help of diagram.

References
  1. E. Horowitz and S. Sahni, "Fundamental of Computer Algorithms", Computer Science Press, 1982.
  2. T. Cormen, C. Leiserson and R. Rivest, "Introduction to Algorithms", MIT Press, 1991
  3. A.V. Aho, J.E. Hopcroft and J.D. Ullman, "The Design and Analysis of Computer Algorithms", Addison-Wesley, 1974.
  4. A.V. Aho, J.E. Hopcroft and J.D. Ullman, "Data Structures and Algorithms", Addison-Wesley,1984.
  5. N. Wirth, "Algorithms and Data Structures" Prentice-Hall, 1986
  6. D. I-Iarel, "Algorithmics: The spirit of computing", Addison-Wesley 1987.
  7. R. Baeza-Yates, "Teaching Algorithms", IV Iberoamerican Congress on Computer Science Education, Canela, Brazil, July 1995.
  8. G. Tel, "Introduction to Distributed Algorithms"Cambridge Univ. Press 1995.
  9. G- Brassard, and P. Bratley, "Algorithmics: Theory and Practice", Prentice-Hall, 1988.
  10. E.M. Reingold, J. Nievergelt and N. Deo, "Combinatorial Algorithms: Theory and Practice",Prentice-Hall, 1977.
Index Terms

Computer Science
Information Sciences

Keywords

Tree Red black tree time complexity

Powered by PhDFocusTM