# **TOC**
[TOC]
# <font color="#365c0c">**Tree Introduction**★</font>
> <font color="#000000">Link List is an ++one-dimensional++ structure.</font>
A、B、C、D are nodes can represent data, state, etc。
the link between nodes call edges, may be unidirected or directed.
> <font color="#000000">Tree and Graph is an ++multidimensional++ structure.</font>
<font color="#000000">Set-relationship</font>
<span style="display:block;text-align:center;"></span>
Tree is a preferred option when we confront to ++hierarchical problems++,
that means we have ++sequence(order)++ in this structure.
Example: Premutation (R is the *root* of *Tree*)
In these picture, we choose the first alphabet A, B, C from root, then choose the second one, and so on.
<!---->
* <font color="#3770b4">**Definition**</font>
A *Tree* is a finite set of *>0* nodes such that
1. There is a specially designated node called `root`
2. The remaining nodes can be partitioned into *n≥0* ++disjointed sets++ *T~1~...T~n~* are called the `subtree` of the `root`. (means there is ++no cycle in tree++)
* <font color="#3770b4">**Discription**</font>
***Node:***
* ***degree:*** The number of subtrees of a node.
* *degree(T)=max{node's degree}*
* *degree(A)=3*
* *degree(B)=2*
* ***height/depth:***
* *height(T)=max{node's level}*
* *height(F)=2*
:::warning
height = depth
:::
* ***root:*** The most upper layer node which parent is NULL.
* *root(T)=A*
* ***leaf:*** The node doesn't have child/subtree.
* *leaf(T)=G、H、J、K、L、M、N*
* ***external node：*** The node doesn't have child.
* ++external_node=leaf++
* ***internal node：*** The node has ++a least one child++.
* *internal_node(T)=A、B、C、D、E、F、I*
<span style="display:block;text-align:center;"></span>
***Tree:***
* ***parent->child:***
* *A(parent)->C(child)*
* ***siblings:*** The nodes have same parent
* *sibling(B)=C、D*
* ***ancestor:*** The nodes travel through child->parent direction of a node.
* *ancestor(F)=C、A*
* ***descendant:*** The nodes travel through parent->child direction of a node.
* *descendant(F)=L、M*
* ***path:*** The nodes in ancestor and descendent relationship.
* *A-B-E-K*
* ***level:***
* *level(root)=1*
* *level(child)=level(parent)+1*
* *level(I)=3*
***Forest***
* A set of n≥0 Trees
# <font color="#365c0c">**Tree's Representaion**</font>
## **Link List**
* <font color="#3770b4">**Definition**</font>
* node_num(T)=n
* degree(T)=k
* **Analysis**
* Pros
* None
* Cons
* Waste link list memory
* Total: *n-k*
* Used: *n-1*
* Waste Rate: *k-1/k* (k=2 B.T)
## **Sibling child**
* <font color="#3770b4">**Definition**</font>
* Parent->left_most_child
* child->right_sibling
## **Bracket**
* <font color="#3770b4">**Definition**</font>
* Parent(C~1~ ... C~n~)
* A(B(EF)C(GD(HIJ))
## **Binary Tree(B.T)**
* <font color="#3770b4">**Definition**</font>
* A *B.T* is a finite set of *≥0* nodes, if > 0 then
* `root->left_subtree`
* `root->right_subtree`
* `left_subtree` and `right_subtree` ∈ B.T
* **Tree v.s. B.T**
| Tree | B.T |
| ---- | ---- |
| n>0 | n≥0 |
| 0≤degree(T) | 0≤degree(T)≤2 |
| unordered | ordered(left,right) |
# <font color="#365c0c">**Binary Tree★★**</font>
* <font color="#3770b4">**Definition**</font>
* [above](##Binary-Tree(B.T))
* <font color="#3770b4">**Properties**</font>
\begin{aligned}
&height(T)=h \\
&\text{At most: }2h-1\text{ nodes}\\
&num(degree==0)=n_0 (leaf) \\
&num(degree(nodes)==2)=n_2 \\
&n_0= n_2+1 &&\text{(★★★)} \\
&n = n_0+n_1+n_2 \\
&n = B+1 = 1*n_1+2*n_2+1 &&B\text{ = totoal num of edge}\\
&n = n_0+n_1+n_2 = 1*n_1+2*n_2+1 \\
\end{aligned}
* <font color="#3770b4">**Type of B.T**</font>
* **Skewed B.T**
* left-skewed B.T
* right-skewed B.T
<img src="https://hackmd.io/_uploads/Syf2UrHga.png" width="360" height="180">
* **Full B.T**
* *num(nodes) = 2^h^-1*
* **Complete B.T**
* *height(T) = h, num(nodes) = n*
* *2^h-1^-1<n≤2^h^-1*
* ==*h = ⌈log~2~(n+1)⌉*==
* order of *Tree* is from
* top to bottom
* left to right
* ==*n~1~ to n~n~, n~i~*==
* leftchild: *2i*
* if *2i>n, n~i~->left_child=null*
* rightchild: *2i+1*
* if *2i+1>n, n~i~->right_child=null*
* parent: *[i/2]*, expect *root*
*n~i~'->left_node=2i*
*n~500~'->left_node=1000*
*n~500~\~n~1000~ are leaves*
* **Strict B.T**
* *degree(non-leaf nodes)=2*
* *num(degree(n)==1)=0*
<br>
# <font color="#365c0c">**B.T's Representaion**</font>
## **Array**
* <font color="#3770b4">**Definition**</font>
* *height(T)=h*
* arr[1...2^h^-1]={}
* pros
* easy to get the nodes by index
* suit to Full/Complete B.T
* cons
* diffcult to add/delete/move nodes
* not suit to Skewed B.T
* Waste memo: 2^h^-1-h
## **Link List★**
* <font color="#3770b4">**Definition**</font>
```cpp
typedef struct TreeNode
{
int data;
TreeNode *leftChild;
TreeNode *rightChild;
//TreeNode *parent;
}TreeNode;
```
* pros
* easy to add/delete/move nodes
* suit to Skewed B.T
* cons
* not ease to save parent node, but still acceptable
* link will waste *50%* memory space
* *num(nodes)=n, 2n links*
* *n-1 links != null*
* *n+1 links == null*
# <font color="#365c0c">**Traversal★★★**</font>
There is *3!=6* kinds of Traversal
But we restrict that meet left befor right
* **DFS**
* **Pre-order:** parent->left->right
* **In-order:** left->parent->right
* **Post-order:** left->right->parent
* **BFS**
* Level-order:
* top to bottom
* left to right
<span style="display:block;text-align:center;"></span>
:::spoiler **Code**
```cpp
//DFS
//preorder
void preorder(TreeNode *root)
{
output(root);
preorder(root->leftChild);
preorder(root->rightChild);
}
//Inorder
void Inorder(TreeNode *root)
{
Inorder(root->leftChild);
output(root);
Inorder(root->rightChild);
}
//postorder
void postorder(TreeNode *root)
{
postorder(root->leftChild);
postorder(root->rightChild);
output(root);
}
//level order(BFS)
void levelorder(TreeNode *root)
{
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
TreeNode *curNode = q.front();
q.pop();
output(curNode);
if(curNode->left!=NULL)
q.push(curNode->leftChild);
if(curNode->right!=NULL)
q.push(curNode->rightChild);
}
}
```
:::
* **Complexity**
* DFS: *O(n)*
* BFS: *O(n)*
## **Reconstruction B.T★★★**
If we only have one order, we can't reconstruct a new binary tree, because there various prosiblilities.
<span style="display:block;text-align:center;"></span>
So once have two order, we can find the unique binary tree?
No!only when we have two kinds of order conbination.
1. Preorder-Inorder →
* PLR: the first node is `root`
* LPR: get the `left_subtree` and `right_subtree` by `root`
2. Postorder-Inorder ←
* LRP: the last node is `root`
* LPR: get the `left_subtree` and `right_subtree` by `root`
3. ~~Preorder-Postorder~~
* Preorder-Postorder can't identify the position of root
4. Level-order-Inorder
:::warning
Must have **inorder** to part left and right
:::
<span style="display:block;text-align:center;"></span>
Preorder-Postorder: Try and Error by person
++Pre-order:a b c++
++Post-order: c b a++
There are ++4++ conditions fullfill the order
:::info
If a **Full/Complete** tree are given only an order.
We can still restruct it
:::
:::spoiler **Code**
```cpp
//c++
typedef struct TreeNode
{
int val;
TreeNode *leftChild;
TreeNode *rightChild;
}TreeNode;
TreeNode *newTreeNode(int val)
{
TreeNode *newTreeNode = (TreeNode*)malloc*(sizeof(TreeNode));
newTreeNode->val = val;
newTreeNode->leftChild = NULL;
newTreeNode->rightChild =NULL;
}
//reconstruct tree by comparing index of inorder
void buildTree(TreeNode *curNode, vector<int> inorderIDX, int insert_val)
{
while(true)
{
if(inorderIDX[intsert_val] < inordorIDX[curNode->val])
{
if(curNode->leftChild == NULL)
{
curNode->leftChild = newNode(insert_val);
return;
}
else
curNode = curNode->left;
}
if(inorderIDX[intsert_val] > inordorIDX[curNode->val])
{
if(curNode->rightChild == NULL)
{
curNode->rightChild = newNode(insert_val);
return;
}
else
curNode = curNode->right;
}
}
}
int main()
{
string order_type;
cin >> order_type;
int num_nodes;
cin >> num_nodes;
vector<int> preorder(-1, num_nodes);
vector<int> postorder(-1, num_nodes);
vector<int> inorderIDX(-1, num_nodes);
if(order_type == "preorder-inorder")
{
int tmpIDX = -1;
for(int i=0; i<num_nodes; i++)
cin >> preoroder[i];
for(int i=0; i<num_nodes; i++)
{
cin >> tmpIDX;
inorderIDX[tmpIDX] = i;
}
//root is first element in preorder
TreeNode *root = newNode(preorder[0]);
for(int i=1; i<num_nodes; i++)
buildTree(root, inorderIDX, preorder[i]);
}
else if(order_type == "postorder-inorder")
{
int tmpIDX = -1;
for(int i=0; i<num_nodes; i++)
cin >> postoroder[i];
for(int i=0; i<num_nodes; i++)
{
cin >> tmpIDX;
inorderIDX[tmpIDX] = i;
}
//root is last element in preorder
TreeNode *root = newNode(postorder[num_nodes]);
for(int i=num_nodes; i>0; i--)
buildTree(root, inorderIDX, postorder[i]);
}
return 0;
}
```
:::
## **B.T operation**
* **copy a B.T**
```cpp
//preorder
//inorder
//postorder
//level order all acceptable
TreeNode *preorder_copy(TreeNode *root)
{
TreeNode *t = newTreeNode(root->val);
t->leftChild = preorder_copy(root->leftChild);
t->rightChild = preorder_copy(root->rightChild);
return t;
}
```
* **equal B.T**
```cpp
//preorder
//inorder
//postorder
//level order all acceptable
bool is_tree_eq(TreeNode *root1, TreeNode *root2)
{
bool res = false;
if(root1 == NULL && root2 == NULL)
res=true;
else if(root1->val == root2->val)
{
res = true;
res = is_tree_eq(root1->leftChild);
res = is_tree_eq(root2->rightChild);
}
return res;
}
```
* **count B.T nodes**
```cpp
int cnt_tree_nodes(TreeNode *root)
{
int nL,nR;
if(root == NULL)
return 0;
else
{
nL = cnt_tree_nodes(root->leftChild);
nR = cnt_tree_nodes(root->rightChild);
return (nL+nR+1)
}
}
```
* **B.T height**
```cpp
int height_Tree(TreeNode *root)
{
int hL, hR;
if(root == NULL)
return 0;
else
{
hL = height_Tree(root->leftChild);
hR = height_Tree(root->rightChild);
}
return max(hL,hR)+1
}
```
* **Swap B.T subtrees**
```cpp
void swap_tree_subtree(TreeNode *root)
{
TreeNode *tmp;
tmp = root->leftChild;
root->leftChild = root->rightChild;
root->rightChild = tmp;
return;
}
```
## **B.T Application**
### **Expression B.T★**
* **Compiler**
* Parsing Tree
* Syntax Tree
* <font color="#3770b4">**Definition**</font>
* leaf operand
* non-leaf operator
* priority = level(node)
* **parsing**
* postfix = postorder(T)
* prefix = preorder(T)
* Infix = inorder(T)
:::spoiler **Code**
```cpp
//add opcode in data structure TreeNode
int eval_exp_BT(TreeNode *root)
{
if(root == NULL)
return 0;
if (root->opcode == "n")
return root->val;
int resL,resR;
resL = eval_exp_BT(root->leftChild);
resR = eval_exp_BT(root->rightChild);
if(root->opcode == "+")
return resL+resR;
else if(root->opcode == "-")
return resL-resR;
else if(root->opcode == "*")
return resL*resR;
else if(root->opcode == "/")
return resL/resR;
else if(root->opcode == "~")'
{
if(root->leftChild != NULL)
return -resL;
else if(root->rightChild != NULL)
return -resR;
}
return 0;
}
```
:::
[Stack & Queue★★](https://hackmd.io/aNmcv36xRWewhG1lUwTDCw?both)
### **Binary Search Tree BST★★★**
* <font color="#3770b4">**Definition**</font>
* B.T number of nodes ≥ 0
* **leftChild < parent < rightChild**
* **inorder(BST): min->max** (left->parent->right)
* <font color="#3770b4">**Operation**</font>
* **Insert**
* <font color="#eb0029">**Delete**</font>
There *3* kinds of condition when we deleting the node.
* *degree(node)=0*
* leaf, *delete(p_node)*
* *degree(node)=1*
* *parent->left/rightChild->(p_node->left/rightChild)*
* *delete(p_node)*
* ++*degree(node)=2*++
There're 2 kinds of way to delete nodes with *degree(node)=2*.
* *replace(p_node)* with the ++smallest node in right subtree++
* *replace(p_node)* with the ++largest node in left subtree++
so the *degree(p_node)=0∨1*, *delete(p_node)* with case 0 or 1
* **Search in BST**
```cpp
bool bst_search(TreeNode *root, int data)
{
TreeNode *curNode = root;
while(true)
{
if(curNode == NULL)
return false;
else
{
if(data == curNode->data)
{
return true;
}
else if(data > curNode->data)
{
curNode = curNode->right;
}
else if(data < curNode->data)
{
curNode = curNode->left;
}
}
}
return false;
}
```
* ==**Search k~th~ small in BST**==
```cpp
//add information in TreeNode
//th_num=num(left_subTree nodes)+1
TreeNode* bst_search_kth(TreeNode *root, int k)
{
if(root != NULL)
{
if(k == root->th_num)
return root;
else if (k < root->th_num)
bst_search_kth(root->leftChild, k);
else if (k > root->th_num)
bst_search_kth(root->rightChild, k-root->th_num);
}
}
```
:::success
**root 為第幾小的數**
:::
* **Example**
* **Complexity**
* worst case
* ==*skewed BST O(n)*==
* best case
* f*ull/completed BST O(log~2~n)*
* *smallest height(T)=⌈log2(n+1)⌉*
:::success
successful search: *num_compare(node) = level(node)*
failed search: *num_compare(node) = level(insert(node))-1*
:::
:::info
*S = ar^0^+(a+d)r^1^+(a+2d)r^2^...+(a+(n-1)d)r^n-1^*
*rS =ar^1^+(a+d)r^2^+(a+2d)r^3^...+(a+(n-2)d)r^n-1^+(a+(n-1)d)r^n^*
*(1-r)S = ar^0^+d(r^1^+r^2^+...+r^n-1^)-(a+(n-1)d)r^n^*
:::
:::info
when you get BST nodes, you get the *inorder*
:::
:::info
*max(left_subtree)<parent<min(right_subtree)*
:::
:::spoiler **Code**
```c
#include<bits/stdc++.h>
using namespace std;
//struct of tree
typedef struct TreeNode
{
int data;
TreeNode *left;
TreeNode *right;
}TreeNode;
TreeNode *bst(TreeNode **root);
bool bst_insert(TreeNode **root, int data);
bool bst_delete(TreeNode **root, int data);
bool bst_search(TreeNode *root, int data);
void bst_print(TreeNode *root);
void prefix(TreeNode *root)
{
if(root!=NULL)
{
cout << root->data << " ";
prefix(root->left);
prefix(root->right);
}
return;
}
void infix(TreeNode *root)
{
if(root!=NULL)
{
infix(root->left);
cout << root->data << " ";
infix(root->right);
}
return;
}
void postfix(TreeNode *root)
{
if(root!=NULL)
{
postfix(root->left);
postfix(root->right);
cout << root -> data << " ";
}
return;
}
void level(TreeNode *root)
{
//bfs
queue<TreeNode*> q;
if(root == NULL)
{
return;
}
q.push(root);
while(!q.empty())
{
TreeNode *curNode = q.front();
cout << curNode->data << " ";
if(curNode->left!=NULL)
{
q.push(curNode->left);
}
if(curNode->right!=NULL)
{
q.push(curNode->right);
}
q.pop();
}
return;
}
bool bst_insert(TreeNode **root, int data)
{
//create a new node
//give the the new TreeNode a new memory location
TreeNode *newNode = (TreeNode*) malloc(sizeof(TreeNode));
newNode -> data = data;
newNode -> left = NULL;
newNode -> right = NULL;
//if root is NULL, create a new root
if(*root==NULL)
{
*root = newNode;
return true;
}
else
{
TreeNode *curNode = *root;
while(true)
{
if(data == curNode->data)
return false;
//insert in exist bst
else if(data > curNode->data)
{
//create a treeNode
if(curNode->right == NULL)
{
curNode->right = newNode;
return true;
}
else
curNode = curNode->right;
}
else if(data < curNode->data)
{
//create a treeNode
if(curNode->left == NULL)
{
curNode->left = newNode;
return true;
}
else
curNode = curNode->left;
}
}
}
return false;
}
/*
(1) If the deleted node is a leaf, then delete directly.
(2) If the deleted node has a child, then replace the deleted node with its child.
(3) If the deleted node has left and right sub-tree, then replace the deleted node
with the smallest node of the right sub-tree.
*/
bool bst_delete(TreeNode **root, int data)
{
TreeNode *curNode = *root;
TreeNode *preNode = *root;
if(*root == NULL)
return false;
while(true)
{
//cannot find TreeNode
if(curNode == NULL)
return false;
//cout << curNode->data << " ";
//find TreeNode
if(data == curNode->data)
{
//(1)
if(curNode->left == NULL && curNode->right==NULL)
{
if(curNode->data < preNode->data)
preNode->left = NULL;
if(curNode->data > preNode->data)
preNode->right = NULL;
return true;
}
//(2)
if(curNode->left == NULL || curNode->right == NULL)
{
//have left child but no right child
if(curNode->left != NULL && curNode->right == NULL)
{
curNode->data = curNode->left->data;
curNode->left = NULL;
return true;
}
//have right child but no left child
if(curNode->left == NULL && curNode->right != NULL)
{
curNode->data = curNode->right->data;
curNode->right = NULL;
return true;
}
}
//(3)
if(curNode->left!=NULL && curNode->right!=NULL)
{
TreeNode* replacedNode = curNode->right;
TreeNode* replacedPreNode = curNode->right;
//find the smallest TreeNode in right sub-tree
//which mean the left-most TreeNode
while(replacedNode->left!=NULL)
{
replacedPreNode = replacedNode;
replacedNode = replacedNode->left;
}
if(replacedNode == replacedPreNode)
{
curNode->data = replacedNode->data;
curNode->right = NULL;
return true;
}
curNode->data = replacedNode->data;
replacedPreNode->left = NULL;
//replaceNode has right child
if(replacedNode->right != NULL)
{
replacedPreNode->left = replacedNode->right;
}
return true;
}
}
//Traversal
else if(data < curNode->data)
{
preNode = curNode;
curNode = curNode->left;
}
else if(data > curNode->data)
{
preNode = curNode;
curNode = curNode->right;
}
}
return false;
}
bool bst_search(TreeNode *root, int data)
{
TreeNode *curNode = root;
while(true)
{
if(curNode == NULL)
return false;
else
{
if(data == curNode->data)
{
return true;
}
else if(data > curNode->data)
{
curNode = curNode->right;
}
else if(data < curNode->data)
{
curNode = curNode->left;
}
}
}
return false;
}
void bst_print(TreeNode *root)
{
cout << "The tree in prefix order: ";
prefix(root);
cout << endl;
cout << "The tree in infix order: ";
infix(root);
cout << endl;
cout << "The tree in postfix order: ";
postfix(root);
cout << endl;
cout << "The tree in level order: ";
level(root);
cout << endl;
return;
}
int main()
{
TreeNode *bst_root = NULL;
bst(&bst_root);
}
```
:::
### **Calculation★**
* **Construct different B.T**
\begin{aligned}
&num(node) = n \\
&num(BT) = \frac{C\binom{2n}{n}}{(n+1)} \\
\end{aligned}
### **Heap★★★**
* <font color="#3770b4">**Definition**</font>
Heap is a particular ++complete tree (suit to array)++ with two kinds of priority
* **MaxHeap:** *parent ≥ children*
* **MinHeap:** *parent ≤ children*
*max/min(Heap) = root->val* ++(priority queue)++
* **Operation** (MaxHeap)
* **Insert**
* place *node* at *array[end+1]*
* compare to it's *parent*
* *parent < node*
* swap and continue
* *parent > node*
* stop
* **Delete**
* replace *node* by *array[end]*
* compare to it's *max(childs)*
* *node < max(childs)*
* swap and continue
* *node->val > max(childs)*
* stop
* *node->childs== NULL*
* stop
* **Build**
* **Topdown**
* insert(all_nodes)
* **Complexity**
* *O(nlogn)≈log1+log2+..logn=log(n!)*
* **Bottom-up** (Faster)
* Build a *complete tree* by input data (top->bottom, left->right)
```cpp
vector<int> heap(heap_size+1,INT_MAX);
for(int i=1; i<=heap_size; i++)
cin >> heap[i];
* ==Compare every *internal nodes* from last to first==
```cpp
void maxHeapify(vector<int> &heap, int rootIDX)
{
int leftChildIDX = 2 *rootIDX;
int rightChildIDX = 2*rootIDX + 1;
int largestIDX; //record index of largest({root, leftChild, rightChild})
if(leftChildIDX < heap.size() && heap[leftChildIDX] > heap[rootIDX])
largestIDX = leftChildIDX;
else
largestIDX = rootIDX;
if(rightChildIDX < heap.size() && heap[rightChildIDX] > heap[largestIDX])
largestIDX = rightChildIDX;
if(largestIDX != rootIDX)
{
swap(heap[largestIDX], heap[rootIDX]);
maxHeapify(heap, largestIDX); //maxheapify the subtree of swapped nodes
}
}
```
```cpp
void buildMaxHeap(vector<int> &heap)
{
//[n/2] nodes has children
//buildMaxHeap from bottom to top (from [n/2] to 1)
for(int i=heap.size()/2; i>=1; i--)
maxHeapify(heap, i);
}
```
* **Complexity**
* *h=⌈log~2~(n+1)⌉*
* *internal node in level i* needs *h-i* comparsion
* There are *2^i-1^ nodes in level i*
* Total cost: *from 1 to h Σ(h-i)\*2^i-1^*
:::info
*(1-r)S = ar^0^+d(r^1^+r^2^+...+r^n-1^)-(a+(n-1)d)r^n^*
*S = 2^h^-2-h+1*
*h=⌈log~2~(n+1)⌉≈⌈log~2~n⌉*
*2^logn^-logn-1=n-logn-1*
:::
* O(n)
:::spoiler **Code**
```c
#include<bits/stdc++.h>
using namespace std;
void insertHeap(vector<int> &heap, int val);
void deleteHeap(vector<int> &heap, int val);
void maxHeapify(vector<int> &heap, int rootIDX);
void buildMaxHeap(vector<int> &heap);
void insertHeap(vector<int> &heap, int val)
{
//root == NULL
if(heap[1]==INT_MAX)
{
heap[1] = val;
return;
}
heap.push_back(val);
for(int i=heap.size()-1; heap[i]>heap[i/2]; i=i/2)
swap(heap[i], heap[i/2]);
return;
//buildMaxHeap(heap);
}
void deleteHeap(vector<int> &heap, int val)
{
vector<int>::iterator it;
it = find(heap.begin(), heap.end(), val);
if(it == heap.end())
return;
int deleteIDX = distance(heap.begin(), it);
swap(heap[deleteIDX], heap[heap.size()-1]);
heap.pop_back();
buildMaxHeap(heap);
}
void maxHeapify(vector<int> &heap, int rootIDX)
{
int leftChildIDX = 2 *rootIDX;
int rightChildIDX = 2*rootIDX + 1;
int largestIDX; //record index of largest({root, leftChild, rightChild})
if(leftChildIDX < heap.size() && heap[leftChildIDX] > heap[rootIDX])
largestIDX = leftChildIDX;
else
largestIDX = rootIDX;
if(rightChildIDX < heap.size() && heap[rightChildIDX] > heap[largestIDX])
largestIDX = rightChildIDX;
if(largestIDX != rootIDX)
{
swap(heap[largestIDX], heap[rootIDX]);
maxHeapify(heap, largestIDX); //maxheapify the subtree of swapped nodes
}
}
//bottom-up
void buildMaxHeap(vector<int> &heap)
{
//[n/2] nodes has children
//buildMaxHeap from bottom to top (from [n/2] to 1)
for(int i=heap.size()/2; i>=1; i--)
maxHeapify(heap, i);
}
void printHeap(vector<int> heap)
{
for(int i=1;i<heap.size();i++)
cout << heap[i] << " ";
}
int main()
{
int heap_size = -1;
cin >> heap_size;
//heap[0] need to be empty
vector<int> heap(heap_size+1,INT_MAX);
for(int i=1; i<=heap_size; i++)
cin >> heap[i];
buildMaxHeap(heap);
//insertHeap(heap, val);
//deleteHeap(heap, val);
printHeap(heap);
}
```
:::
* **Complexity**
| Op | Time |
| ------- | --------- |
| Insert | *O(logn)* |
| Delete | *O(logn)* |
| Max/Min | *O(1)* |
| Search | ==*O(n)*==|
| Build | ==*O(n)*==|
# <font color="#365c0c">**Tread Binary Tree**</font>
There will *n+1* links wasted in linked B.T
Take the most of these links
* <font color="#3770b4">**Definition**</font>
The node *ptr* point to depends on *++inorder++*
* **Head:** A no data node
* *head->leftchild = root*
* *head->rightchild = head*
* **Predecessor:** *node->leftChild* links to previous node in *++inorder++*
* The first *node->leftChild = head*
* **Successor:** *node->rightChild* links to next node in *++inorder++*
* The last *node->rightChild = head*
:::spoiler **Code**
```c
//add thread_code in data structure TreeNode
//default is_left_thread = false;
//default is_right_thread = true;
//The first node->leftChild = head
//The last node->rightChild = head
Treenode* ptr
if(ptr->leftChild == NULL)
{
ptr->is_left_thread = true;
ptr->leftChild = inorder.predecessor();
}
if(ptr->rightChild == NULL)
{
ptr->is_right_thread = true;
ptr->rightChild = inorder.successor();
}
```
:::
If a binary tree inorder is `D B E G A C F`,
the thread binary tree would be
Can linearly traversal binary tree, which is faster than recursively traversal.
However they're both *O(n)*.
* **Operation**
* **Find predecessor**
* Recurs find the ++left most in right subtree++
```c
TreeNode *find_predecessor(TreeNode *curNode)
{
if(curNode == NULL)
return NULL;
//leaf
else if(curNode->is_left_thread == true &&
curNode->is_right_thread == true)
return curNode->leftChild;
else if(curNode->rightChild)
return lefttMost(curNode->rightChild);
return NULL;
}
```
* **Find successor**
* Recurs find the ++right most in left subtree++
```c
TreeNode *find_successor(TreeNode *curNode)
{
if(curNode == NULL)
return NULL;
//leaf
if(curNode->is_left_thread == true &&
curNode->is_right_thread == true)
return curNode->rightChild;
if(curNode->leftChild)
return rightMost(curNode->leftChild);
return NULL;
}
```
* **Insert**
There's *2* condition
* *node* become another *node's leftChild*
* *node* become another *node's rightChild*
* *parent->is_right_thread == true*
* *parent->is_right_thread == false*
:::spoiler **Code**
```c
void insert_thread_BT(TreeNode* root, int val,int p_val, string direction)
{
TreeNode *newNode = (TreeNode*) malloc(sizeof(TreeNode));
new_node->val = val;
TreeNode* p_node = search(root, p_val);
if(p_node == NULL)
return;
if(direction == "left")
{
if(p_node->is_left_thread == true)
{
//1
newNode->rightChild = p_node;
newNode->is_right_thread = true;
//2
newNode->leftChild = p_node->leftChild;
newNode->is_left_thread = true;
//3
p_node->leftChild = newNode;
targer_node->is_left_thread = false;
}
else if (p_node->is_left_thread == false)
{
//1
newNode->rightChild = p_node;
newNode->is_right_thread = true;
//2
newNode->leftChild = p_node->leftChild;
newNode->is_left_thread = false;
p_node->leftChild = newNode;
//3
targer_node->is_left_thread = false;
//4
tmp = find_perdecessor(p_node);
tmp->right_child = p_node;
}
}
else if(direction == "right")
{
if(p_node->is_right_thread == true)
{
//1
newNode->leftChild = p_node;
newNode->is_left_thread = true;
//2
newNode->rightChild = p_node->rightChild;
newNode->is_right_thread = true;
//3
p_node->rightChild = newNode;
targer_node->is_right_thread = false;
}
else if (p_node->is_right_thread == false)
{
//1
newNode->leftChild = p_node;
newNode->is_left_thread = true;
//2
newNode->rightChild = p_node->rightChild;
newNode->is_right_thread = false;
//3
p_node->rightChild = newNode;
targer_node->is_right_thread = false;
//4
tmp = find_successor(p_node);
tmp->left_child = p_node;
}
}
}
```
:::
* **Delete**
* not-defined
:::spoiler **Code**
```c
typedef struct TreeNode
{
int val;
//0:left subTree, 1:predecessor
int leftType;
//0:right subTree, 1:successor
int rightType;
TreeNode* leftChild;
TreeNode* rightChild;
}TreeNode;
TreeNode *threadedNode(TreeNode* prev,TreeNode *curNode)
{
if(curNode == NULL)
return NULL;
threadedNode(prev, curNode->leftChild);
//predecessor
if(curNode->leftChild == NULL)
{
curNode->leftChild = prev;
curNode->leftType = 1;
}
//successor
if(prev != NULL && prev->rightChild == NULL)
{
pre->rightChild = curNode;
pre->rightTypr = 1;
}
prev = curNode;
treadedNode(prev, curNode->rightChild);
}
void threadList(TreeNode *curNode)
{
while(curNode != NULL)
{
//find the first element of inorder
while(curNode->leftType == 0)
{
curNode = curNode->leftChild;
}
output(curNode);
while(curNode->rightType == 1)
{
curNode = curNode->rightChild;
output(curNode);
}
curNode = curNode->rightChild;
}
}
int main()
{
TreeNode *prev = NULL;
TreeNode *root = creatTree();
threadNode(prev, root);
threadList(root);
}
```
:::
# <font color="#365c0c">**Transform to B.T**</font>
## **N-ary Tree to B.T**
* <font color="#3770b4">**Definition**</font>
* the first child (from left to right)
* *parent->leftChild = leftMost(parent's children)*
* other children
* *node->rightChild = node's right_sibling*
* *delete the link from parent to child*
* (rotate clockwise 45^o^)
## **Forest to B.T**
* <font color="#3770b4">**Definition**</font>
* every tree in forest *TtoBT(T)*
* *root_1->rightChild = root_2->rightChild (from left to right)*
# **Course Connection**
* [Disjoint Set](https://hackmd.io/vC9SXISoRSSKptuJMfcVrw)
* [Advance Tree](https://hackmd.io/d8ukUmPHS3iB4WGEimz5kw)
Sign in with Wallet
Connect another wallet