Data Structures/Trees

From

---

Revision as of 03:51, 10 October 2008

Contents 1 Trees 1.1 Traversal 1.2 Sample implementations for Tree Traversal 1.3 Examples of Tree Traversals 1.4 Balancing 1.5 Binary Search Trees 1.5.1 Terms 1.5.2 Searching through a binary search tree 1.5.2.1 Example 1.5.3 Adding an item to a binary search tree 1.5.3.1 Example 1.5.4 Deleting an item from a binary search tree 1.5.4.1 Case 1: The node you want to delete is a leaf 1.5.4.2 Case 2: The node you want to delete has one child 1.5.4.3 Case 3: The node you want to delete has two children 1.5.4.4 Case 1: The successor is the right child of the node being deleted 1.5.4.5 Case 2: The successor isn't the right child of the node being deleted 2 Applications of Trees 3 References 4 External Links

Trees

A tree is a non-empty set, one element of which is designated the root of the tree while the remaining elements are partitioned into non-empty sets each of which is a subtree of the root.

Tree nodes have many useful properties. The depth of a node is the length of the path (or the number of edges) from the root to that node. The height of a node is the longest path from that node to its leaves. The height of a tree is the height of the root. A leaf node has no children -- its only path is up to its parent.

See the axiomatic development of trees and its consequences for more information.

Types of trees:

Binary: Each node has zero, one, or two children. This assertion makes many tree operations simple and efficient.

Binary Search: A binary tree where any left child node has a value less than its parent node and any right child node has a value greater than or equal to that of its parent node.

Red-Black Tree: A balanced binary search tree using a balancing algorithm based on colors assigned to a node, and the colors of nearby nodes.

AVL: A balanced binary search tree according to the following specification: the heights of the two child subtrees of any node differ by at most one.

Traversal

Many problems require we visit* the nodes of a tree in a systematic way: tasks such as counting how many nodes exist or finding the maximum element. Three different methods are possible for binary trees: preorder, postorder, and in-order, which all do the same three things: recursively traverse both the left and rights subtrees and visit the current node. The difference is when the algorithm visits the current node:

preorder: Current node, left subtree, right subtree(DLR)

postorder: Left subtree, right subtree, current node(LRD)

in-order: Left subtree, current node, right subtree.(LDR)

levelorder: Level by level, from left to right, starting from the root node.

• Visit means performing some operation involving the current node of a tree, like incrementing a counter or checking if the value of the current node is greater than any other recorded.

Sample implementations for Tree Traversal

preorder(node)
  visit(node)
  if node.left  ≠ null then preorder(node.left)
  if node.right ≠ null then preorder(node.right)

inorder(node)
  if node.left  ≠ null then inorder(node.left)
  visit(node)
  if node.right ≠ null then inorder(node.right)

postorder(node)
  if node.left  ≠ null then postorder(node.left)
  if node.right ≠ null then postorder(node.right)
  visit(node)

levelorder(root)
  queue<node> q
  q.push(root)
  while not q.empty do
     node = q.pop
     visit(node)
     if node.left  ≠ null then q.push(node.left)
     if node.right ≠ null then q.push(node.right)

For an algorithm that is less taxing on the stack, see Threaded Trees.

Examples of Tree Traversals

File:Bstreesample.jpg

preorder: 50, 30, 20, 40, 90, 100
inorder: 20, 30, 40, 50, 90, 100
postorder: 20, 40, 30, 100, 90, 50
levelorder: 50, 30, 90, 20, 40, 100

Balancing

When entries that are already sorted are stored in a tree, all new records will go the same route, and the tree will look more like a list (such a tree is called a degenerate tree). Therefore the tree needs balancing routines, making sure that under all branches are an equal number of records. This will keep searching in the tree at optimal speed. Specifically, if a tree with n nodes is a degenerate tree, the longest path through the tree will be n nodes; if it is a balanced tree, the longest path will be log n nodes.

Binary Search Trees

A typical binary search tree looks like this:

File:Bstreesample.jpg

Terms

