1#include "btree.h"
  2#include "list.h"
  3#include "stack.h"
  4#include <stdio.h>
  5
  6/**
  7 * A helper function used to print a visual
  8 * representation of a binary tree.
  9 *
 10 * @param tree the tree or subtree to inspect
 11 * @param level the level of the subtree
 12 */
 13static void inspect(BTree *tree, int level) {
 14  if (!tree)
 15    return;
 16
 17  for (int i = 0; i < level; i++)
 18    printf("  ");
 19
 20  printf("%2d\n", tree->data);
 21  inspect(tree->left, level + 1);
 22  inspect(tree->right, level + 1);
 23}
 24
 25/**
 26 * Initializes an new subtree in a binary tree
 27 *
 28 * @param parent the parent of the new btree node
 29 * @param data the data to assign to the root of the tree.
 30 * @return Returns the new subtree
 31 */
 32BTree *btree_initialize(BTree *parent, int data) {
 33  BTree *tree = malloc(sizeof(BTree));
 34  tree->parent = parent;
 35  tree->left = NULL;
 36  tree->right = NULL;
 37  tree->data = data;
 38  return tree;
 39}
 40
 41/**
 42 * Converts a binary tree into a linked list
 43 * using an in order traversal.
 44 *
 45 * @param tree The binary tree to convert
 46 * @return Returns the head of a linked list.
 47 */
 48List *btree_to_list(BTree *tree) {
 49  if (tree == NULL)
 50    return NULL;
 51
 52  List *list = NULL;
 53  Stack *stack = stack_init();
 54  BTree *tmp = tree;
 55
 56  while (true) {
 57    if (tmp) {
 58      stack_push(stack, tmp);
 59      tmp = tmp->left;
 60    } else if (stack_size(stack) == 0) {
 61      break;
 62    } else {
 63      tmp = stack_pop(stack);
 64      if (list)
 65        list_add(list, tmp);
 66      else
 67        list = list_initialize(tree);
 68      tmp = tmp->right;
 69    }
 70  }
 71
 72  return list;
 73}
 74
 75/**
 76 * Calculates the size of a binary tree
 77 *
 78 * @param tree the tree to inspect
 79 * @return Returns the # of nodes in the binary tree.
 80 */
 81int btree_size(BTree *tree) {
 82  List *list = btree_to_list(tree);
 83  return list ? list_size(list) : 0;
 84}
 85
 86/**
 87 * Determines if a subtree in a binary tree
 88 * can be used as a scapegoat to rebalance
 89 * the tree.
 90 *
 91 * @param tree the subtree to investigate
 92 * @return Returns true then subtree can be used as a scapegoat.
 93 */
 94bool btree_is_scapegoat(BTree *tree) {
 95  int size = btree_size(tree);
 96  int parent_size = btree_size(tree->parent);
 97
 98  return ((size * 3) > (parent_size * 2));
 99}
100
101/**
102 * Rebuilds a subtree by converting it
103 * to a list then rebuilding a binary tree.
104 *
105 * @param tree The tree to rebuild
106 * @return Returns the new binary tree.
107 */
108BTree *btree_rebuild(BTree *tree) {
109  List *list = btree_to_list(tree->parent);
110  int mid = (list_size(list) / 2) - 1;
111  List *new_root = list_get(list, mid);
112  int data = ((BTree *)new_root->data)->data;
113  BTree *new_broot = btree_initialize(NULL, data);
114
115  for (int i = 0; i < list_size(list); i++) {
116    if (i == mid)
117      continue;
118
119    int data = ((BTree *)list_get(list, i)->data)->data;
120    btree_insert(new_broot, data);
121  }
122  return new_broot;
123}
124
125/**
126 * Rebalances a binary tree starting from
127 * the bottom up.
128 *
129 * @param tree the subtree to rebalance
130 * @return Returns the new root of the binary tree.
131 */
132BTree *btree_rebalance(BTree *tree) {
133  if (!tree->parent)
134    return tree;
135
136  if (btree_is_scapegoat(tree))
137    return btree_rebuild(tree);
138
139  return btree_rebalance(tree->parent);
140}
141
142/**
143 * Inserts a new node into a binary tree.
144 *
145 * @param tree the tree to insert the new new into
146 * @return Returns the root of the tree.
147 */
148BTree *btree_insert(BTree *tree, int data) {
149  if (!tree)
150    return btree_initialize(NULL, data);
151
152  if (data <= tree->data)
153    if (tree->left)
154      return btree_insert(tree->left, data);
155    else {
156      tree->left = btree_initialize(tree, data);
157      return btree_rebalance(tree->left);
158    }
159  else if (tree->right)
160    return btree_insert(tree->right, data);
161  else {
162    tree->right = btree_initialize(tree, data);
163    return btree_rebalance(tree->right);
164  }
165
166  return tree;
167}
168
169/**
170 * A helper function used to print
171 * a visual representation of a binary
172 * tree.
173 *
174 * @param tree The root of the tree to inspect
175 */
176void btree_inspect(BTree *tree) { inspect(tree, 0); }