11 Binary Trees

Binary Tree¶

flowchart TB

subgraph ct[Complete Tree]
    direction TB
    p --> q & r
    q --> s & t
    r --> u & v
end

subgraph pt[Proper Tree]
    direction TB
    a --> b & c
    b --> d & e
end

Binary Search Tree¶

Inorder traversal goes through elements in ascending order

Operations Complexity: \(O(\log_2 n)\)

flowchart TB
6 --> 5 & 7

7 --> 0[" "] & 8
8 --> -1[" "] & 9

5 --> 3 & 4
3 --> 1 & 2

Insertion¶

If the element already exists in BST, then traverse left once and then right once

flowchart LR

Before -.-> After

subgraph Before
direction TB
z[4] --> x[2] & y[3]
x --> w[1] & l[" "]
end

subgraph After
direction TB
4 --> 2 & 3
2 --> 1 & k[" "]
1 --> -1[" "] & a[2]
end

Deletion¶

Algorithm delete(w, v)
    find(w, v)

    if isExternal()
        remove w
    if isInternal
        Find smallest descendant d of w
        Replace w with d
        remove d in the leaf node

For internal node, you can replace \(w\) with the

• smallest element from right subtree
• largest element from left subtree

Depth¶

Calculating depth is \(O\Big(1 + \text{depth(v)} \Big)\)

Algorith depth(v)
    if isRoot(v)
        return 0
    else
        return 1 + depth( parent(v) )

Height¶

Height is kinda like the reverse of depth

Algorith depth(v)
    if isExternal(v)
        return 0
    else
        h = 0
        for each w children(v) do
            h = 

Properties¶

Expressions¶

Algorithm printExpression(v)
    if isInternal(v)
        print("(")
        printExpression(leftChild(v))
    print(v.element())
    if isExternal(v)
        printExpression(rightChild(v))
        print(")")

Algorithm evaluateExpression()
    something

Euler Tour Traversal¶

Application¶

Computing number of descendants of a node

Algo countDescendants(t, v)
    count = t.counter
    somethign

Comments