# -*- mode: org -*-
#+HTML_HEAD: <link rel="stylesheet" type="text/css" href="../css/emacs.css" />



* *Binary Tree structure concepts*

#+CAPTION: A UML diagram of a Node for a LinkedList. It contains some data as well as a previous pointer and next pointer. 2. UML diagram of a Binary Tree's node. It also has a data member variable, and it has a node pointer to a left child and a node pointer to a right child.
[[http://rachel.likespizza.com/courses/_images/bytopic/datastructure-heap/different-nodes.png]]

Remember that a Linked List contains Nodes, and each Node contains
the data, as well as a pointer to the next Node item (and maybe even
the previous!) A tree-based structure is similar to a linked list
type structure.

A Tree is also made up of Nodes, though a tree is hierarchical. The
Node stores the data, as well as pointers to its children Nodes. For
a Binary Tree, any given Node has a Left Child Node pointer and a
Right Child Node pointer.

#+CAPTION: A small tree with "A" as the top (root) node, "B" to its left, and "C" to its right. The written code says: nodeA.data = "A"; nodeA.ptrLeft = nodeB; nodeA.ptrRight = nodeC;
[[http://rachel.likespizza.com/courses/_images/bytopic/datastructure-heap/ABC-tree.png]]



#+BEGIN_cf
#+BEGIN_REVIEW
Review 1. Which is which?

Linked List node:
#+ATTR_HTML: :class options-float
- ○ ptrLeft and ptrRight
- ○ ptrPrev and ptrNext

Binary Tree node:
#+ATTR_HTML: :class options-float
- ○ ptrLeft and ptrRight
- ○ ptrPrev and ptrNext
#+END_REVIEW
#+END_cf



* *Complete binary trees*

#+CAPTION: A tree drawing, there is a root node with 2 children. The left child has 2 children, and the right child has 1 child on the left side.
[[http://rachel.likespizza.com/courses/_images/bytopic/datastructure-heap/complete-binary-tree.png]]

Complete binary tree: A complete binary tree is one where all nodes
have 2 children, except possibly in the lowest level. Additionally:

- In the 2nd-to-lowest level, if a node has children, then all its
  siblings to its left must have 2 children each.
- If a node in the 2nd-to-lowest level has only one node, it must be
  a left child.
- This mean the tree fills from left-to-right.



#+BEGIN_cf
#+BEGIN_REVIEW
Review 2. Is this binary tree *complete*?

#+CAPTION: A tree with "A" as its root node, with "B" as the left child of "A" and "C" as the right child of "A".
[[http://rachel.likespizza.com/courses/_images/bytopic/datastructure-heap/tree-question1.png]]

#+ATTR_HTML: :class options-float
- ○ Complete
- ○ Not complete

---------------------------------

Review 3. Is this binary tree *complete*?

#+CAPTION: A tree with "A" as its root node, with "B" as the left child of "A" and "C" as the right child of "A". The "B" node has a right child "D".
[[http://rachel.likespizza.com/courses/_images/bytopic/datastructure-heap/tree-question2.png]]

#+ATTR_HTML: :class options-float
- ○ Complete
- ○ Not complete
#+END_REVIEW
#+END_cf



* *Heaps*

#+CAPTION: Another image of a Heap. The contents don't really matter, the important thing is that children are filled from left-to-right.
[[http://rachel.likespizza.com/courses/_images/bytopic/datastructure-heap/max-heap.png]]

#+BEGIN_QUOTE
“In a heap data structure the node keys are always larger than their
child nodes, but their children nodes are not in any particular
order.” [...]

“Three major characteristics make a heap data structure what it is:
(a) A heap is a binary tree. (b) A heap is a complete data
structure, meaning the rows of nodes are completely filled in from
left to right without any gaps, [...] (c) Every node in a heap is
larger than or equal to its child nodes.”
#+END_QUOTE

From Data Structures and Algorithms for Game Developers, by Allen Sherrod, page 328-329

** *Identifying Heaps*

Remember that the criteria for a heap is:

- (A) a heap is a *binary tree*,
- (B) a heap is *complete*, and
- (C) every node in a heap is larger than or equal to its child
  nodes (for a max-heap).




#+BEGIN_cf
#+BEGIN_REVIEW
Review 4. *○ True or ○ False:* A node's child can be larger than the
node itself (for a max heap).

Review 5. Is this a heap?

#+CAPTION: A tree with 100 as its root. 100's left child is 50. 100's right child is 40. 50's left child is 15. 50's right child is 35. 40's left child is 27.
[[http://rachel.likespizza.com/courses/_images/bytopic/datastructure-heap/tree-question3.png]]

#+ATTR_HTML: :class options
- ○ Min-heap
- ○ Max-heap
- ○ Not a heap

---------------------------------

Review 6. Is this a heap?

#+CAPTION: A tree with 60 as its root. 60's left child is 20, and 60's right child is 70. 20's left child is 10, and 20's right child is 40. 40's left child is 30, and 40's right child is 50.
[[http://rachel.likespizza.com/courses/_images/bytopic/datastructure-heap/tree-question4.png]]

#+ATTR_HTML: :class options
- ○ Min-heap
- ○ Max-heap
- ○ Not a heap

---------------------------------

Review 7. Is this a heap?

#+CAPTION: A tree with 50 as the root. 50 has a left child of 100. 50 has a right child of 40.
[[http://rachel.likespizza.com/courses/_images/bytopic/datastructure-heap/tree-question5.png]]

#+ATTR_HTML: :class options
- ○ Min-heap
- ○ Max-heap
- ○ Not a heap

#+END_REVIEW
#+END_cf

--------------------------------------------------------------------------

** *Implementation of a Heap*

Even though heaps are visualized as a binary tree, they are usually
implemented with an array structure, with the root node (the node
with the greatest value) being at index 0.

#+CAPTION: “Example of a complete binary max-heap with node keys being integers from 1 to 100 and how it would be stored in an array.” by Maxiantor; downloaded from https://en.wikipedia.org/wiki/Heap data structure#Implementation
[[http://rachel.likespizza.com/courses/_images/bytopic/datastructure-heap/heap-array-tree.png]]

With a heap implemented in this way, you can locate children and
parents by modifying the index of a given node at position i (that
is, item[i])

- Its left child, if it exists, is items[2 * i + 1]
- Its right child, if it exists, is items[2 * i + 2]
- Its parent, if it exists, is items[(i - 1) / 2]

Remember that only the root in items[0] does not have a parent.

#+ATTR_HTML: :class figure
From Data Abstraction & Problem Solving with C++: Walls and Mirrors
7th ed, by Carrano and Henry, page 489



#+BEGIN_cf
#+BEGIN_REVIEW
Review 8. The root's index is ___ , the root's *left child* is at index
___ , the root's *right child* is at index ___ .



Review 9. Given this heap:

#+CAPTION: A tree with 100 as its root. 100's left child is 80. 100's right child is 50.
[[http://rachel.likespizza.com/courses/_images/bytopic/datastructure-heap/tree-question6.png]]

What would the array look like?

| *Index* |   0 |   1 |   2 |   3 |   4 |   5 |
| *Value* | ___ | ___ | ___ | ___ | ___ | ___ |

#+END_REVIEW
#+END_cf