Software 1 - Structures and makefile (10)

administrivia

Web Page - http://www.cs.tau.ac.il/~efif/courses/Software1_Spring_03

A Program for Directing Recompilation

• GNU make
• Automatically determines which pieces of a large program need to be recompiled, and issues commands to recompile them.
• target ... : prerequisites ...
    command
• rbtree example

  rbtree: Red_black_tree.o rbtree.o gcc $? -o $@ Red_black_tree.o: Red_black_tree.h rbtree.o: Red_black_tree.h clean: rm -rf Red_black_tree.o rbtree.o rbtree

Red-black Binary Tree

• A binary tree that satisfies the following properties:
  • Each node has a color, which is either red or black.
  • A red node cannot have a red parent.
  • The number of black nodes from every path from the tree root to a leaf is the same for all tree leaves (it is called the 'black depth' of the tree).
  Propeties 2-3 guaranty that the depth of a red-black tree containing n nodes is bounded by 2*log₂(n).
• Code
  • rbtree.c
  • Red_black_tree.h
  • Red_black_tree.c
  • makefile
  • makefile_simple
  • html