On Determination of Balance Ratio for Some Tree Structures
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. Th
- PDF / 166,605 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 83 Downloads / 172 Views
Quanzhou Normal University, Quanzhou 362000, China Fujian University of Technology, Fuzhou 350108, China [email protected] School of Mathematical Science, Peking University, Beijing 100871, China 2
3
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(n2 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).
1
Introduction
This paper studies the worst case balance ratio of the red-black tree structure. A red-black tree is a kind of self-balancing binary search tree. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions. The data structure was originally presented by Rudolf Bayer in 1972 with its name ’symmetric binary B-tree’ [2]. Guibas and Sedgewick named the data structure red-black tree in 1978, [4]. They introduced the red/black color convention and the properties of a red-black tree at length. A simpler-to-code variant of red-black trees was presented in [1,5]. This variant of red-black trees was called the variant AA-trees [8]. The left-leaning red-black tree [6] was introduced in 2008 by Sedgewick. It is a new version of red-black tree which eliminated a previously unspecified degree of freedom. Either 2–3 trees or 2–4 trees can also be made isometric to red-black trees for any sequence of operations [6].
2
The Basic Properties and Algorithms
A red-black tree of n keys is denoted by T in this paper. In a red-black tree T of n keys, r(n) and s(n), are defined as the maximal and the minimal number of red internal nodes respectively. It is readily seen that in this case of n = 2k − 1, the number of red nodes of T achieves its maximum, if the node from the bottom c IFIP International Federation for Information Processing 2016 Published by Springer International Publishing AG 2016. All Rights Reserved G.R. Gao et al. (Eds.): NPC 2016, LNCS 9966, pp. 205–212, 2016. DOI: 10.1007/978-3-319-47099-3 17
206
D. Zhu et al.
to the top are colored alternately red and black. the number of red nodes of T achieves its minimum, if the node from the bottom to the top are all colored black. In the special case of n = 2k − 1, we can conclude, (k−1)/2
r(n) = r(2k − 1) =
2k−2i−1
i=0 (k−1)/2
= 2k−1 k−1
= = = = = =
2
3
i=0
4−
1 4i 1
4(k−1)/2
2k+1 − 2k−1−2(k−1)/2 3 k+1 (k−1) mod 2 2 −2 3 2k+1 − 2 + k mod 2 3 k 2(2 − 1) + k mod 2 3 2n + log(n + 1) mod 2 3
The number of black nodes b(n) can then be, b(n) = n − r(n) 2n + log(n + 1) mod 2 3 n − log(n + 1) mod 2 = 3
=n−
Therefore, in this case, the rat
Data Loading...
