// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"errors"
	"fmt"
)

var (
	ErrorDuplicatedNode = errors.New("在树上发现重复值")
	ErrorNodeNotFound   = errors.New("节点没有找到")
)

// node 表示二叉树中的一个节点
type node struct {
	height, value int   // 节点的高度和值
	left, right   *node // 左右子节点
}

// newNode 创建具有指定值的新节点
func newNode(val int) *node {
	return &node{
		height: 1,
		value:  val,
		left:   nil,
		right:  nil,
	}
}

// 高度返回节点的高度
// 如果节点为 nil，则 Height 返回 0
func (n *node) Height() int {
	if n == nil {
		return 0
	}
	return n.height
}

// balanceFactor 返回节点的平衡因子
// 如果节点为 nil，balanceFactor 返回 0
func (n *node) balanceFactor() int {
	if n == nil {
		return 0
	}
	return n.left.Height() - n.right.Height()
}

// updateHeight 根据其子节点的高度更新节点的高度
func (n *node) updateHeight() {
	max := func(a, b int) int {
		if a > b {
			return a
		}
		return b
	}
	n.height = max(n.left.Height(), n.right.Height()) + 1
}

// 值返回节点的值
func (n *node) Value() int {
	return n.value
}

// Left 返回节点的左子节点
func (n *node) Left() *node {
	return n.left
}

// Right 返回节点的右子节点
func (n *node) Right() *node {
	return n.right
}

func insertNode(node *node, val int) (*node, error) {
	// 如果没有节点，则创建一个
	if node == nil {
		return newNode(val), nil
	}

	// 如果有重复的节点，则返回错误
	if node.value == val {
		return nil, ErrorDuplicatedNode
	}

	// 如果值大于当前节点的值，则向右插入
	if val > node.value {
		right, err := insertNode(node.right, val)

		if err != nil {
			return nil, err
		}

		node.right = right
	}

	// 如果值小于当前节点的值，则向左插入
	if val < node.value {
		left, err := insertNode(node.left, val)

		if err != nil {
			return nil, err
		}

		node.left = left
	}

	return rotateInsert(node, val), nil
}

func removeNode(node *node, val int) (*node, error) {
	if node == nil {
		return nil, ErrorNodeNotFound
	}

	if val > node.value {
		right, err := removeNode(node.right, val)
		if err != nil {
			return nil, err
		}

		node.right = right
	} else if val < node.value {
		left, err := removeNode(node.left, val)
		if err != nil {
			return nil, err
		}

		node.left = left
	} else {
		if node.left != nil && node.right != nil {
			//寻找继任者
			successor := greatest(node.left)
			value := successor.value

			// 删除后继者
			left, err := removeNode(node.left, value)
			if err != nil {
				return nil, err
			}
			node.left = left

			// 复制后继值到当前节点
			node.value = value
		} else if node.left != nil || node.right != nil {
			//将子位置移动到当前节点
			if node.left != nil {
				node = node.left
			} else {
				node = node.right
			}
		} else if node.left == nil && node.right == nil {
			// 简单地删除节点
			node = nil
		}
	}

	if node == nil {
		return nil, nil
	}

	return rotateDelete(node), nil
}

func findNode(node *node, val int) *node {
	if node == nil {
		return nil
	}

	// 如果找到节点，则返回该节点
	if node.value == val {
		return node
	}

	// 如果值大于当前节点的值，则向右递归搜索
	if val > node.value {
		return findNode(node.right, val)
	}

	// 如果值小于当前节点的值，则向左递归搜索
	if val < node.value {
		return findNode(node.left, val)
	}

	return nil
}

func rotateInsert(node *node, val int) *node {
	// 每次插入时更新高度
	node.updateHeight()

	//会告诉你重量在哪一边
	bFactor := node.balanceFactor()

	//向左线性
	if bFactor > 1 && val < node.left.value {
		return rightRotate(node)
	}

	//直线向右
	if bFactor < -1 && val > node.right.value {
		return leftRotate(node)
	}

	//小于符号
	if bFactor > 1 && val > node.left.value {
		node.left = leftRotate(node.left)
		return rightRotate(node)
	}

	// 大于符号
	if bFactor < -1 && val < node.right.value {
		node.right = rightRotate(node.right)
		return leftRotate(node)
	}

	return node
}

func rotateDelete(node *node) *node {
	node.updateHeight()
	bFactor := node.balanceFactor()

	// 向左线性
	if bFactor > 1 && node.left.balanceFactor() >= 0 {
		return rightRotate(node)
	}

	if bFactor > 1 && node.left.balanceFactor() < 0 {
		node.left = leftRotate(node.left)
		return rightRotate(node)
	}

	if bFactor < -1 && node.right.balanceFactor() <= 0 {
		return leftRotate(node)
	}

	if bFactor < -1 && node.right.balanceFactor() > 0 {
		node.right = rightRotate(node.right)
		return leftRotate(node)
	}

	return node
}

func rightRotate(x *node) *node {
	y := x.left
	t := y.right

	y.right = x
	x.left = t

	x.updateHeight()
	y.updateHeight()

	return y
}

func leftRotate(x *node) *node {
	y := x.right
	t := y.left

	y.left = x
	x.right = t

	x.updateHeight()
	y.updateHeight()

	return y
}

func greatest(node *node) *node {
	if node == nil {
		return nil
	}

	if node.right == nil {
		return node
	}

	return greatest(node.right)
}

func traverse(node *node) {
	if node == nil {
		return
	}
	fmt.Println(node.value)
	traverse(node.left)
	traverse(node.right)
}

func main() {
	node1 := newNode(2)
	node2 := newNode(1)
	node1.left = node2
	insertNode(node2, 2)
	traverse(node1)
}