LLRB：简化红黑树实现与原理探讨

需积分: 7 115 浏览量更新于2024-09-07 收藏 801KB PDF 举报

"LLRB（左倾红黑树）是一种红黑树的变种，由Robert Sedgewick提出，旨在实现平衡搜索树。红黑树作为数据结构在各种编程语言如C++、Java、Python以及BSD Unix等系统中广泛应用。尽管它们在标准教材中有描述，但很多实际的实现为了优化删除操作，往往牺牲了最初的设计目标。因此，重新审视并改进红黑树是必要的。本文提出了一个新的红黑树变种——左倾红黑树，它不仅满足原始设计目标，而且插入和删除操作的代码更简洁，比常用实现少四分之三以上。红黑树的核心是通过红色链接将二叉树中的内部节点组合成2-3或2-3-4树。2-3树是一种自平衡的B树，它包含两种节点：2节点（两个键和两个子节点）和3节点（三个键和三个子节点）。2-3-4树是2-3树的扩展，增加了4节点（四个键和四个子节点），以提供更大的灵活性。在红黑树中，红色链接用来模拟这些额外的节点。在传统的红黑树中，每个节点可以是红色或黑色，并遵循以下规则： 1. 节点是红色或黑色。 2. 根节点是黑色。 3. 所有叶子节点（NIL或空节点）是黑色。 4. 如果一个节点是红色，则其两个子节点必须是黑色。 5. 对每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数量的黑色节点。左倾红黑树与传统红黑树的区别在于，它规定所有红色链接都向左倾斜，即红色链接只能出现在父节点到子节点的路径上的右子节点。这个规则简化了旋转操作，尤其是处理插入和删除时的右旋。左旋通常比右旋更直观且容易实现。插入操作在左倾红黑树中通常涉及以下步骤： 1. 将新节点插入作为叶子节点，并标记为红色。 2. 遵循红黑树的性质进行调整，可能需要通过颜色翻转和旋转来保持平衡。删除操作则复杂得多，因为它可能破坏红黑树的平衡。在左倾红黑树中，由于红色链接总是向左，删除规则和旋转策略更加明确，从而简化了实现。 LLRB红黑树通过其特定的红色链接规则，提供了更简洁的代码实现，同时保持了红黑树的高效搜索性能和良好的平衡特性。这对于理解和实现红黑树，特别是对于优化和简化代码库是有益的。"

Left-leaning Red-Black Trees

Robert Sedgewick

Department of Computer Science

Princeton University

Princeton, NJ 08544

Abstract

The red-black tree model for implementing balanced search trees, introduced by Guibas and Sedge-

wick thirty years ago, is now found throughout our computational infrastructure. Red-black trees

are described in standard textbooks and are the underlying data structure for symbol-table imple-

mentations within C++, Java, Python, BSD Unix, and many other modern systems. However, many

of these implementations have sacriﬁced some of the original design goals (primarily in order to

develop an effective implementation of the delete operation, which was incompletely speciﬁed in

the original paper), so a new look is worthwhile. In this paper, we describe a new variant of red-

black trees that meets many of the original design goals and leads to substantially simpler code for

insert/delete, less than one-fourth as much code as in implementations in common use.

All red-black trees are based on implementing 2-3 or 2-3-4 trees within a binary tree, using

red links to bind together internal nodes into 3-nodes or 4-nodes. The new code is based on com-

bining three ideas:

Use a recursive implementation.•

Require that all 3-nodes lean left.•

Perform rotations on the way up the tree (after the recursive calls).•

Not only do these ideas lead to simple code, but they also unify the algorithms: for example, the left-

leaning versions of 2-3 trees and top-down 2-3-4 trees differ in the position of one line of code.

All of the red-black tree algorithms that have been proposed are characterized by a worst-case

search time bounded by a small constant multiple of lg N in a tree of N keys, and the behavior ob-

served in practice is typically that same multiple faster than the worst-case bound, close the to op-

timal lg N nodes examined that would be observed in a perfectly balanced tree. This performance

is also conjectured (but not yet proved) for trees built from random keys, for all the major variants

of red-black trees. Can we analyze average-case performance with random keys for this new, sim-

pler version? This paper describes experimental results that shed light on the fascinating dynamic

behavior of the growth of these trees. Speciﬁcally, in a left-leaning red-black 2-3 tree built from N

random keys:

A random successful search examines lg • N

–

0.5 nodes.

The average tree height is about 2 ln • N (!)

The average size of left subtree exhibits log-oscillating behavior.•

The development of a mathematical model explaining this behavior for random keys remains one

of the outstanding problems in the analysis of algorithms.

From a practical standpoint, left-leaning red-black trees (LLRB trees) have a number of at-

tractive characteristics:

Experimental studies have not been able to distinguish these algorithms from optimal.•

They can be implemented by adding just a few lines of code to standard BST algorithms.•

Unlike hashing, they support ordered operations such as • select, rank, and range search.

Thus, LLRB trees are useful for a broad variety of symbol-table applications and are prime candi-

dates to serve as the basis for symbol tables in software libraries in the future.

下载后可阅读完整内容，剩余9页未读，立即下载

yonyong3

粉丝: 0
资源: 8

LLRB：简化红黑树实现与原理探讨

有关红黑树的算法研究

红黑树（Robert Sedgewick）Princeton University

红黑树源码java-leftrb:Leftrb是Python中2-3个平衡二叉搜索树的左倾红黑(LLRB)实现。RobertSedgewick

左倾红黑树：简化的红黑树算法

gllrb:Go写的左斜红黑树

Left-Leaning_Red_Black_Tree:在C ++中实现左倾斜红黑树的实现

LLRB.pdf_algorithm_

最小左偏树的合并源代码

BSTVisualizer:一个有助于可视化各种二叉搜索树及其操作的网络应用程序

左倾红黑树算法深入解析

最新资源