平衡木

• 二分探索木での探索は平均$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
}