Advertisement
Published in:
2016 | OriginalPaper | Chapter
On Determination of Balance Ratio for Some Tree Structures
Authors : Daxin Zhu, Tinran Wang, Xiaodong Wang
Published in: Network and Parallel Computing
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
In this paper, we studies the problem to find the maximal number of red nodes of a kind of balanced binary search tree. We have presented a dynamic programming formula for computing r(n), the maximal number of red nodes of a red-black tree with n keys. The first dynamic programming algorithm uses \(O(n^2\log n)\) time and uses \(O(n\log n)\) space. The basic algorithm is then improved to a more efficient O(n) time algorithm. The time complexity of the new algorithm is finally reduced to O(n) and the space is reduced to only \(O(\log n)\).