平衡木

• 二分探索木での探索は平均$O(\log n)$，最悪$O(n)$
• 木の左右のバランスが取れていれば効率的に探索ができるけど，偏りがあると（もはやそれは配列とおんなじなので）効率が悪い
• 「新たにデータが加えられても，その度に左右のバランスを保つ」ような木があればいいのになぁ...
• それは「平衡木」
• でも，「新たにデータが加えられても，その度に左右のバランスを保つ」のにかかる計算が$O(\log n)$を超えちゃうと意味がない．
• 完全二分木に対する探索は最も効率がいいけど，データが加わるたびに完全二分木に木を作り変えるのはよくない．最悪の場合，木を作り変えるのに最悪$O(n)$かかってしまう．
• じゃあ，どの程度バランスしておくのがいいのだろうか？
• いろいろ研究された結果，「左右の部分木の高さの差が$-1$，$0$，$+1$のいずれか」であればいい感じになりそうだという．
• 「（どの頂点から見ても）左右の部分木の高さの差が$-1$，$0$，$+1$のいずれか」という制約を満たす平衡木のことをAVL木という
• AVL木を使って連想配列mapを実装している言語もあるらしい

実装

package main

import (
    "fmt"
    "math/rand"
)

type Node struct {
    Key int
    Height int
    Left, Right *Node
}

func (n *Node) getHeight() int {
    if n != nil {
        return n.Height
    }
    return -1
}

// `LeftRotate()` rotates to left a tree whose root is `root`
// and returns rotated tree's root node.
func LeftRotate(root *Node) (rotated *Node) {
    rotated = root.Right
    root.Right = rotated.Left
    rotated.Left = root

    root.Height = max(root.Left.getHeight(), root.Right.getHeight()) + 1
    rotated.Height = max(rotated.Left.getHeight(), rotated.Right.getHeight()) + 1
    return rotated
}

// `RightRotate()` rotates to right a tree whose root is `root`
// and returns rotated tree's root node.
func RightRotate(root *Node) (rotated *Node) {
    rotated = root.Left
    root.Left = rotated.Right
    rotated.Right = root

    root.Height = max(root.Left.getHeight(), root.Right.getHeight()) + 1
    rotated.Height = max(rotated.Left.getHeight(), rotated.Right.getHeight()) + 1
    return rotated
}

// `LeftRightRotate()`...
//     1. rotates to left a tree whose root is `root.Left`
//     2. rotates to right a tree whose root is `root`
// and returns rotated tree's root node.
func LeftRightRotate(root *Node) *Node {
    root.Left = LeftRotate(root.Left)
    root = RightRotate(root)
    return root
}

// `RightLeftRotate()`...
//     1. rotates to right a tree whose root is `root.Right`
//     2. rotates to left a tree whose root is `root`
// and returns rotated tree's root node.
func RightLeftRotate(root *Node) *Node {
    root.Right = RightRotate(root.Right)
    root = LeftRotate(root)
    return root
}

func max(x, y int) int {
    if x < y {
        return y
    }
    return x
}

// `Insert()` returns inserted AVL tree's root.
func Insert(root *Node, key int) *Node {
    if root == nil {
        root = &Node{Key:key, Height:0, Left:nil, Right:nil}
        root.Height = max(root.Left.getHeight(), root.Right.getHeight()) + 1
        return root
    }
    if key < root.Key {
        root.Left = Insert(root.Left, key)
        if root.Left.getHeight() - root.Right.getHeight() == 2 {
            if key < root.Left.Key {
                root = RightRotate(root)
            } else {
                root = LeftRightRotate(root)
            }
        }
    }
    if key > root.Key {
        root.Right = Insert(root.Right, key)
        if root.Right.getHeight() - root.Left.getHeight() == 2 {
            if key > root.Right.Key {
                root = LeftRotate(root)
            } else {
                root = RightLeftRotate(root)
            }
        }
    }
    root.Height = max(root.Left.getHeight(), root.Right.getHeight()) + 1
    return root
}

type action func(node *Node)

func InorderTraverse(root *Node, action action) {
    if root == nil {
        return
    }
    InorderTraverse(root.Left, action)
    action(root)
    InorderTraverse(root.Right, action)
}

func PostorderTraverse(root *Node, action action) {
    if root == nil {
        return
    }
    PostorderTraverse(root.Left, action)
    PostorderTraverse(root.Right, action)
    action(root)
}

func PreorderTraverse(root *Node, action action) {
    if root == nil {
        return
    }
    action(root)
    PreorderTraverse(root.Left, action)
    PreorderTraverse(root.Right, action)
}

func main() {
    var avl *Node
    keys := make([]int, 50)
    for i := range keys {
        keys[i] = i
    }
    keys = shuffle(keys)
    for _, key := range keys {
        avl = Insert(avl, key)
    }
    InorderTraverse(avl, func(node *Node) {
        fmt.Println("KEY: ", node.Key, ", HEIGHT: ", node.Height)
    })
}

func shuffle(data []int) []int {
    n := len(data)
    for i := n - 1; i >= 0; i-- {
        j := rand.Intn(i + 1)
        data[i], data[j] = data[j], data[i]
    }
    return data
}