title: C++ Creating an Balanced Binary Search Tree Using Array Structure
body: <p>am tasked with storing a binary tree within a vector. Within each node is stored an int ID, int Age, and a string name.</p>
  
  <p>The nodes are stored and organized within the vector by ID.</p>
  
  <p>When storing the binary tree within a vector, I am using the algorithm 2i and 2i+1 to dictate a node's left and right child respectively.</p>
  
  <p>I have managed to create an insert method that I believe satisfies these conditions, however for some reason, when attempting to print the values of my vector, I appear to get negative values. For this particular example, I insert the following values</p>
  
  <p>100 21 Stan</p>
  
  <p>50 30 Phil</p>
  
  <p>I attempt to place another node</p>
  
  <p>30 31 Alice</p>
  
  <p>According to sources, <strong>this causes the tree to become unbalanced.</strong></p>
  
  <p>So I am attempting to create a balanced binary search tree using nodes stored in a vector. Previously I created an unbalanced tree using this previous insertion structure. However, <strong>I don't exactly understand what a balanced binary search tree is</strong></p>
  
  <p>So my questions are as followed:</p>
  
  <ol>
  <li><p>What exactly is a balanced binary search tree?</p></li>
  <li><p>What would you suggest I should change in my insert function to encourage the creation of a balanced tree?</p></li>
  </ol>
  
  <p>Thanks in advance!</p>
  
  <p>Here is my code:</p>
  
  <pre><code>#include "BinaryTree.h"
  #include &lt;string&gt;
  #include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;algorithm&gt;
  
  using namespace std;
  int index = 0;
  
  struct Node
  {
      int ID = -1;
      int age = -1;
      string name = "";
  
      Node()
      {
  
  
      }
  
      Node(int id, int Age, string nm)
      {
          this-&gt;ID = id;
          this-&gt;age = Age;
          this-&gt;name = nm;
      }
  };
  
  vector&lt;Node&gt; binaryTree;
  
  
  BST::BST()
  {
  
  }
  
  
  
  
  
  void BST::insert()
  {
      unsigned int ID;
      int AGE;
      string NAME;
      int root = 0;
  
      bool success = false;
      cout &lt;&lt; "Please enter the ID number, age and name:" &lt;&lt; endl;
  
  
      cin &gt;&gt; ID &gt;&gt; AGE &gt;&gt; NAME;
  
      Node *tree = new Node(ID, AGE, NAME);
  
  
  
      if (!binaryTree.empty())
      {
          do
          {
              if (tree-&gt;ID &gt; binaryTree.at(root).ID &amp;&amp; binaryTree.at(root).ID != 0)
              {
                  root = 2 * root + 2;
                  if (root &gt;= binaryTree.size()) binaryTree.resize((2 * root + 2 + 1) * 5);
  
              }
  
              if (tree-&gt;ID &lt; binaryTree.at(root).ID &amp;&amp; binaryTree.at(root).ID != 0)
              {
                  root = 2 * root + 1;
                  if (root &gt;= binaryTree.size()) binaryTree.resize((2 * root + 2 + 1) * 5);
  
              }
  
              if (binaryTree.at(root).ID == -1)
              {
                  binaryTree[root] = *tree;
                  success = true;
              }
          } while (!success);
      }
  
      if (binaryTree.empty())
      {
          binaryTree.push_back(*tree);
      }
  
      delete tree;
  
  }
  </code></pre>