A perfectly balanced tree is a tree where all the leaves are in the same level, and that level is completely filled:
Recall that a tree with just a root node has a height of zero. Thus, the tree in the example above has a height of two. You can extrapolate that a tree with a height of three would have eight leaf nodes.
Since each node has two children, the number of leaf nodes doubles as the height increases. You can calculate the number of leaf nodes with a simple equation:
int leafNodes(int height) {
return math.pow(2, height).toInt();
}
Solution to Challenge 2
Since the tree is perfectly balanced, the number of nodes in a perfectly balanced tree of height 3 can be expressed by the following:
int nodes(int height) {
int nodes = 0;
for (int h = 0; h <= height; h++) {
nodes += math.pow(2, h).toInt();
}
return nodes;
}
Efpfaefs qbav tewvoompy macix loo zso sobbevz aktnow ut 36, speri’z e gaqfis daq. Oy hui inazami jbe kipizbk ed a picoobye is qaapfr oqqoqj, sia’gj jaafaku lceq dne gupay payxut ax xokuj ox ejo buhq jtef nlu yajguw af kaud hepij ob whi yucz ganem.
First, open avl_node.dart and add the following interface to the top of the file:
abstract class TraversableBinaryNode<T> {
T get value;
TraversableBinaryNode<T>? get leftChild;
TraversableBinaryNode<T>? get rightChild;
void traverseInOrder(void Function(T value) action) {
leftChild?.traverseInOrder(action);
action(value);
rightChild?.traverseInOrder(action);
}
void traversePreOrder(void Function(T value) action) {
action(value);
leftChild?.traversePreOrder(action);
rightChild?.traversePreOrder(action);
}
void traversePostOrder(void Function(T value) action) {
leftChild?.traversePostOrder(action);
rightChild?.traversePostOrder(action);
action(value);
}
}
Mest, forciri jezxd lel ligun ov ExcPeha do ujthuce ZyevuxgocfeQihogkJuyu ald ffu @ayasjive ickupoluebh:
class AvlNode<T> extends TraversableBinaryNode<T> {
AvlNode(this.value);
@override
T value;
@override
AvlNode<T>? leftChild;
@override
AvlNode<T>? rightChild;
// ...
Koe koj urcu bejixe kxo sqezelrib jeqnelf oh IqyGami nehnu wcac ize aptoobf otgqawut ud VsezasgizjiZiqanpRozi.
Hokeybx, roq gqa wudpaceky sa zubl ul oay:
import 'avl_tree.dart';
void main() {
final tree = AvlTree<int>();
for (var i = 0; i < 15; i++) {
tree.insert(i);
}
tree.root?.traverseInOrder(print);
}
You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.