平衡树（Balanced Tree）

• 李艳生
• 湖北师范大学
• 物理与电子科学学院
• 2020年春季

回顾

• 树（父子关系的节点集合）
• 二叉树（最多只有两个子节点）
• 二叉搜索树（左子节点<节点<右子节点）

引入

平衡树的概念

• 解决BST树左右子树不平衡引起性能问题。
• AVL（Adelson-Velskii-Landi）树是一种自平衡二叉搜索树
• 任何一个节点左右两侧子树的高度之差最多为1

平衡树的概念

AVL树创建

class AVLTree extends BinarySearchTree {   
    constructor(compareFn = defaultCompare) {
        super(compareFn);     
        this.compareFn = compareFn;     
        this.root = null;   
    } 
} 

节点的高度

• 节点的高度是从节点到其任意子节点的边的最大值。

节点的高度

getNodeHeight(node) {   
    if (node == null) {     
        return -1;   
    }   
    return Math.max(this.getNodeHeight(node.left), 
     this.getNodeHeight(node.right)) + 1; 
}

平衡因子

• 节点左子树高度（hl）和右子树高度（hr）之间的差值
• 差值（hl－hr）应为0、1或-1
• 如果结果不是这三个值之一，则需要平衡该AVL树

平衡因子

平衡因子

const BalanceFactor = {
  UNBALANCED_RIGHT: 1,
  SLIGHTLY_UNBALANCED_RIGHT: 2,
  BALANCED: 3,
  SLIGHTLY_UNBALANCED_LEFT: 4,
  UNBALANCED_LEFT: 5
};
getBalanceFactor(node) {
  const heightDifference = this.getNodeHeight(node.left) - 
    this.getNodeHeight(node.right);
  switch (heightDifference) {
    case -2:
      return BalanceFactor.UNBALANCED_RIGHT;
    case -1:
      return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
    case 1:
      return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
    case 2:
      return BalanceFactor.UNBALANCED_LEFT;
    default:
      return BalanceFactor.BALANCED;
  }
}

平衡操作

• 左-左（LL）：向右的单旋转
• 右-右（RR）：向左的单旋转
• 左-右（LR）：向右的双旋转（先LL旋转，再RR旋转）
• 右-左（RL）：向左的双旋转（先RR旋转，再LL旋转）

向右的单旋转

向右的单旋转

向右的单旋转

rotationLL(node) {
  //将节点X置于节点Y（平衡因子为+2）所在的位置
  const tmp = node.left;
  //将节点Y的左子节点置为节点X的右子节点Z
  node.left = tmp.right;
  //将节点X的右子节点置为节点Y
  tmp.right = node;
  return tmp;
}

向左的单旋转

向左的单旋转

向左的单旋转

rotationRR(node) {
    //将节点X置于节点Y（平衡因子为2）所在的位置
    const tmp = node.right;
    //将节点Y的右子节点置为节点X的左子节点Z
    node.right = tmp.left;
    //将节点X的左子节点置为节点Y
    tmp.left = node;
    return tmp;
}

向右的双旋转

向右的双旋转

向右的双旋转

rotationLR(node) {
    //先做一次RR旋转，即左旋转
    node.left = this.rotationRR(node.left);
    //再做一次LL旋转，即右旋转
    return this.rotationLL(node);
}

向左的双旋转

向左的双旋转

rotationRL(node) {
    //先做一次LL旋转，即右旋转
    node.right = this.rotationLL(node.right);
    //再做一次LL旋转，即左旋转
    return this.rotationRR(node);
}

插入节点

• 向AVL树插入节点和在BST中是一样的
• 除了插入节点外，我们还要验证插入后树是否还是平衡的
• 如果不是，就要进行必要的旋转操作

插入节点

  insert(key) {
    this.root = this.insertNode(this.root, key);
  }

  insertNode(node, key) {
    if (node == null) {
      return new Node(key);
    } if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      node.left = this.insertNode(node.left, key);
    } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      node.right = this.insertNode(node.right, key);
    } else {
      return node; // duplicated key
    }
    // verify if tree is balanced
    const balanceFactor = this.getBalanceFactor(node);
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
      if (this.compareFn(key, node.left.key) === Compare.LESS_THAN) {
        // Left left case
        node = this.rotationLL(node);
      } else {
        // Left right case
        return this.rotationLR(node);
      }
    }
    if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
      if (this.compareFn(key, node.right.key) === Compare.BIGGER_THAN) {
        // Right right case
        node = this.rotationRR(node);
      } else {
        // Right left case
        return this.rotationRL(node);
      }
    }
    return node;
  }

删除节点

• 从AVL树移除节点和在BST中是一样的
• 除了移除节点外，我们还要验证移除后树是否还是平衡的
• 如果不是，就要进行必要的旋转操作

删除节点

  removeNode(node, key) {
    node = super.removeNode(node, key); // {1}
    if (node == null) {
      return node; // null，不需要进行平衡
    }
    // verify if tree is balanced
    const balanceFactor = this.getBalanceFactor(node);
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
      // Left left case
      if (
        this.getBalanceFactor(node.left) === BalanceFactor.BALANCED
        || this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT
      ) {
        return this.rotationLL(node);
      }
      // Left right case
      if (this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
        return this.rotationLR(node.left);
      }
    }
    if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
      // Right right case
      if (
        this.getBalanceFactor(node.right) === BalanceFactor.BALANCED
        || this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT
      ) {
        return this.rotationRR(node);
      }
      // Right left case
      if (this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
        return this.rotationRL(node.right);
      }
    }
    return node;
  }

