This document contains detailed notes from Lecture 18 of the CO2412 course on Computational Thinking, focusing on key data structures and algorithms essential for exam preparation. The lecture provides an in-depth review of Binary Trees, Binary Search Trees (BSTs), Heaps, and Graph Theory, along wi...
Binary Trees
1. Definition and Structure
o A Binary Tree is a data structure where each node has at most two
children referred to as the left child and the right child.
2. Key Characteristics
o Nodes in a binary tree can have 0, 1, or 2 children.
o The binary tree is used in various algorithms due to its efficiency in
searching and sorting operations.
Binary Search Trees (BST)
1. What is a Binary Search Tree?
o A Binary Search Tree (BST) is a sorted binary tree where each
node's left subtree contains only nodes with values less than the
node's value, and the right subtree contains only nodes with values
greater than the node's value.
2. Properties of a BST
o A BST is sorted by key, allowing efficient searching, insertion, and
deletion operations.
o The left child is less than the parent key, and the right child is
greater.
Full Binary Tree
1. Definition
o A Full Binary Tree is one in which every node has either 0 or 2
children. The height of a full binary tree is log(n), where n is the
number of nodes.
2. Level Properties
o Each level in a full binary tree has double the number of nodes
compared to the previous level.
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper BpoBpo. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €4,31. Je zit daarna nergens aan vast.
