Learning toolsProgress & bookmarks
p. 415 · PDF 425
1-4-2 Balanced Tree
Balanced tree is a tree structure that is reorganized to prevent any decline in access efficiency because the level of only a particular leaf becomes deep by adding or deleting data. (A heap is also a type of balanced tree.) The following two tree structures are the representative balanced trees.
(1) AVL tree
AVL tree is a binary tree where difference in depth between right and left leaves in each node is zero or one.
Original source text
Figure 7-12 Examples of an AVL tree and a non-AVL tree
Source visual description
The original AVL and non-AVL trees retain the node depth annotations and the marked difference in depth.
(2) B tree
B tree is a balanced tree where the concept of a binary tree is developed into n-ary tree. B tree is a data structure that has the following features.
- • All leaves are at the same level.
- • Each node except the root has n or more and 2n or fewer elements.
- • In each node (including the root), the number of child node is “number of
elements+1”. - • Each element in the node is sorted.
Original source text
Figure 7-13 Image of B tree
Source visual description
The original B tree shows multi-key nodes, pointer fields and linked groups of keys.
Section progress
Original chapter exercises
Original chapter exercises →New FE Textbook Vol.1 · IT Fundamentals · First Edition, April 2015