数据结构与算法：AVL树

二叉查找树

type BinaryTree struct {
	root *Node
}

type Node struct {
	item  int
	count int
	left  *Node
	right *Node
}

func NewBinaryTree() *BinaryTree {
	tree := new(BinaryTree)
	return tree
}

插入操作

func (t *BinaryTree) Insert(item int) {
	if t.root == nil {
		t.root = &Node{
			item:  item,
			count: 1,
		}
		return
	}
	insert(t.root, item)
}

func insert(node *Node, item int) {

	if item > node.item {
		if node.right == nil {
			node.right = &Node{
				item:  item,
				count: 1,
			}
		} else {
			insert(node.right, item)
			return
		}
	} else if item < node.item {
		if node.left == nil {
			node.left = &Node{
				item:  item,
				count: 1,
			}
		} else {
			insert(node.left, item)
			return
		}
	} else {
		node.count++
	}
}

前序遍历

func (t *BinaryTree) Print() {
	print(t.root)
}

func print(n *Node) {
	if n == nil {
		return
	}
	print(n.left)

	for i := 0; i < n.count; i++ {
		fmt.Printf("n.item: %v\n", n.item)
	}
	print(n.right)
}

查询

func (t *BinaryTree) Get(item int) bool {
	return get(t.root, item)
}

func get(n *Node, item int) bool {
	if n == nil {
		return false
	}
	if n.item == item {
		if n.count > 0 {
			return true
		} else {
			return false
		}
	} else if item > n.item {
		return get(n.right, item)
	} else {
		return get(n.left, item)
	}
}

AVL 平衡二叉查找树

AVL 树是计算机科学中最早被发明的自平衡二叉查找树。在 AVL 树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(logn),增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。

假设平衡因子是左子树的高度减去右子树的高度所得到的值，又假设由于在二叉排序树上插入节点而失去平衡的最小子树根节点的指针为a（即a是离插入点最近，且平衡因子绝对值超过1的祖先节点），则失去平衡后进行的规律可归纳为下列四种情况：

• 单向右旋平衡处理LL：由于在a的左子树根节点的左子树上插入节点，a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次右旋转操作；
• 单向左旋平衡处理RR：由于在a的右子树根节点的右子树上插入节点，a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行一次左旋转操作；
• 双向旋转（先左后右）平衡处理LR：由于在a的左子树根节点的右子树上插入节点，a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。
• 双向旋转（先右后左）平衡处理RL：由于在a的右子树根节点的左子树上插入节点，a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。

代码如下：

func NewBinaryTree() *BinaryTree {
	tree := new(BinaryTree)
	return tree
}

type BinaryTree struct {
	root *Node
}

type Node struct {
	item   int
	count  int
	left   *Node
	right  *Node
	height int8
}

func GetHeight(node *Node) int8 {
	if node == nil {
		return -1
	}
	return node.height
}

func (b *BinaryTree) Insert(item int) {
	b.root = insert(b.root, item)
}

func insert(node *Node, item int) *Node {
	if node == nil {
		return &Node{
			item:   item,
			count:  1,
			height: 0,
		}
	}
	if item > node.item {
		node.right = insert(node.right, item)
		if GetHeight(node.right)-GetHeight(node.left) > 1 {
			if item > node.right.item {
				node = singleRotateRight(node)
			} else {
				node = doubleRotateRight(node)
			}
		}
	} else if item < node.item {
		node.left = insert(node.left, item)
		if GetHeight(node.left)-GetHeight(node.right) > 1 {
			if item > node.left.item {
				node = doubleRotateLeft(node)
			} else {
				node = singleRotateLeft(node)
			}
		}
	} else {
		node.count++
	}
	node.height = maxInt8(GetHeight(node.left), GetHeight(node.right)) + 1
	return node
}

func maxInt8(a, b int8) int8 {
	if a > b {
		return a
	}
	return b
}

func singleRotateLeft(n *Node) *Node {
	n1 := n.left
	n.left = n1.right
	n1.right = n
	n1.height = maxInt8(GetHeight(n1.left), GetHeight(n1.right)) + 1
	n.height = maxInt8(GetHeight(n.left), GetHeight(n.right)) + 1
	return n1
}

func singleRotateRight(n *Node) *Node {
	n1 := n.right
	n.right = n1.left
	n1.left = n
	n1.height = maxInt8(GetHeight(n1.left), GetHeight(n1.right)) + 1
	n.height = maxInt8(GetHeight(n.left), GetHeight(n.right)) + 1
	return n1
}

func doubleRotateLeft(n *Node) *Node {

	n.left = singleRotateRight(n.left)
	return singleRotateLeft(n)
}

func doubleRotateRight(n *Node) *Node {
	n.right = singleRotateLeft(n.right)
	return singleRotateRight(n)
}