Package org.apache.hadoop.hbase.util

Class AvlUtil.AvlTree

java.lang.Object
org.apache.hadoop.hbase.util.AvlUtil.AvlTree
Enclosing class:
AvlUtil
@Private public static class AvlUtil.AvlTree extends Object
Helper class that allows to create and manipulate an AVL Tree

  • Constructor Details

  • Method Details

    • get

      public static <TNode extends AvlUtil.AvlNode> TNode get(TNode root, Object key, AvlUtil.AvlKeyComparator<TNode> keyComparator)
      Return the node that matches the specified key or null in case of node not found.
      Parameters:
      root - the current root of the tree
      key - the key for the node we are trying to find
      keyComparator - the comparator to use to match node and key
      Returns:
      the node that matches the specified key or null in case of node not found.

    • getFirst

      public static <TNode extends AvlUtil.AvlNode> TNode getFirst(TNode root)
      Return the first node of the tree.
      Parameters:
      root - the current root of the tree
      Returns:
      the first (min) node of the tree

    • getLast

      public static <TNode extends AvlUtil.AvlNode> TNode getLast(TNode root)
      Return the last node of the tree.
      Parameters:
      root - the current root of the tree
      Returns:
      the last (max) node of the tree

    • insert

      public static <TNode extends AvlUtil.AvlNode> TNode insert(TNode root, TNode node)
      Insert a node into the tree. It uses the AvlNode.compareTo() for ordering. NOTE: The node must not be already in the tree.
      Parameters:
      root - the current root of the tree
      node - the node to insert
      Returns:
      the new root of the tree

    • insert

      public static <TNode extends AvlUtil.AvlNode> TNode insert(TNode root, Object key, AvlUtil.AvlKeyComparator<TNode> keyComparator, AvlUtil.AvlInsertOrReplace<TNode> insertOrReplace)
      Insert a node into the tree. This is useful when you want to create a new node or replace the content depending if the node already exists or not. Using AvlInsertOrReplace class you can return the node to add/replace.
      Parameters:
      root - the current root of the tree
      key - the key for the node we are trying to insert
      keyComparator - the comparator to use to match node and key
      insertOrReplace - the class to use to insert or replace the node
      Returns:
      the new root of the tree

    • removeMin

      private static <TNode extends AvlUtil.AvlNode> TNode removeMin(TNode p)

    • remove

      public static <TNode extends AvlUtil.AvlNode> TNode remove(TNode root, Object key, AvlUtil.AvlKeyComparator<TNode> keyComparator)
      Removes the node matching the specified key from the tree
      Parameters:
      root - the current root of the tree
      key - the key for the node we are trying to find
      keyComparator - the comparator to use to match node and key
      Returns:
      the new root of the tree

    • remove

      public static <TNode extends AvlUtil.AvlNode> TNode remove(TNode root, Object key, AvlUtil.AvlKeyComparator<TNode> keyComparator, AtomicBoolean removed)
      Removes the node matching the specified key from the tree
      Parameters:
      root - the current root of the tree
      key - the key for the node we are trying to find
      keyComparator - the comparator to use to match node and key
      removed - will be set to true if the node was found and removed, otherwise false
      Returns:
      the new root of the tree

    • visit

      public static <TNode extends AvlUtil.AvlNode> void visit(TNode root, AvlUtil.AvlNodeVisitor<TNode> visitor)
      Visit each node of the tree
      Parameters:
      root - the current root of the tree
      visitor - the AvlNodeVisitor instance

    • balance

      private static <TNode extends AvlUtil.AvlNode> TNode balance(TNode p)

    • rotateRight

      private static <TNode extends AvlUtil.AvlNode> TNode rotateRight(TNode p)

    • rotateLeft

      private static <TNode extends AvlUtil.AvlNode> TNode rotateLeft(TNode q)

    • fixHeight

      private static <TNode extends AvlUtil.AvlNode> void fixHeight(TNode node)

    • height

      private static <TNode extends AvlUtil.AvlNode> int height(TNode node)

    • balanceFactor

      private static <TNode extends AvlUtil.AvlNode> int balanceFactor(TNode node)