Binary Trees

Different type of searches

sequential

  • averageTime (n+1 )/ 2
  • worseTime - n

binary

  • O(log n)

red-black tree (*)

A red-black tree is a binary search tree that is empty or in which the root element is colored black, every other element is colored red or black and the following properties are satisfied: Red Rule: If an element is colored red, none of its children can be colored red. Path Rule: The number of black elements must be the same in all paths from the root element to elements with no children or with one child.

Binary trees

height

  • of a binary tree is the number of branches between the root and the farthest leaf, that is, the leaf with the most ancestors. 

level

two trees

either is empty or in which each non-leaf has 2 branches going down from it.

full

full if t is a two-tree with all of its leaves on the same level.  a binary tree T is full if each node is either a leaf or possesses exactly two child nodes.

complete 

if t is full through the next-to-lowest level and all of the leaves at the lowest level are as far to the left as possible.  a binary tree T with n levels is complete if all levels except possibly the last are completely full, and the last level has all its nodes to the left side.

Full Binary tree theorem

  • I = internal nodes, L = leaves, N = total number of nodes
  • N = I + L
  • L = I + 1
  • N = 2I + 1
  • I = (N-1)/2
  • L = (N+1)/2

Basically, this theorem says that the number of nodes N, the number of leaves L, and the number of internal nodes I are related in such a way that if you know any one of them, you can determine the other two.

Traversal

In order traversal: Left -> Root -> Right

=> worstTime(n)

31 25 47 42 50

25 31 42 47 50

post order traversal : Left -> Right -> Root

  • postOrder traversal produces postfix notation.

preOrder traversal: Root -> Left -> Right

  • produces prefix notation
  • also known as depth-first-search =>  search goes to the left as deeply as possible before searching to the right

breadthFirst Traversal - Level by level

  • worst time is N
  • first in first out

Binary Search trees

  • require logarithmic time on average, linear time in worse case - for inserting, removing and searching
  • TreeSet - logarithmic in the worse case