Node Any item that is stored in the tree.

Root The top item in the tree. (50 in the tree above)

Child Node(s) under the current node. (20 and 40 are children of 30 in the tree above)

Parent The node directly above the current node. (90 is the parent of 100 in the tree above)

Leaf A node which has no children. (20 is a leaf in the tree above)

Searching through a binary search tree

To search for an item in a binary tree:

1. Start at the root node
2. If the item that you are searching for is less than the root node, move to the left child of the root node, if the item that you are searching for is more than the root node, move to the right child of the root node and if it is equal to the root node, then you have found the item that you are looking for :)
3. Now check to see if the item that you are searching for is equal to, less than or more than the new node that you are on. Again if the item that you are searching for is less than the current node, move to the left child, and if the item that you are searching for is greater than the current node, move to the right child.
4. Repeat this process until you find the item that you are looking for or until the node doesn't have a child on the correct branch, in which case the tree doesn't contain the item which you are looking for.

Example

File:Bstreesearchexample.jpg

For example, to find the node 40...

1. The root node is 50, which is greater than 40, so you go to 50's left child.
2. 50's left child is 30, which is less than 40, so you next go to 30's right child.
3. 30's right child is 40, so you have found the item that you are looking for :)

Adding an item to a binary search tree

1. To add an item, you first must search through the tree to find the position that you should put it in. You do this following the steps above.
2. When you reach a node which doesn't contain a child on the correct branch, add the new node there.

Example

For example, to add the node 25...

1. The root node is 50, which is greater than 25, so you go to 50's left child.
2. 50's left child is 30, which is greater than 25, so you go to 30's left child.
3. 30's left child is 20, which is less than 25, so you go to 20's right child.
4. 20's right child doesn't exist, so you add 25 there :)

Deleting an item from a binary search tree

It is assumed that you have already found the node that you want to delete, using the search technique described above.

Case 1: The node you want to delete is a leaf

File:Bstreedeleteleafexample.jpg

For example, do delete 40...

• Simply delete the node!

Case 2: The node you want to delete has one child

1. Directly connect the child of the node that you want to delete, to the parent of the node that you want to delete.

File:Bstreedeleteonechildexample.jpg

For example, to delete 90...

• Delete 90, then make 100 the child node of 50.

Case 3: The node you want to delete has two children

1. Find the left-most node in the right subtree of the node being deleted. (After you have found the node you want to delete, go to its right node, then for every node under that, go to its left node until the node has no left node) From now on, this node will be known as the successor.

File:Bstreefindsuccessorexample.jpg

For example, to delete 30

1. The right node of the node which is being deleted is 40.
2. (From now on, we continually go to the left node until there isn't another one...) The first left node of 40, is 35.
3. 35 has no left node, therefore 35 is the successor!

Case 1: The successor is the right child of the node being deleted

1. Directly move the child to the right of the node being deleted into the position of the node being deleted.
2. As the new node has no left children, you can connect the deleted node's left subtree's root as it's left child.

File:Bstreedeleterightchildexample.jpg

For example, to delete 30

1. Move 40 up to where 30 was.
2. 20 now becomes 40's left child.

Case 2: The successor isn't the right child of the node being deleted

This is best shown with an example

File:Bstreedeletenotrightchildexample.jpg

To delete 30...

1. Move the successor into the place where the deleted node was and make it inherit both of it's children. So 35 moves to where 30 was and 20 and 40 become it's children.
2. Move the successor's (35s) right subtree to where the successor was. So 37 becomes a child of 40.

Applications of Trees

Trees are often used in and of themselves to store data directly, however they are also often used as the underlying implementation for other types of data structures such as [Hash Tables], [Sets and Maps]
and other associative containers. Specifically, the C++ Standard Template Library uses special red/black trees as the underlying implementation for sets and maps, as well as multisets and multimaps.

---

References

• William Ford and William Tapp. Data Structures with C++ using STL. 2nd ed. Upper Saddle River, NJ: Prentice Hall, 2002.

External Links

• Presentation of Iterative Tree Traversals