A note on the largest number of red nodes in red-black trees

DOI10.1016/J.JDA.2017.03.001zbMATH Open1407.68117arXiv1406.3092OpenAlexW2963338499MaRDI QIDQ2397154FDOQ2397154

Authors: Daxin Zhu, Yingjie Wu, Lei Wang, Xiaodong Wang 

Publication date: 29 May 2017

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Abstract: In this paper, we are interested in the number of red nodes in red-black trees. We first present an $O(n^{2}logn)$ time dynamic programming solution for computing $r(n)$, the largest number of red internal nodes in a red-black tree on $n$ keys. Then the algorithm is improved to some $O(logn)$ time recursive and nonrecursive algorithms. Based on these improved algorithms we finally find a closed-form solution of $r(n)$.

Full work available at URL: https://arxiv.org/abs/1406.3092

Recommendations

• A note on the path length of red-black trees
• OPTIMAL OPERATIONS ON RED-BLACK TREES
• Insertion reachability, skinny skeletons, and path length in red-black trees
• Parallel algorithms for red--black trees
• CONSTRUCTING RED-BLACK TREE SHAPES

zbMATH Keywords

dynamic programmingexplicit solutionsred-black treesred internal nodes

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Analysis of algorithms (68W40) Data structures (68P05)

Cites Work

• Introduction to algorithms.
• Title not available (Why is that?)
• Symmetric binary B-trees: Data structure and maintenance algorithms
• A characterization of heaps and its applications
• Balanced search trees made simple
• Title not available (Why is that?)
• CONSTRUCTING RED-BLACK TREE SHAPES

Cited In (2)

• Insertion reachability, skinny skeletons, and path length in red-black trees
• A note on the path length of red-black trees

This page was built for publication: A note on the largest number of red nodes in red-black trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397154)