平衡树是一种二叉查找树，与普通二叉查找树相比，它的特点是能够在插入或删除元素时自动保持平衡状态，从而始终保证查找效率的最优性。
平衡树的最大特点是在树的每个节点上增加平衡因子，通过平衡因子判断当前节点是否平衡。平衡因子可以是-1、0或1，分别表示左子树高度高于右子树、左右子树高度相等、右子树高度高于左子树。
常见的平衡树包括AVL树、红黑树、Treap等，其中最常用的是红黑树。
红黑树是一种自平衡二叉查找树，其本质上是一种带有颜色的二叉树，每个节点都被标记为红色或黑色。它具有以下特点：
- 根节点为黑色
- 每个叶子节点都是黑色的空节点（NIL节点）
- 每个红色节点的两个子节点都是黑色的
- 从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点
红黑树通过在插入或删除节点时自动进行旋转操作来保持平衡状态。旋转操作分为左旋和右旋，通过交换节点和子节点的位置来实现。插入和删除操作需要根据当前节点的平衡因子进行旋转操作，使得红黑树重新恢复平衡状态。
红黑树具有平均插入/删除/查找时间复杂度为O(log n)，空间复杂度为O(n)的优点。因此，在需要快速的插入、删除和查找时，红黑树是一种非常好的选择。
总之，平衡树的主要优势是维持了树的平衡状态，避免了二叉查找树的退化情况。在有需要维护稳定效率的数据结构中，平衡树非常有用，应用广泛。
golang实现红黑树
package main
import (
"fmt"
)
const (
red = true
black = false
)
type Node struct {
value int
color bool
left, right *Node
}
type RBTree struct {
root *Node
}
func (t *RBTree) Insert(value int) {
t.root = insert(t.root, value)
t.root.color = black
}
func insert(node *Node, value int) *Node {
if node == nil {
return &Node{
value: value,
color: red,
}
}
if value < node.value {
node.left = insert(node.left, value)
} else if value > node.value {
node.right = insert(node.right, value)
} else {
// 如果存在相同的值，不进行插入
return node
}
// 调整树的平衡
if isRed(node.right) && !isRed(node.left) {
node = rotateLeft(node)
}
if isRed(node.left) && isRed(node.left.left) {
node = rotateRight(node)
}
if isRed(node.left) && isRed(node.right) {
flipColors(node)
}
return node
}
func (t *RBTree) Delete(value int) {
t.root = deleteNode(t.root, value)
if t.root != nil {
t.root.color = black
}
}
func deleteNode(node *Node, value int) *Node {
if value < node.value {
if node.left == nil {
return node
}
if !isRed(node.left) && !isRed(node.left.left) {
node = moveRedLeft(node)
}
node.left = deleteNode(node.left, value)
} else {
if isRed(node.left) {
node = rotateRight(node)
}
if value == node.value && node.right == nil {
return nil
}
if node.right != nil {
if !isRed(node.right) && !isRed(node.right.left) {
node = moveRedRight(node)
}
if value == node.value {
min := getMin(node.right)
node.value = min.value
node.right = deleteMin(node.right)
} else {
node.right = deleteNode(node.right, value)
}
}
}
return balance(node)
}
func isRed(node *Node) bool {
if node == nil {
return false
}
return node.color == red
}
func rotateLeft(node *Node) *Node {
x := node.right
node.right = x.left
x.left = node
x.color = node.color
node.color = red
return x
}
func rotateRight(node *Node) *Node {
x := node.left
node.left = x.right
x.right = node
x.color = node.color
node.color = red
return x
}
func flipColors(node *Node) {
node.color = !node.color
node.left.color = !node.left.color
node.right.color = !node.right.color
}
func moveRedLeft(node *Node) *Node {
flipColors(node)
if isRed(node.right.left) {
node.right = rotateRight(node.right)
node = rotateLeft(node)
flipColors(node)
}
return node
}
func moveRedRight(node *Node) *Node {
flipColors(node)
if isRed(node.left.left) {
node = rotateRight(node)
flipColors(node)
}
return node
}
func getMin(node *Node) *Node {
for node.left != nil {
node = node.left
}
return node
}
func deleteMin(node *Node) *Node {
if node.left == nil {
return nil
}
if !isRed(node.left) && !isRed(node.left.left) {
node = moveRedLeft(node)
}
node.left = deleteMin(node.left)
return balance(node)
}
func balance(node *Node) *Node {
if isRed(node.right) {
node = rotateLeft(node)
}
if isRed(node.left) && isRed(node.left.left) {
node = rotateRight(node)
}
if isRed(node.left) && isRed(node.right) {
flipColors(node)
}
return node
}
func (t *RBTree) InorderTraversal() {
if t.root != nil {
inorderTraversalHelper(t.root)
}
fmt.Println()
}
func inorderTraversalHelper(node *Node) {
if node == nil {
return
}
inorderTraversalHelper(node.left)
fmt.Printf("%v ", node.value)
inorderTraversalHelper(node.right)
}
func main() {
tree := &RBTree{}
vals := []int{5, 1, 8, 12, 6, 15, 11, 23, 20, 16, 7}
// 插入节点
for _, val := range vals {
tree.Insert(val)
}
// 打印中序遍历结果
tree.InorderTraversal()
// 删除节点
tree.Delete(8)
tree.Delete(1)
tree.Delete(16)
tree.Delete(23)
// 打印中序遍历结果
tree.InorderTraversal()
}
红黑树前序遍历
func (t *RBTree) PreorderTraversal() {
if t.root != nil {
preorderTraversalHelper(t.root)
}
fmt.Println()
}
func preorderTraversalHelper(node *Node) {
if node == nil {
return
}
fmt.Printf("%v ", node.value)
preorderTraversalHelper(node.left)
preorderTraversalHelper(node.right)
}
