L8 logn search

Binary Search Generalized

Outline：

• Red-Black Tree

Ref:

• 算法设计与分析(Algorithm design and analysis) by 黄宇

Balanced Binary Search Tree

binary search tree

• Def
  • 2-Tree
  • 左子树的所有值比根节点小，右子树的所有值比根节点大（如果properly drawn的话，会很清楚 ）

Red-Black Tree

• Def (基于二叉搜索树，附加一些性质)
  • If T is a binary search tree in which each node has a color, red or black, and all external nodes are black, then T is a red-black tree if and only if:
    • [Color constraint] No red node has a red child
    • [Black height constraint] The black length of all external paths from a given node u is the same(the black height of u)
    • The root is black
  • Almost-red-black tree(ARB tree)
    • Root is red, satisfying the other constraints

Recursive Definition of RBT

(a red black tree of black height h is denoted as $R{B}_h$

• Def:
  • An external node is an $R{B}_0$​ tree, and the node is black.
  • A binary tree is an $AR{B}_h$( $h\ge 1$ )tree if:
    • Its root is red,and
    • Its left and right subtrees are each an $R{B}_{h-1}$ tree.
  • A binary tree is an $R{B}_h$ tree if:
    • Its root is black, and
    • Its left and right subtrees are each either an $R{B}_{h-1}$​ tree or an $AR{B}_h$​ tree.​

Properties of Red-Black Tree

• The black height of any $R{B}_h$ tree or $AR{B}_h$ is well-defined and is h.
• Let T be an $R{B}_h$ tree, then:
  • T has at most $2^h-1$ internal black nodes.
  • T has at most $4^h-1$ in internal nodes.
  • The depth of any black node is at most twice its black depth.
• Let A be an $AR{B}_h$ tree, then:
  • A has at least $2^h-2$ internal black nodes.
  • A has at most $\frac{4^h}{2}-1$ internal nodes.
  • The depth of any black node is at most twice its black depth.

Bound on Depth of Node in RBT

• Let T be a red-black tree with n internal nodes. Then no node has black depth greater than $log(n+1)$, which means that the height of T in the usual sense is at most $2log(n+1)$​.
  • Proof:
  • Let h be the black height of T. The number of internal nodes, n, is at least the number of internal black nodes, which is at least $2^h-1$​, so $h\le log(n+1)$​​. The node with greatest depth is some external node. All external nodes are with black depth h. So, the depth is at most $2h$​.

Deletion

• Logical: 删除节点的内容
• Structural：删除节点，整棵树做修复

Complexity of Operations on RBT

• With reasonable implementation
  • A new node can be inserted correctly in a red-black tree with n nodes in $\mathrm{\Theta }(logn)$​ time in the worst-case
  • Repairs for deletion do $O(1)$ structural changes, but may do $O(logn)$color changes