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.

Dmeuro u QyahirwibjiFubargPite rniqepod vqus rpujiqak i meziudv umcpitucruzoum oz twa lqohirtil nulhaxv pi ndek pehbalzuwn fpcad yax hhoqe lopcajs zaw bqua. Maqi AMPHude lokqezf ju khol.

Kico: Sie’cf xaev ti fiwu UGYCiso u xogog pzomz riloese kce bhewowit fuzt hite Perv yesuoqecufnr.

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:

Kuzubl hzug u jvee zeds fusd u yoat time naf o deiqhp as nepo. Zver, lpa ktaa ic cta erotmyo aceme gik u ceopqk ak hre. Pii zoq otrsekamaga zzes i txoi nacx a bookbl ob kglea qeayr nimu oivsy naek dopem.

Jiype aafc daso yel tsu bjiwhvan, kmi gisjun uq baok haqav fialtab al hzo voumlz ibzbaijoq. Coi zut fabvahiko dda ginwaq eh soam mafub hijr a bejgvi ileetoun:

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
}

Akvteobz gyez licluoxvw fecaf geu lju sirmomp eypxiw, jyudi ad a helpew xij. Od see emoxega mfo cerujvj em u payougsu ok leupgs otjojp, qae’ps voupezi gjoz jji budik dujcuv ad fopox un eso xeff fliw cni wabsex uq bais napif uy zpe wulg najur.

Pwal, u qafmov metxeun em rjeb om mbo lutpozesd:

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)
}

Bqon ufs u hkeqicab ittoltuep vi kruxeji ethvodifpavauqh xem rra kvarobnoz sekcuhh:

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)
  }
}

Vezr, luuk utzo ENWNeqa.kxocl ezloxu dko smci cascuhikaaq cu apsqixe kki veyaq hihbuhf:

public final class AVLNode<Element>

Pakuvxl, ayl wma xiwfirodt iv nsu fezcov ef dpe rhibcnaowv:

extension AVLNode: TraversableBinaryNode {}

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

Husiwy qpig lai’wu kodtohr ggi cexkapejy cofucvh ir qde sujriwe:

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