Binary Trees

Simple binary tree

Binary trees are a simple and effecient means of storing information. The data is sorted as it is placed into the tree, allowing faster searching. On the right you can see a simple binary tree, consisting of 7 nodes. The lines represent links between each node. The left link is always to a node that is less than the current one, the link to the right is always to a node greater than the current one. Nodes that are directly connected and below a node are children of that node. Strictly, nodes in a binary tree may only have 2 or less children. However there are other tree types which may have more children and these are often (incorrectly) called binary trees (or b-trees) as well. Usually the tree is traversed downwards from the root node and so a link from the child to the parent is not needed.

Searching

Searching is simply a matter of starting at the top-most node (called the root node) and comparing the value of that node to what you are searching for. If you "fall out of the tree" (ie need to follow a link that doesn't exist) then the item you're searching for is not in the tree.

Example #1: Searching for node 7

  1. Starting out at #10 (because this is the root node), we determine that 7 is less than 10, so we follow the left link.
  2. We are now at node 5. 7 is greater than 5, so we follow the link to the right.
  3. We have found node 7!

Example #2: Searching for node 20

  1. Start at the root node (node 10), 20 is larger than 10, so we follow the right-hand link.
  2. 20 is less than 23, so move left.
  3. 20 is greater than 18, so attempt to move right. Because there is no child on the right hand side, we know that 20 does not exist in this tree.

Inserting

Adding to a binary tree To insert a node, you simply search for that node, and insert it at the point where you try to move onto a non-existant node. Because items are always added to the bottom of the tree, searching may generate a match if duplicate items are allowed in the tree. In this case, ignore the match and move to either the left or right child (which you choose does not matter).

Example #3: Adding node 5 (with duplicates allowed)

  1. Search for 5 until we reach the bottom of the tree.
  2. When we reached the existing node 5, we chose to go to the right. Going left at this point, or even deciding randomly will not hurt the tree.
  3. Reaching node 7 (which does not have a left-hand child), we have reached the bottom on the tree, so we link node 7 to our new node.

Deleting

Deleting is the most difficult part of a binary tree. There are 3 possible cases that we have to handle:

Deleting a leaf node

Case 1: Node to be deleted is a leaf node (has no children)

This is the easiest case; simply delete the node. It does not connect any parts of the tree, so there is no need to reconnect anything.

Example #4: Deleting node 31

  1. Delete the node from memory and remove the link from node 23


Deleting a node with 1 child

Case 2: Node to be deleted has exactly 1 child

To delete this node, we promote the child into the node-to-be-deleted's place.

Example #5: Deleting node 7

  1. Delete the node from memory
  2. Make the link that used to point to node 7 now reference node 6.


Deleting a node with 2 children

Case 3: Node to be deleted has 2 children

For this, we must take the node to the right of the node being deleted, and attach it as the right-hand child of the right-most node that is to the left of node being deleted. Usually this will result in a skinny tree. Then the left-hand child of the deleted node is promoted to where the deleted node was.

Example #6: Deleting node 10

  1. Find the right-most node that is left of 10. This is done by stepping left (to node 5) and then repeatedly stepping right until we find a node that doesn't have a right-hand child. Because we only have a small tree, this node is only 1 step away (ie node 7).
  2. Make node 23 the right-hand child of node 7
  3. Delete node 10
  4. Promote node 5 to where node 10 was.

Balanced binary trees

Degenerated b-tree Binary trees work well when unsorted data is inserted; but if ordered data is entered, the tree will degenerate into a linked-list (see right). The tree will still work, but it will lose the search effeciency (which is most likely the reason you implemented a b-tree in the first place).

Several methods have been invented to solve this problem, usually by storing some information about the tree's structure within the nodes. All of these methods balance the tree by checking if an operation will unbalance the tree, and if so readjusting the nodes to restore the tree to an optimal condition. A tree is balanced when it is impossible to reduce the height by rearranging the nodes.