CSCA67H3 Lecture Notes - Lecture 5: Treap, Binary Search Tree, Graph Theory
whitewalnut0803 and 38507 others unlocked
6
CSCA67H3 Full Course Notes
Verified Note
6 documents
Document Summary
A tree is a connected graph without cycles or loops. Trees are important data structures in computer science. The top of the tree is the root and the nodes follow a parent-child relationship. Similar to a family tree, rooted trees in graph theory also have the root at the top and follow parent-child relationships. A tree on more than one vertex has a leaf (vertex of degree 1). A tree t on n vertices has exactly n 1 edges. De nition a binary tree is a rooted tree in which each internal vertex has two children and one parent. De nition a binary search tree is a binary tree in which each vertex contains a value and the vertices or nodes of the tree are ordered according to their values. Complete the binary search tree by lling in appropri- ate values: where do binary trees appear in computer sciences, nearly everywhere!