8.3: Binary Trees and Binary Search Trees
- Page ID
- 112274
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\dsum}{\displaystyle\sum\limits} \)
\( \newcommand{\dint}{\displaystyle\int\limits} \)
\( \newcommand{\dlim}{\displaystyle\lim\limits} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\(\newcommand{\longvect}{\overrightarrow}\)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Binary and Binary Search Trees
Trees we discuss in Graph Theory are often used in Computer Science for solving many programming problems. Binary trees as a subdivision of general trees are often used in creating a structure for data storage.
A tree is a directed graph which means the edges in a tree all have directions from one vertex to another vertex. If an edge between vertices m and n is pointed from m to n, then we can call m is the parent of n and n is one of child of m.
Definition
A Binary tree is a rooted tree in which every vertex has at most two children.
Example
The trees we created for Huffman Codes are binary trees:
Definition 1
A full binary tree is a binary tree in which each vertex has either two children or zero children.
The tree in the previous example is a full binary tree.
One of important facts about a full binary tree is
Theorem 1
If a full binary tree T has n internal vertices, then T has n+1 terminal vertices and 2n+ total vertices.
In the previous example, we have 4 internal vertices (the vertices that have at least one child), then we can see the tree has 5 terminal vertices (the one that don't have any children)
It won't be sufficient to convince others an assertion stated in a theorem by just presenting a few of examples. We will need a formal proof by using basic facts and logic.
Here we present a formal proof of above theorem to let us see the logic and the way we use in proving a theorem in graph theory.
Proof
Since the T has n internal vertices and T is a full binary tree, T will have 2n vertices that are children. Since there is only one vertex in T that is not a child of any other vertices, which is the root, the total number of vertices in T is 2n+1. Now, subtract the number of internal vertices from the total number of vertices, (2n+1)-n, so T has n+1 terminal vertices.
From this point on, we will refer a vertex in a binary tree as a "node" and put the children below their parent with one on the left and one on the right. Refer the one on the left as "left child" and the one on the right as "right child"
Definition 2
A binary search tree (BST) is a binary tree T in which data are associated with the nodes. The data are arranged so that, for each node v in T, each data item in the left subtree of v is less than the data item in v, and each data item in the right subtree of v is greater than the data item in v.
Example
In this example, the graph is binary tree with set of integers associated with each node. We can see that all the number on the left subtree of a node v are all less than the number in v and all the numbers in the right subtree are all greater than the number in v for any node v in the tree, thus this is a binary search tree.
Example
Construct a binary search tree for storing following sequence of integers: 32, 10, 38, 15, 19, 8, 9, 2, 11, 42, 35
We create such binary search tree in following process:
Step 1: create a node and place the first number, 32, in the sequence into the node and use this node as the root of BST
Step 2: Set the next number in the sequence as a child of 32. In this case, it is the left child because 10 is less than 32 and all the numbers that are less than 32 go to left subtree of 32 based on the BST definition.
Step 3: Take the third number, 38, in the sequence and begin at the number in the root, 32. If the number in the sequence is less than 32, go to the left, otherwise, go to the right. If we reach a node, compare the number in the sequence with the number in the node, then either go to the left or go to the right depending on whether the number in the sequence is less than or greater than the number in the node. Keep on going until no edge to follow. In this case, 38 is greater than 32, so we go to right, but there is no edge on this direction which means 32 has not right child. Now, we set 38 as right child of 32
Step 3: Take the next number in the sequence, 15 and repeat Step 2: begin with 32, go the left. Reach 10, compare and then go to the right. No more edges, set 15 as the right child of 10:
Step 4: Take the next number in the sequence, 19 and repeat step 2.
continue until we place all the numbers in the sequence. In this case, the binary search tree is shown as following:
Tree Traversals
Traversing a tree normally means visiting the objects that each node represents in that tree
There are many different ways of traversing a tree
- Breadth-first Search
Visit all the nodes in the same level before visit the nodes in the next level beginning at level 0 (root)
Using such method to visit the tree in above example, we are getting a sequence of numbers as following: 32, 10, 38, 8, 15, 35, 42, 2, 9, 11, 19 - Depth-first Search
Set the items in a tree in a certain order v1,v2,..., vn. Visit the root first, and then visit the closest node with the smallest position number. From the second visited node, do the same thing: visit the closest node with the smallest position number. Repeat this process until reach a terminal node. After a terminal node is visited, visit its siblings. When all the members in a family (children and parent) are visited, visit the siblings of the parent of this family.
Here, we demonstrate how to use Depth-first Search method to traverse the binary search tree we created in above example. In this binary search tree, we have 11 nodes which represent a set of 11 integers. The Depth-first Search depends on the way we arrange those integers. Here we simply arrange them in an ascending order: 2, 8, 9, 10, 11, 15, 19, 32, 35, 38, 42 and use a position value i with i = 1, 2, 3, ..., 11 to represent the positions of each integer in the sequence. For example, the position value of the integer 2 is 1 and the position value of 19 is 7. And we also name each node in this binary search tree with the number it represents. For example, we will name the root as node 32 and call its left child node 10 and so on.
Now, let's get started.
step 1: visit the root node32, then from 32 visit next closest node and choose the one with the smallest position value. In this case, it is node 10
step 2: from node 10, visit closest node with the smallest position again. Continue this process until we reach a terminal node, in this case, it is node 2
step 3: After visiting this terminal node, visit its siblings if it has siblings.
step 4: After everyone in this family is visited, visit the siblings of the parent. In this case, it is node 15.
step 5: Now, from node 15, repeat the Depth-first Search.
step 6: After all the members of node 15's family are visited, all the members in node 10's family are also visited, now visit the siblings of node 10, which is node 38
With Depth-first Search from each node, we will eventually visit all the node in the tree and get a sequence of numbers as following: 32, 10, 8, 2, 9, 15, 11, 19, 38, 35, 42
It may seem very complicated and very confusing, actually, it is not. It is just difficult to explain it with the text. Let's watch the following video demo:
- Preorder Visit
This method visits the parents before visiting their children. Children are visited right after the parent is visited and children are visited from left to right
If we preorder visit the binary search tree we created in above example, we will get a sequence as following:
32, 10, 8, 2, 9, 15, 11, 19, 38, 35, 42
For this binary search tree, Preorder Visit and Depth-First Search produce the same result. But, in general, they won't. - Inorder Visit
This method visits a binary tree as following: visit a node after all the nodes in it left subtree are visited and before any node in its right subtree is visited.
If we inorder visit the binary search tree we created in above example, we will get following sequence:
2, 8, 9, 10, 11, 15, 19, 32, 35, 38, 42 - Postorder Visit
This method visits a node after all the descendent of this node are visited. Siblings are visited from left to right.
If postorder visit the binary search tree we created in above example, we will get following sequence:
2, 9, 8, 11, 19, 15, 10, 35, 42, 38, 32
We can write an algorithm for creating a binary search tree or any type of binary tree. We can also write algorithms for those traverse methods and code them with different computer languages. We can use tree structures in many programming applications and more.
Studying computer science is a long journey, it will never end.