Java编程入门：2-4树与B树详解（第8版45-48章）

需积分: 10 144 浏览量更新于2024-07-21 收藏 1.36MB PDF 举报

《Java语言程序设计第八版》是一本专为初学者设计的编程教材，英文原名为Introduction to Java programming，包含了第45章至第48章的内容。该部分着重讲解了2-4树和B-树的数据结构与算法。以下是章节概要： 46.2-4树与B-树 - 目标：理解什么是2-4树（2-3-4树），它是一种完全平衡的搜索树，所有叶节点位于同一层级。2-4树的特性包括： - 节点类型：节点可以有1、2或3个元素。内部2-节点有一个元素和两个子节点，内部3-节点有两个元素和三个子节点，内部4-节点有三个元素和四个子节点。 - 子树结构：每个子树也是一个2-4树，可能为空。根节点无父节点，叶节点无子节点。 - 元素唯一性：树中的元素互不相同。 46.3 搜索元素 - 学习如何在2-4树中查找特定元素，理解查找操作的实现方法。 46.4 插入元素及分裂节点 - 描述如何插入元素到2-4树中，以及当节点满时如何进行分裂操作，以保持树的平衡。 46.5 删除元素与转移与融合操作 - 学习删除元素时可能涉及的转移和融合操作，以维护树的结构完整性。 46.6 遍历元素 - 掌握遍历2-4树的所有元素的方法，可能包括前序、中序和后序遍历。 46.7-46.8 实现与测试Tree24类 - 介绍如何实现并测试一个名为Tree24的类，该类可能实现了2-4树的基本操作。 46.9 2-4树的复杂性分析 - 分析2-4树在时间复杂度和空间复杂度上的特点，理解其高效性能的关键。 46.10 B-树的应用 - 探讨如何利用B-树来索引大量数据，B-树在数据库和文件系统等场景中的优势。通过学习这一系列章节，读者将深入理解2-4树和B-树在Java编程中的应用，掌握它们在数据结构和算法中的重要地位，以及在实际编程项目中如何高效地使用这些数据结构。这对于提高程序设计能力和解决大型数据处理问题具有重要意义。

46–6 Chapter 46 2-4 Trees and B-Trees

Listing 46.2 gives an algorithm for inserting an element.

LISTING 46.2 Inserting an Element to a 2-4 Tree

1 public boolean insert(E e) {

2 if (root == null)

3 root = new Tree24Node<E>(e); // Create a new root for element

4 else {

5 Locate leafNode for inserting e

6 insert(e, null, leafNode); // The right child of e is null

7 }

9 size++; // Increase size

10 return true; // Element inserted

11 }

13 private void insert(E e, Tree24Node<E> rightChildOfe,

14 Tree24Node<E> u) {

15 if (u is a 2- or 3- node) { // u is a 2- or 3-node

16 insert23(e, rightChildOfe, u); // Insert e to node u

17 }

18 else { // Split a 4-node u

19 Tree24Node<E> v = new Tree24Node<E>(); // Create a new node

20 E median = split(e, rightChildOfe, u, v); // Split u

22 if (u == root) { // u is the root

23 root = new Tree24Node<E>(median); // New root

24 root.child.add(u); // u is the left child of median

25 root.child.add(v); // v is the right child of median

26 }

27 else {

28 Get the parent of u, parentOfu;

29 insert(median, v, parentOfu); // Inserting median to parent

30 }

31 }

32 }

The insert(E e, Tree24Node<E> rightChildOfe, Tree24Node<E> u) method

inserts element e along with its right child to node u. When inserting e to a leaf node, the

right child of e is null (line 6). If the node is a 2- or 3-node, simply insert the element to the

node (lines 15–17). If the node is a 4-node, invoke the split method to split the node (line

20). The split method returns the median element. Recursively invoke the insert method

to insert the median element to the parent node (line 29). Figure 46.9 shows the steps of

inserting elements 34, 3, 50, 20, 15, 16, 25, 27, 29, and 24 into a 2-4 tree.

46.5 Deleting an Element from a 2-4 Tree

To delete an element from a 2-4 tree, first search the element in the tree to locate the node that

contains the element. If the element is not in the tree, the method returns false. Let u be the

node that contains the element and parentOfu be the parent of u. Consider three cases:

Case 1: u is a leaf 3-node or 4-node. Delete e from u.

Case 2: u is a leaf 2-node. Delete e from u. Now u is empty. This situation is known as

underflow. To remedy an underflow, consider two subcases:

Case 2.1: u’s immediate left or right sibling is a 3- or 4-node. Let the node be w, as shown

in Figure 46.10(a) (assume that w is a left sibling of u). Perform a transfer operation that

create a new node

insert e

one element added

element added

insert to a node

a 2- or 3-node

split 4-node

new root

insert median to parent

underflow

transfer

M46_LIAN0807_08_SE_C46.QXD 11/16/09 12:08 PM Page 46–6

剩余26页未读，继续阅读

qqqrrrjjj

粉丝: 3
资源: 30

Java编程入门：2-4树与B树详解（第8版45-48章）

Java语言程序设计(第8版)习题答案

Java语言程序设计-基础篇(原书第8版)

《Java语言程序设计（第八版）》编程习题答案

JAVA语言程序设计第十版

java语言程序设计第九章思维导图

java语言程序设计 姚羽

java语言程序设计pdf下载

java语言程序设计第10版(基础篇+进阶篇) 答案

java语言程序设计编程练习

java语言程序设计(第4版)

最新资源

java语言程序设计姚羽