Software 1 - Red-Black Tree & awk(8)

administrivia

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

awk

• Pattern scanning and processing language and utility
• awk
• Calling Built-in Functions

  toupper(string)

  returns a copy of string, with each lower-case character in the string replaced with its corresponding upper-case character. Nonalphabetic characters are left unchanged. For example, toupper("MiXeD cAsE 123") returns "MIXED CASE 123".

  or(v1, v2)

  Returns the bitwise OR of the values provided by v1 and v2.

  lshift(val, count)

  returns the value of val, shifted left by count bits.

  printf

  fancy printing

  awk 'BEGIN { printf "%-10s %s\n", "Name", "Number" printf "%-10s %s\n", "----", "------" } { printf "%-10s %s\n", $1, $2 }' BBS-list

• Regular Expressions as Patterns

  /foo|bar|baz/ { buzzwords++ } END { print buzzwords, "buzzwords seen" }

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