Tree Structures -
Binary Search Tree, AVL-tree, B-tree
Author: PhD Jaanus Pöial, Estonian
IT College
All videoclips are captured
during fall semester of 2011 when the course was taught in
English.
Learning outcomes:
- Student knows the basic definitions - tree, BST, AVL-tree,
B-tree, heap
- Student is able to use different types of tree structures in
programs
- Student is able to implement a tree in object oriented
framework
Video (230 min)
Video
1 - Introduction to
trees, tree of an arithmetic expression
Video
2 - Traversal of trees,
representation of trees, implementation
Video
3 - Binary trees
Video
4 - Binary search tree,
AVL-tree, binary heap, heapsort
Video
5 - B-tree, binomial
tree
Lecture
Notes
Lecture 1 - Trees. Examples of trees - arithmetic expression
tree. Traversal of trees - preorder, postorder, in-order.
Forms of expression for trees - parenthetic expressions,
pointer structures, textual representation. Examples of
"top-down" and "bottom-up" traversal (in Estonian: puud, puude
läbimine, suluesitused, näited läbimise kohta)
Lecture 2 - Binary search trees, AVL trees,
red-black trees, binomial trees. B-trees. Heaps, heapsort (in
Estonian: kahendotsimise puu, AVL-puu, binomiaalpuu, B-puu,
kahendkuhi)
Extra
