RBNode depth bounds

def RBTree.RBNode.depth {α : Type u_1} : RBNode α → Nat

O(n). depth t is the maximum number of nodes on any path to a leaf. It is an upper bound on most tree operations.

Equations

• RBTree.RBNode.nil.depth = 0
• (RBTree.RBNode.node c a v b).depth = max a.depth b.depth + 1

theorem RBTree.RBNode.size_lt_depth {α : Type u_1} (t : RBNode α) : t.size < 2 ^ t.depth

def RBTree.RBNode.depthLB : RBColor → Nat → Nat

depthLB c n is the best upper bound on the depth of any balanced red-black tree with root colored c and black-height n.

Equations

• RBTree.RBNode.depthLB RBTree.RBColor.red x✝ = x✝ + 1
• RBTree.RBNode.depthLB RBTree.RBColor.black x✝ = x✝

theorem RBTree.RBNode.depthLB_le (c : RBColor) (n : Nat) : n ≤ depthLB c n

def RBTree.RBNode.depthUB : RBColor → Nat → Nat

depthUB c n is the best upper bound on the depth of any balanced red-black tree with root colored c and black-height n.

Equations

• RBTree.RBNode.depthUB RBTree.RBColor.red x✝ = 2 * x✝ + 1
• RBTree.RBNode.depthUB RBTree.RBColor.black x✝ = 2 * x✝

theorem RBTree.RBNode.depthUB_le (c : RBColor) (n : Nat) : depthUB c n ≤ 2 * n + 1

theorem RBTree.RBNode.depthUB_le_two_depthLB (c : RBColor) (n : Nat) : depthUB c n ≤ 2 * depthLB c n

theorem RBTree.RBNode.Balanced.depth_le {α : Type u_1} {t : RBNode α} {c : RBColor} {n : Nat} : t.Balanced c n → t.depth ≤ depthUB c n

theorem RBTree.RBNode.Balanced.le_size {α : Type u_1} {t : RBNode α} {c : RBColor} {n : Nat} : t.Balanced c n → 2 ^ depthLB c n ≤ t.size + 1

theorem RBTree.RBNode.Balanced.depth_bound {α : Type u_1} {t : RBNode α} {c : RBColor} {n : Nat} (h : t.Balanced c n) : t.depth ≤ 2 * (t.size + 1).log2

theorem RBTree.RBNode.WF.depth_bound {α : Type u_1} {cmp : α → α → Ordering} {t : RBNode α} (h : WF cmp t) : t.depth ≤ 2 * (t.size + 1).log2

A well formed tree has t.depth ∈ O(log t.size), that is, it is well balanced. This justifies the O(log n) bounds on most searching operations of RBSet.