Please enable JavaScript.
Coggle requires JavaScript to display documents.
(M8) CHAPTER 1, 4 AND 5 - Coggle Diagram
(M8) CHAPTER 1, 4 AND 5
TREES
FOREST
GRAPH NOT CONNECTED TO OTHERS
ROOTED TREES
THERE ARE LEVELS
EVERY TWO VERTICES HAS JUST ONE PATH TO EACH OTHER
ANCESTORS
ALL VERTICES FROM THE ROOT TO ANOTHER VERTICE IS ANCESTORS OF THIS ONE
PARENT
THE VERTICE BEFORE (NEXT UPPER LEVEL)
CHILD
THE VERTICE AFTER (NEXT DOWN LEVEL)
SIBLING
VERTICES WITH SAME PARENT
DESCENDANTS
ALL VERTICES ARE DESCENDATS OF A VERTICE THAT ARE THEIR ANCESTORS
DEPTH
LENGTH OF THE PATH FROM ROOT TO VERTICE
HEIGHT
LENGTH OF THE LONGEST PATH FROM ROOT TO A LEAF
LEAF
VERTICE WITH NO CHILDREN
ORDERED TREES
HAS ALL VERTICES ORDERED
LEFT AND RIGHT SIDE (SUBTREES)
BINARY TREE
FREE TREE
NUMBER OF EDGES IS ALWAYS ONE LESS THAN THE NUMBER OF VERTICES
BINARY TREE
SET OF NODES THAT IS EMPTY OR ANOTHER BINARY TREE
EMPTY SUBTREES ARE SPECIAL NODES (EXTERNAL)
SUBTRESS WITH AT LEAST ONE CHILD IS ORIGINAL NODE (INTERNAL)
NUMBER OF EXTERNAL = NUMBER OF INTERNAL + 1
TRAVERSALS
PREORDER
ROOT FIRST
INORDER
ROOT AFTER LEFT
POSTORDER
ROOT AFTER
SEARCH AND INSERT
MOST SENSIBLE MEASURE OF SIZE
HEIGHT
SEARCH SUBTREE BY SUBTREE, LEFT AND THEN RIGHT
WORST CASE Θ(N)
AVERAGE CASE Θ(LOG N)