美文网首页
第五周上:Balanced Search Trees

第五周上:Balanced Search Trees

作者: Lynn_4f26 | 来源:发表于2020-04-09 15:18 被阅读0次

    1. 2-3 search trees

    1. 每个Node有1或2个key

      • 2-node:one key,two children
      • 3-node:two keys,three children
    2. Perfect balance:

      • 每一条path,从root到null-link都是相同长度
    3. Symmetric order

      • 横向从左到右升序
    4. Search

      • search key与各个Node的key比较
      • 沿着对应的link(recursively),直到找到相同的key
    5. Insertion

      • 若每个key都已经有2个key,将新key加入这个3-node形成临时的4-node

      • 将这个4-node中间值的key晋升为parent

      • 重复直到结束

      • 当这条search path从root起的每一个node都是2-node,那么再加入一个key,length+1

    2. Red-Black BSTs

    Represent 2-3 tree as a BST

    1. Definition:

      • 每一个Node最多只有一个red-link
      • 每一条path从root到null-link都有相同数量的black-links
      • Red-link只在左侧
      • 当将red-link平方,red-black BST就是2-3 tree
    2. Insertion

      1. 找到的null-link的parent node只有black-link

        • 若key小于parent node,带着red-link加在左边就完成
        • 若key大于parent node,带着red-link加在右边,再rotate left即可
      2. 找到的null-link的parent node已经有red-link(相当于在2-3tree中,3-node要临时变4-node)

        • case 1(larger:已有a,b(parent),插入c):找到null-link,加入新的node(key=c, red-link),然后flip color
        • case 2(smaller:已有b,c(parent),插入a):找到null-link,加入新的node(key=a, red-link)。现在b有两个red-links,不符合规定。c进行rotate right操作,回归case 1,然后flip color
        • case 3(middle:已有a,c(parent),插入b):找到null-link,加入新的node(key=b, red-link)。此时red-link在a的右侧,不符合规定。b进行rotate left,回归case2,然后c进行rotate right操作,最后flip color
    3. Java implementation

      public class RBtree<Key extends Comparable<Key>, Value>{
      
       private static final boolean RED = true;
       private static final boolean BLACK = false;
       private Node root; // root of BST
      
       private class Node{
           Key key;
           Value val;
           Node left, right;
           boolean color;  // color of parent link
      
           public Node(Key key, Value val, boolean color){
               this.key = key;
               this.val = val;
               this.color = color;
           }
       }
      
       public void put(Key key, Value val){
            root = put(root, key, val);
          }
      
       private Node put(Node h, Key key, Value val){
           // find the null-link, insert at bottom (and color it red)
           if(h == null){ 
               return new Node(key, val, RED);
           }
      
           int cmp = key.compareTo(x.key);
           if(cmp < 0){
               h.left = put(h.left, key, val);
           }else if(cmp > 0){
               h.right = put(h.right, key, val);
           }else{
               h.val = val;
           }
      
           // Right child red, left child black: rotate left.
           if(isRed(h.right) && !isRed(h.left)){
               h = rotateLeft(h);
           }
           // Left child, left-left grandchild red: rotate right.
           if(isRed(h.left) && isRed(h.left.left)){
               h = rotateRight(h);
           }
           // Both children red: flip colors.
           if(isRed(h.left) && isRed(h.right)){
               flipColor(h);
           }
      
           return h;
      
       }
      
       private boolean isRed(Node x){
           if(x == null){
               return false;
           }
           return x.color == RED;
       }
      
       // Orient a (temporarily) right-leaning red link to lean left.
       private Node rotateLeft(Node h){
           // assert isRed(h.right);
           Node x = h.right;
           h.right = x.left;
           x.left = h;
           x.color = h.color;
           h.color = RED;
           return x
       }
      
       // Orient a left-leaning red link to (temporarily) lean right.
       private Node rotateRight(Node h){
           // assert isRed(h.left);
           Node x = h.left;
           h.left = x.right;
           x.right = h;
           x.color = h.color;
           h.color = RED;
           return x;
      
       }
      
       // Recolor to split a (temporary) 4-node.
       private void flipColors(Node h){
           // assert !isRed(h);
           // assert isRed(h.left);
           // assert isRed(h.right);
           h.color = RED;
           h.left.color = BLACK;
           h.right.color = BLACK;
       }
      
       public Value get(Key key){
           Node x = root;
           while(x != null){
               int cmp = key.compareTo(x.key);
               if(cmp < 0){
                   x = x.left;
               }else if(cmp > 0){
                   x = x.right;
               }else{
                   return null;
               }
           }
       } 
      }
      

    相关文章

      网友评论

          本文标题:第五周上:Balanced Search Trees

          本文链接:https://www.haomeiwen.com/subject/ycycmhtx.html