Binary Trees

Notes

Goodrich Chapter 8 Trees

See Trees for more notes from this chapter.

Binary Trees

A binary tree is an ordered tree that has the properties:

• Every node has max 2 children
• Each child labeled as left or right
• Left has precedence over right

Other definitions:

• Subtree rooted at left or right child of an internal node is the left subtree/right subtree
• Proper binary trees - trees in which each node has either zero or two children
• Improper binary tree - one or more nodes with a single child

Binary Tree Abstract Data Type

• tree.left(p) - returns the position that is the left child of p
• tree.right(p) - returns the position that is the right child of p
• tree.sibling(p) - return the position that represents the sibling of p

Binary Tree Properties

Let T be a non-empty binary tree, and let n, n_E, n_I, and h denote number of nodes, number of external nodes, number of internal nodes, and height of T, respectively.

Then T has the following properties:

$ h+1 \leq n \leq 2^{h+1} - 1 $

$ 1 \leq n_{E} \leq 2^h $

$ h \leq n_I \leq 2^h - 1 $

$ \log{(n+1)} - 1 \leq h \leq n-1 $

Proper binary tree properties

If T is a tree that is proper, it has the following properties:

$ 2h + 1 \leq n \leq 2^{h+1} - 1 $

$ h + 1 \leq n_{E} \leq 2^h $

$ h \leq n_I \leq 2^h - 1 $

$ \log{(n+1)} - 1 \leq h \leq \dfrac{(n-1)}{2} $

Skiena Chapter 3 Data Structures

Question 3-5

Question 3-5) Find the overhead fraction (data space/total space) for each binary tree implementation on n nodes given the following conditions:

• All nodes store data, 2 child pointers, and 1 parent pointer. Data fields are 4 bytes, pointers are 4 bytes.
• Only leaf nodes store data; internal nodes store 2 child pointers. Data field requires 4 bytes, 2 bytes per pointer.

First case:

• Binary tree with n nodes -> n-1 edges
• Child/parent ppointers means 2x edges
• 2(n-1) edges, 2(n-1) pointers
• Alternatively, here's the analysis:

n nodes x (4 bytes of data/node) = 4n bytes data

n nodes x (12 bytes of pointers/node) = 12 n bytes

Total space is 16 n bytes, so overhead fraction is 1/4, i.e., the data space to total space ratio is 1/4

Second case:

• If we have n nodes, we have ~n/2 leaves
• n nodes total x (1 leaf node / 2 nodes) ~ n/2 lleaf nodes

n/2 empty nodes x (2 pointers/1 empty node) x (2 bytes/pointer) = 2n bytes for empty nodes with pointers

n/2 data nodes x (4 bytes/1 empty node) = 2n bytes data

The overhead fraction is thus 1/2: half the bytes are for data, half the bytes are for pointers.

Question 3-6

Question 3-6) Describe how to modify any balanced tree structure such that search, insert, delete, min, max each take the expected amount of time, O(log n), but sucessor and predecessor methods now take O(1) time each. What modifications are required, and to which methods?

The methods:

• Predecessor(D,k) - returns the predecessor key (in order) to the given key k
• Successor(D,k) - returns the successor key to the given key k

Question is, how to we implement neighbor lookup in O(1) time in a balanced tree?

Two options:

• Option one - add a previous and next node pointers. This increases the complexity of the bookkeeping, and of the add/insert/remove methods, which now have to traverse the tree to fix their links.
• Option two - make a data tree that is twice as big, and only holds data in the bottom-most leaf nodes. This obviates the need for a next and previous pointer, because the tree is easy to navigate - up and over... at most log(n) operations to traverse tree.

Option one:

We would need to modify the add() and insert() method, the delete method, no need to modify search or min or max methods.

We modify them to keep track of the previous node. Finding the previous node would be somewhat tricky logic. When we add a new node, find its next and previous nodes, and link them correctly.

Option two:

It would be algorithmically easier (but more expensive and more complicated implementation wise) to use a tree structure with only data in the leaf nodes. Finding/keeping track of next or previous node then doesn't require the extra two pointers and the extra logic of traversing a binary tree, it just requires twice the number of nodes (tree of size N has N/2 leaf nodes).

This also requires implementation of the entire data structure again, and it is not so obvious how you keep a tree structure like that balanced and dynamically resized.