✦ LIBER ✦

General Balanced Trees

✍ Scribed by Arne Andersson

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 117 KB
Volume: 30
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1998.0967

No coin nor oath required. For personal study only.

✦ Synopsis

We show that, in order to achieve efficient maintenance of a balanced binary search tree, no shape restriction other than a logarithmic height is required. The obtained class of trees, general balanced trees, may be maintained at a logarithmic amortized cost with no balance information stored in the nodes. Thus, in the case when amortized bounds are sufficient, there is no need for sophisticated balance criteria.

The maintenance algorithms use partial rebuilding. This is important for certain applications and has previously been used with weight-balanced trees. We show that the amortized cost incurred by general balanced trees is lower than what has been shown for weight-balanced trees.

📜 SIMILAR VOLUMES

Balance vertices in trees

✍ Reid, K. B. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB

A new notion of balanced bipartitions of the vertices in a tree T is introduced and studied. It gives rise to a new central set of vertices in T, each of which can be considered to be a discrete version of the center of gravity of T. We seek vertices x, called balance vertices, such that the two sum

Balancing two spanning trees

✍ Matthias Kriesell 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB

AVL Trees with Relaxed Balance

✍ Kim S. Larsen 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 185 KB

The idea of relaxed balance is to uncouple the rebalancing in search trees from the updating in order to speed up request processing in main-memory databases. In this paper, we describe a relaxed version of AVL trees. We prove that each update gives rise to at most a logarithmic number of rebalancin

Do nearly balanced multigraphs have more

Do nearly balanced multigraphs have more spanning trees?

✍ Ching-Shui Cheng; Joseph C. Masaro; Chi Song Wong 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 320 KB

We prove that, with very few exceptions, every graph of order n, n = 0, 1 (mod 4) and size a t most n -1, is contained in a self-complementary graph of order n. We study a similar problem for digraphs. Throughout the paper, G and D will denote a finite graph and a finite digraph, respectively, with

Balanced Aspect Ratio Trees: Combining t

Balanced Aspect Ratio Trees: Combining the Advantages of k-d Trees and Octrees

✍ Christian A. Duncan; Michael T. Goodrich; Stephen Kobourov 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 273 KB

Given a set S of n points on ‫ޒ‬ d , we show, for fixed d, how to construct in Ž . Ž . O n log n time a data structure we call the balanced aspect ratio BAR tree. A Ž . BAR tree is a binary space partition tree on S that has O log n depth in which Ž . every region is convex and ''fat'' that is, has

Rectilinear full Steiner tree generation

✍ Zachariasen, Martin 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 353 KB

The fastest exact algorithm (in practice) for the rectilinear Steiner tree problem in the plane uses a two-phase scheme: First, a small but sufficient set of full Steiner trees (FSTs) is generated and then a Steiner minimum tree is constructed from this set by using simple backtrack search, dynamic