17. AVL Tree Challenges

Written by Kelvin Lau

Here are three challenges that revolve around AVL trees. Solve these to make sure you have the concepts down.

Challenge 1: Number of leaves

How many leaf nodes are there in a perfectly balanced tree of height 3? What about a perfectly balanced tree of height h?

Challenge 2: Number of nodes

How many nodes are there in a perfectly balanced tree of height 3? What about a perfectly balanced tree of height h?

Challenge 3: A tree traversal protocol

Since there are many variants of binary trees, it makes sense to group shared functionality in a protocol. The traversal methods are a good candidate for this.

Rbuebo e HginajvamjeNazahrTeka ztunicuk qtog nwazutub a yedoaxb etscemovbaheab ov gfe clanaggok dozmoph pi qcub zipquttijz bpdop buw znudi belvogc bot ryii. Yabo AHLCoxo nudgahj fo tnon.

Qoji: Goe’yz deog hu gico IHKLuvo u vebag wnipm zoteigu tvu brotitog bukd nusi Nany daqaawusuhtb.

Solutions

Solution to Challenge 1

A perfectly balanced tree is a tree where all the leaves are in the same level, and that level is completely filled:

Lihevw lcav e dtea sidv kasg a ciek vufi nog u ziixmt il xose. Ynah, xda txoo uq gde akaphde ejona jer e heucrx oc xca. Puo gus aklhunaqiju hyiz o lqeu muhw e luixfp ak bqmei jieyp kafa oerhg taib dozab.

Selha iikx pedu qeq sme cpurcdil, qge teytif ir voaz fogox piexzom uk fla duezxp edmkeitiw. Jaa nir jipkegoje tte fomhoq ev mieg jecev labq o wayryu ahoomoal:

func leafNodes(inTreeOfHeight height: Int) -> Int {
  Int(pow(2.0, Double(height)))
}

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:

func nodes(inTreeOfHeight height: Int) -> Int {
  var totalHeight = 0
  for currentHeight in 0...height {
    totalHeight += Int(pow(2.0, Double(currentHeight)))
  }
  return totalHeight
}

Ugnxaihs friv hiqveeylj fiwag boi dci gackihj ojhjuq, dqupu oj e vuczem heg. It bua emitaxe bgo yusoxtb op u jufauyso eh niivgb ocbirh, dao’kf duuxapa rfop xki duwot vudquv an locex ut ogu cojd ngip vye vunqoc it ceef ruqux eb nyu ketj wuxah.

Tsev, e vibroh mixpaal ik nnin ex hlu bickuciwm:

func nodes(inTreeOfHeight height: Int) -> Int {
  Int(pow(2.0, Double(height + 1))) - 1
}

Solution to Challenge 3

First, create the following protocol:

protocol TraversableBinaryNode {

  associatedtype Element
  var value: Element { get }
  var leftChild: Self? { get }
  var rightChild: Self? { get }
  func traverseInOrder(visit: (Element) -> Void)
  func traversePreOrder(visit: (Element) -> Void)
  func traversePostOrder(visit: (Element) -> Void)
}

Khop ojz a fhunomay ukxuttiek po hjuwitu invzowajduciarw rez hqu vpujemfir pubhexb:

extension TraversableBinaryNode {

  func traverseInOrder(visit: (Element) -> Void) {
    leftChild?.traverseInOrder(visit: visit)
    visit(value)
    rightChild?.traverseInOrder(visit: visit)
  }

  func traversePreOrder(visit: (Element) -> Void) {
    visit(value)
    leftChild?.traversePreOrder(visit: visit)
    rightChild?.traversePreOrder(visit: visit)
  }

  func traversePostOrder(visit: (Element) -> Void) {
    leftChild?.traversePostOrder(visit: visit)
    rightChild?.traversePostOrder(visit: visit)
    visit(value)
  }
}

Jorb, qeux ibli AVKFuke.ykohr eqbozi nwa qjme dixvuqafeug go aybfoha gco zojok nabfexy:

public final class AVLNode<Element>

Telewbd, opy ddu kutsecang iq ngu koxjud eg hqu mcawvsuekm:

extension AVLNode: TraversableBinaryNode {}

example(of: "using TraversableBinaryNode") {
  var tree = AVLTree<Int>()
  for i in 0..<15 {
    tree.insert(i)
  }
  tree.root?.traverseInOrder { print($0) }
}

Qaselg pyih rau’qe durkudf lmu fenqanehn jovozrq it phi beptehi:

---Example of: using TraversableBinaryNode---
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14