AVL树

• AVL树插入和移除节点可能会造成旋转
• 插入和删除频率较低， AVL树较好

红黑树

• 多次插入和删除的自平衡树
• 每个节点不是红的就是黑的
• 树的根节点是黑的；
• 所有叶节点都是黑的（用NULL引用表示的节点）
• 如果一个节点是红的，那么它的两个子节点都是黑的
• 不能有两个相邻的红节点，一个红节点不能有红的父节点或子节点
• 从给定的节点到它的后代节点（NULL叶节点）的所有路径包含相同数量的黑色节点

创建节点

• 存储节点值，并要指向左子节点和右子节点

class Node {   
    constructor(key) {     
        this.key = key; // 节点值    
        this.left = null; // 指向左子节点    
        this.right = null; // 指向右子节点  
    } 
}

class RedBlackNode extends Node {   
    constructor(key) {     
        super(key);     
        this.key = key;     
        this.color = Colors.RED;     
        this.parent = null; 
    }   
    isRed() {     
        return this.color === Colors.RED;   
    } 
}

创建树

class RedBlackTree extends BinarySearchTree {
    constructor(compareFn = defaultCompare) {
         super(compareFn);     
         this.compareFn = compareFn;     
         this.root = null;   
    } 
} 

插入

• 向红黑树插入节点和在二叉搜索树中是一样的
• 除了插入的代码，还要在插入后给节点应用一种颜色
• 验证树是否满足红黑树的条件以及是否还是自平衡的

插入

insert(key) {
  if (this.root == null) {    
      this.root = new RedBlackNode(key);      
      this.root.color = Colors.BLACK;    
  } else {     
      const newNode = this.insertNode(this.root, key); 
      this.fixTreeProperties(newNode); 
  }
}
insertNode(node, key) {
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {       
        if (node.left == null) {           
            node.left = new RedBlackNode(key);
            node.left.parent = node; 
            return node.left;     
        }       
        else {           
            return this.insertNode(node.left, key);
        }   
    }   else if (node.right == null) { 
        node.right = new RedBlackNode(key);
        node.right.parent = node;      
        return node.right;    
    }   else {       
        return this.insertNode(node.right, key);   
    } 
}

验证红黑树属性

验证红黑树属性

验证红黑树属性

验证红黑树属性

fixTreeProperties(node) {   
    while (node && node.parent && node.parent.color.isRed() 
      && node.color !== Colors.BLACK) {       
          let parent = node.parent;        
          const grandParent = parent.parent;       
          // 情形A：父节点是左侧子节点      
          if (grandParent && grandParent.left === parent) { 
                const uncle = grandParent.right; 
                // 情形1A：叔节点也是红色——只需要重新填色          
                if (uncle && uncle.color === Colors.RED) { 
                    grandParent.color = Colors.RED; 
                    parent.color = Colors.BLACK;               
                    uncle.color = Colors.BLACK;               
                    node = grandParent;            
                } else {                
                    // 情形2A：节点是右侧子节点——左旋转   
                    if (node === parent.right) {   
                        this.rotationRR(parent);    
                        node = parent;   
                        parent = node.parent;  
                    }
                    // 情形3A：节点是左侧子节点——右旋转   
                    this.rotationLL(grandParent);
                    parent.color = Colors.BLACK; 
                    grandParent.color = Colors.RED;  
                    node = parent;  
                } 
            } else { // 情形B：父节点是右侧子节点         
            const uncle = grandParent.left;          
            // 情形1B：叔节点是红色——只需要重新填色         
            if (uncle && uncle.color === Colors.RED) { 
                grandParent.color = Colors.RED;              
                parent.color = Colors.BLACK;              
                uncle.color = Colors.BLACK;              
                node = grandParent;          
            }  else {              
                // 情形2B：节点是左侧子节点——右旋转             
                if (node === parent.left) {   
                    this.rotationLL(parent); 
                    node = parent;   
                    parent = node.parent; 
                }
                // 情形3B：节点是右侧子节点——左旋转        
                this.rotationRR(grandParent); 
                parent.color = Colors.BLACK; 
                grandParent.color = Colors.RED;
                node = parent; 
            }       
        }   
    }   
    this.root.color = Colors.BLACK; 
}    

红黑树旋转

• 逻辑和AVL树是一样
• 保存了父节点的引用,保存了父节点的引用

左-左旋转（右旋转）

rotationLL(node) {   
    const tmp = node.left
    node.left = tmp.right;   
    if (tmp.right && tmp.right.key) { 
        tmp.right.parent = node;  
    }   
    tmp.parent = node.parent;   
    if (!node.parent) {       
        this.root = tmp;   
    }  else {       
        if (node === node.parent.left) { 
            node.parent.left = tmp;      
        }  else { 
            node.parent.right = tmp;      
        }   
    }   
    tmp.right = node; node.parent = tmp;
} 

右-右旋转（左旋转）

rotationRR(node) {   
    const tmp = node.right;   
    node.right = tmp.left;   
    if (tmp.left && tmp.left.key) { 
        tmp.left.parent = node;  
    }   
    tmp.parent = node.parent;   
    if (!node.parent) {       
        this.root = tmp;   
    }   else {       
        if (node === node.parent.left) { 
            node.parent.left = tmp;      
        }   else { 
            node.parent.right = tmp;      
        }   
    }   
    tmp.left = node; node.parent = tmp; 
}

任务

设计一个AVL树，向树中插入1,2,3,4,5,6,7,8,9,10,分别用先序、中序、后序方式遍历该树。