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

DOI10.1016/J.JDA.2017.03.001MaRDI QIDQ2397154zbMATH OpenOpenAlexFDO

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)

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

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)

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)$.

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

Cites work

• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 2090024 (Why is no real title available?)
• A characterization of heaps and its applications
• Balanced search trees made simple
• CONSTRUCTING RED-BLACK TREE SHAPES
• Introduction to algorithms.
• Symmetric binary B-trees: Data structure and maintenance algorithms

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)