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} $

Proper binary tree: number of external vs internal nodes

If $ n_E, n_I $ are the number of external and internal nodes, respectively, here is a proof by induction of the fact:

$ n_{E} = n_{I} + 1 $

• Justification by removing nodes from T and dividing into two piles, internal node pile and external node pile
• If one node v in T, remove one node and place in external node pile. External node pile has one node, internal node pile is empty.
• Otherwise, T has more than one node. We remove from T an arbitrary external node w and its parent v, which is an internal node. We place w on the external node pile, and v on the internal node pile. If v has a parent u, we reconnect u with the former sibling z of w,and thereby remove one internal node and one external node, leaving the tree as a proper binary tree.
• Eventually we are left with a final tree consisting of a single node.

the relationship above does not hold for improper trees and nonbinary trees.

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.