English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In this paper, we investigate the problem to compute the largest number of red nodes in red-black trees in red-black trees. We first present a dynamic programming solution for computing ) (n r , the largest number of red internal nodes in a red-black tree on n keys in ) log ( 2 n n O time. Then the algorithm is improved to a new ) (n O time algorithm. Based on the structure of the solution we finally present a linear time recursive algorithm using only ) log ( n O space. Introduction Red-black tree was invented in 1972 by Rudolf Bayer[2]. Guibas and Sedgewick named it red-black tree in 1978[4]. In their paper they studied the properties of red-black trees at length and introduced the red/black color convention. Andersson [1] gives a simpler-to-code variant of red-black trees. Weiss [7] calls this variant AA-trees. An AA-tree is similar to a red-black tree except that left children may never be red. In 2008, Sedgewick introduced a simpler version of the red-black tree called the left-leaning red-black tree[5] by eliminating a previously unspecified degree of freedom in the implementation. Red-black trees can be made isometric to either 2-3 trees or 2-4 trees,[5] for any sequence of operations. The number of black nodes on any simple path from, but not including, a node x down to a leaf is called the black-height of the node, denoted ) (x bh . By the property (5), the notion of black-height is well defined, since all descending simple paths from the node have the same number of black nodes. The black-height of a red-black tree is defined to be the black-height of its root. We are interested in the number of red nodes in red-black trees in this paper. We will investigate the problem that in a red-black tree on n keys, what is the largest possible ratio of red internal nodes to black internal nodes, and what is the smallest possible ratio. Dynamic Programming Algorithm Let T be a red-black tree on n keys. The largest and the smallest number of red internal nodes in a red-black tree on n keys can be denoted as ) (n r and ) (n s respectively. The values of ) (n r and ) (n s can be easily observed for the special case of 1 2 = − k n . In the general cases, we denote the largest number of red internal nodes in a subtree of size i and black-height j to be ,0) , ( j i a when its root red and ,1) , ( j i a when its root black respectively. Since in a red-black tree on n keys we have n j n log 2 log 2 1 ≤ ≤ , we have, ) , , ( max = ) , ( log 2 log 2 1 k j n a k n n j n ≤ ≤ g (1) Furthermore, for any i j i n i log 2 log 2 1 , 1 ≤ ≤ ≤ ≤ , we can denote, 5th International Conference on Information Engineering for Mechanics and Materials (ICIMM 2015) © 2015. The authors Published by Atlantis Press 1134

An Optimal Algorithm for Computing the Largest Number of Red Nodes