Repairs crash in RTreeBase::Node::LeastAreaEnlargement

This CL was originally uploaded at
https://codereview.chromium.org/269513002 but was reverted due to a high
number of crash reports on Windows. The issue was that RTree::Insert()
would remove duplicate nodes before re-inserting them, but didn't handle
the corner case where the root node would end up as a non-leaf node with
only one child. RTree::Remove() did the right thing in this case, which
is to remove the root and replace it with its solitary child, but
RTree::Insert() did not. This lead to a situation with invalid trees
being created that would ultimately lead to a crash on a subsequent
call to RTree::Insert(). A short unit test that reproduced the crash
is included.

BUG=384736

Review URL: https://codereview.chromium.org/342723002

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@278227 0039d316-1c4b-4281-b951-d872f2087c98

8 files changed, 1780 insertions, 1525 deletions

diff --git a/ui/gfx/geometry/r_tree.cc b/ui/gfx/geometry/r_tree.cc
deleted file mode 100644
index 7fa0955..0000000
--- a/ui/gfx/geometry/r_tree.cc
+++ /dev/null
@@ -1,750 +0,0 @@
-// Copyright 2014 The Chromium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file.
-
-#include "ui/gfx/geometry/r_tree.h"
-
-#include <algorithm>
-#include <limits>
-
-#include "base/logging.h"
-
-namespace {
-
-// Returns the center coordinates of the given rectangle.
-gfx::Vector2d CenterOfRect(const gfx::Rect& rect) {
-  return rect.OffsetFromOrigin() +
-         gfx::Vector2d(rect.width() / 2, rect.height() / 2);
-}
-}
-
-namespace gfx {
-
-RTree::Node::Node(int level) : level_(level), parent_(NULL), key_(0) {
-}
-
-RTree::Node::Node(const Rect& rect, intptr_t key)
-    : rect_(rect), level_(-1), parent_(NULL), key_(key) {
-}
-
-RTree::Node::~Node() {
-  Clear();
-}
-
-void RTree::Node::Clear() {
-  // Iterate through children and delete them all.
-  children_.clear();
-  key_ = 0;
-}
-
-void RTree::Node::Query(const Rect& query_rect,
-                        base::hash_set<intptr_t>* matches_out) const {
-  // Check own bounding box for intersection, can cull all children if no
-  // intersection.
-  if (!rect_.Intersects(query_rect)) {
-    return;
-  }
-
-  // Conversely if we are completely contained within the query rect we can
-  // confidently skip all bounds checks for ourselves and all our children.
-  if (query_rect.Contains(rect_)) {
-    GetAllValues(matches_out);
-    return;
-  }
-
-  // We intersect the query rect but we are not are not contained within it.
-  // If we are a record node, then add our record value. Otherwise we must
-  // query each of our children in turn.
-  if (key_) {
-    DCHECK_EQ(level_, -1);
-    matches_out->insert(key_);
-  } else {
-    for (size_t i = 0; i < children_.size(); ++i) {
-      // Sanity-check our children.
-      Node* node = children_[i];
-      DCHECK_EQ(node->parent_, this);
-      DCHECK_EQ(level_ - 1, node->level_);
-      DCHECK(rect_.Contains(node->rect_));
-      node->Query(query_rect, matches_out);
-    }
-  }
-}
-
-void RTree::Node::RecomputeBounds() {
-  RecomputeBoundsNoParents();
-  // Recompute our parent's bounds recursively up to the root.
-  if (parent_) {
-    parent_->RecomputeBounds();
-  }
-}
-
-void RTree::Node::RemoveNodesForReinsert(size_t number_to_remove,
-                                         ScopedVector<Node>* nodes) {
-  DCHECK_GE(children_.size(), number_to_remove);
-
-  // Sort our children by their distance from the center of their rectangles to
-  // the center of our bounding rectangle.
-  std::sort(children_.begin(),
-            children_.end(),
-            &RTree::Node::CompareCenterDistanceFromParent);
-
-  // Add lowest distance nodes from our children list to the returned vector.
-  nodes->insert(
-      nodes->end(), children_.begin(), children_.begin() + number_to_remove);
-  // Remove those same nodes from our list, without deleting them.
-  children_.weak_erase(children_.begin(), children_.begin() + number_to_remove);
-}
-
-size_t RTree::Node::RemoveChild(Node* child_node, ScopedVector<Node>* orphans) {
-  // Should actually be one of our children.
-  DCHECK_EQ(child_node->parent_, this);
-
-  // Add children of child_node to the orphans vector.
-  orphans->insert(orphans->end(),
-                  child_node->children_.begin(),
-                  child_node->children_.end());
-  // Remove without deletion those children from the child_node vector.
-  child_node->children_.weak_clear();
-
-  // Find an iterator to this Node in our own children_ vector.
-  ScopedVector<Node>::iterator child_it = children_.end();
-  for (size_t i = 0; i < children_.size(); ++i) {
-    if (children_[i] == child_node) {
-      child_it = children_.begin() + i;
-      break;
-    }
-  }
-  // Should have found the pointer in our children_ vector.
-  DCHECK(child_it != children_.end());
-  // Remove without deleting the child node from our children_ vector.
-  children_.weak_erase(child_it);
-
-  return children_.size();
-}
-
-scoped_ptr<RTree::Node> RTree::Node::RemoveAndReturnLastChild() {
-  if (!children_.size())
-    return scoped_ptr<Node>();
-
-  scoped_ptr<Node> last_child(children_[children_.size() - 1]);
-  DCHECK_EQ(last_child->parent_, this);
-  children_.weak_erase(children_.begin() + children_.size() - 1);
-  // Invalidate parent, as this child may even become the new root.
-  last_child->parent_ = NULL;
-  return last_child.Pass();
-}
-
-// Uses the R*-Tree algorithm CHOOSELEAF proposed by Beckmann et al.
-RTree::Node* RTree::Node::ChooseSubtree(Node* node) {
-  // Should never be called on a record node.
-  DCHECK(!key_);
-  DCHECK(level_ >= 0);
-  DCHECK(node);
-
-  // If we are a parent of nodes on the provided node level, we are done.
-  if (level_ == node->level_ + 1)
-    return this;
-
-  // We are an internal node, and thus guaranteed to have children.
-  DCHECK_GT(children_.size(), 0U);
-
-  // Iterate over all children to find best candidate for insertion.
-  Node* best_candidate = NULL;
-
-  // Precompute a vector of expanded rects, used both by LeastOverlapIncrease
-  // and LeastAreaEnlargement.
-  std::vector<Rect> expanded_rects;
-  expanded_rects.reserve(children_.size());
-  for (size_t i = 0; i < children_.size(); ++i) {
-    Rect expanded_rect(node->rect_);
-    expanded_rect.Union(children_[i]->rect_);
-    expanded_rects.push_back(expanded_rect);
-  }
-
-  // For parents of leaf nodes, we pick the node that will cause the least
-  // increase in overlap by the addition of this new node. This may detect a
-  // tie, in which case it will return NULL.
-  if (level_ == 1)
-    best_candidate = LeastOverlapIncrease(node->rect_, expanded_rects);
-
-  // For non-parents of leaf nodes, or for parents of leaf nodes with ties in
-  // overlap increase, we choose the subtree with least area enlargement caused
-  // by the addition of the new node.
-  if (!best_candidate)
-    best_candidate = LeastAreaEnlargement(node->rect_, expanded_rects);
-
-  DCHECK(best_candidate);
-  return best_candidate->ChooseSubtree(node);
-}
-
-RTree::Node* RTree::Node::LeastAreaEnlargement(
-    const Rect& node_rect,
-    const std::vector<Rect>& expanded_rects) {
-  Node* best_node = NULL;
-  int least_area_enlargement = std::numeric_limits<int>::max();
-  for (size_t i = 0; i < children_.size(); ++i) {
-    Node* candidate_node = children_[i];
-    int area_change = expanded_rects[i].size().GetArea() -
-                      candidate_node->rect_.size().GetArea();
-    if (area_change < least_area_enlargement) {
-      best_node = candidate_node;
-      least_area_enlargement = area_change;
-    } else if (area_change == least_area_enlargement) {
-      // Ties are broken by choosing entry with least area.
-      DCHECK(best_node);
-      if (candidate_node->rect_.size().GetArea() <
-          best_node->rect_.size().GetArea()) {
-        best_node = candidate_node;
-      }
-    }
-  }
-
-  DCHECK(best_node);
-  return best_node;
-}
-
-RTree::Node* RTree::Node::LeastOverlapIncrease(
-    const Rect& node_rect,
-    const std::vector<Rect>& expanded_rects) {
-  Node* best_node = NULL;
-  bool has_tied_node = false;
-  int least_overlap_increase = std::numeric_limits<int>::max();
-  for (size_t i = 0; i < children_.size(); ++i) {
-    int overlap_increase =
-        OverlapIncreaseToAdd(node_rect, i, expanded_rects[i]);
-    if (overlap_increase < least_overlap_increase) {
-      least_overlap_increase = overlap_increase;
-      best_node = children_[i];
-      has_tied_node = false;
-    } else if (overlap_increase == least_overlap_increase) {
-      has_tied_node = true;
-      // If we are tied at zero there is no possible better overlap increase,
-      // so we can report a tie early.
-      if (overlap_increase == 0) {
-        return NULL;
-      }
-    }
-  }
-
-  // If we ended up with a tie return NULL to report it.
-  if (has_tied_node)
-    return NULL;
-
-  return best_node;
-}
-
-int RTree::Node::OverlapIncreaseToAdd(const Rect& rect,
-                                      size_t candidate,
-                                      const Rect& expanded_rect) {
-  Node* candidate_node = children_[candidate];
-
-  // Early-out option for when rect is contained completely within candidate.
-  if (candidate_node->rect_.Contains(rect)) {
-    return 0;
-  }
-
-  int total_original_overlap = 0;
-  int total_expanded_overlap = 0;
-
-  // Now calculate overlap with all other rects in this node.
-  for (size_t i = 0; i < children_.size(); ++i) {
-    // Skip calculating overlap with the candidate rect.
-    if (i == candidate)
-      continue;
-    Node* overlap_node = children_[i];
-    Rect overlap_rect = candidate_node->rect_;
-    overlap_rect.Intersect(overlap_node->rect_);
-    total_original_overlap += overlap_rect.size().GetArea();
-    Rect expanded_overlap_rect = expanded_rect;
-    expanded_overlap_rect.Intersect(overlap_node->rect_);
-    total_expanded_overlap += expanded_overlap_rect.size().GetArea();
-  }
-
-  // Compare this overlap increase with best one to date, update best.
-  int overlap_increase = total_expanded_overlap - total_original_overlap;
-  return overlap_increase;
-}
-
-size_t RTree::Node::AddChild(Node* node) {
-  DCHECK(node);
-  // Sanity-check that the level of the child being added is one more than ours.
-  DCHECK_EQ(level_ - 1, node->level_);
-  node->parent_ = this;
-  children_.push_back(node);
-  rect_.Union(node->rect_);
-  return children_.size();
-}
-
-RTree::Node* RTree::Node::Split(size_t min_children, size_t max_children) {
-  // Please don't attempt to split a record Node.
-  DCHECK(!key_);
-  // We should have too many children to begin with.
-  DCHECK_GT(children_.size(), max_children);
-  // First determine if splitting along the horizontal or vertical axis. We
-  // sort the rectangles of our children by lower then upper values along both
-  // horizontal and vertical axes.
-  std::vector<Node*> vertical_sort(children_.get());
-  std::vector<Node*> horizontal_sort(children_.get());
-  std::sort(vertical_sort.begin(),
-            vertical_sort.end(),
-            &RTree::Node::CompareVertical);
-  std::sort(horizontal_sort.begin(),
-            horizontal_sort.end(),
-            &RTree::Node::CompareHorizontal);
-
-  // We will be examining the bounding boxes of different splits of our children
-  // sorted along each axis. Here we precompute the bounding boxes of these
-  // distributions. For the low bounds the ith element can be considered the
-  // union of all rects [0,i] in the relevant sorted axis array.
-  std::vector<Rect> low_vertical_bounds;
-  std::vector<Rect> low_horizontal_bounds;
-  BuildLowBounds(vertical_sort,
-                 horizontal_sort,
-                 &low_vertical_bounds,
-                 &low_horizontal_bounds);
-
-  // For the high bounds the ith element can be considered the union of all
-  // rects [i, children_.size()) in the relevant sorted axis array.
-  std::vector<Rect> high_vertical_bounds;
-  std::vector<Rect> high_horizontal_bounds;
-  BuildHighBounds(vertical_sort,
-                  horizontal_sort,
-                  &high_vertical_bounds,
-                  &high_horizontal_bounds);
-
-  bool is_vertical_split = ChooseSplitAxis(low_vertical_bounds,
-                                           high_vertical_bounds,
-                                           low_horizontal_bounds,
-                                           high_horizontal_bounds,
-                                           min_children,
-                                           max_children);
-
-  // Lastly we determine optimal index and do the split.
-  Node* sibling = NULL;
-  if (is_vertical_split) {
-    size_t split_index = ChooseSplitIndex(
-        min_children, max_children, low_vertical_bounds, high_vertical_bounds);
-    sibling = DivideChildren(
-        low_vertical_bounds, high_vertical_bounds, vertical_sort, split_index);
-  } else {
-    size_t split_index = ChooseSplitIndex(min_children,
-                                          max_children,
-                                          low_horizontal_bounds,
-                                          high_horizontal_bounds);
-    sibling = DivideChildren(low_horizontal_bounds,
-                             high_horizontal_bounds,
-                             horizontal_sort,
-                             split_index);
-  }
-
-  return sibling;
-}
-
-// static
-void RTree::Node::BuildLowBounds(const std::vector<Node*>& vertical_sort,
-                                 const std::vector<Node*>& horizontal_sort,
-                                 std::vector<Rect>* vertical_bounds,
-                                 std::vector<Rect>* horizontal_bounds) {
-  DCHECK_EQ(vertical_sort.size(), horizontal_sort.size());
-  Rect vertical_bounds_rect;
-  Rect horizontal_bounds_rect;
-  vertical_bounds->reserve(vertical_sort.size());
-  horizontal_bounds->reserve(horizontal_sort.size());
-  for (size_t i = 0; i < vertical_sort.size(); ++i) {
-    vertical_bounds_rect.Union(vertical_sort[i]->rect_);
-    horizontal_bounds_rect.Union(horizontal_sort[i]->rect_);
-    vertical_bounds->push_back(vertical_bounds_rect);
-    horizontal_bounds->push_back(horizontal_bounds_rect);
-  }
-}
-
-// static
-void RTree::Node::BuildHighBounds(const std::vector<Node*>& vertical_sort,
-                                  const std::vector<Node*>& horizontal_sort,
-                                  std::vector<Rect>* vertical_bounds,
-                                  std::vector<Rect>* horizontal_bounds) {
-  DCHECK_EQ(vertical_sort.size(), horizontal_sort.size());
-  Rect vertical_bounds_rect;
-  Rect horizontal_bounds_rect;
-  vertical_bounds->resize(vertical_sort.size());
-  horizontal_bounds->resize(horizontal_sort.size());
-  for (int i = static_cast<int>(vertical_sort.size()) - 1; i >= 0; --i) {
-    vertical_bounds_rect.Union(vertical_sort[i]->rect_);
-    horizontal_bounds_rect.Union(horizontal_sort[i]->rect_);
-    vertical_bounds->at(i) = vertical_bounds_rect;
-    horizontal_bounds->at(i) = horizontal_bounds_rect;
-  }
-}
-
-// static
-bool RTree::Node::ChooseSplitAxis(
-    const std::vector<Rect>& low_vertical_bounds,
-    const std::vector<Rect>& high_vertical_bounds,
-    const std::vector<Rect>& low_horizontal_bounds,
-    const std::vector<Rect>& high_horizontal_bounds,
-    size_t min_children,
-    size_t max_children) {
-  // Examine the possible distributions of each sorted list by iterating through
-  // valid split points p, min_children <= p <= max_children - min_children, and
-  // computing the sums of the margins of the bounding boxes in each group.
-  // Smallest margin sum will determine split axis.
-  int smallest_horizontal_margin_sum = std::numeric_limits<int>::max();
-  int smallest_vertical_margin_sum = std::numeric_limits<int>::max();
-  for (size_t p = min_children; p < max_children - min_children; ++p) {
-    int horizontal_margin_sum =
-        low_horizontal_bounds[p].width() + low_horizontal_bounds[p].height() +
-        high_horizontal_bounds[p].width() + high_horizontal_bounds[p].height();
-    int vertical_margin_sum =
-        low_vertical_bounds[p].width() + low_vertical_bounds[p].height() +
-        high_vertical_bounds[p].width() + high_vertical_bounds[p].height();
-    // Update margin minima if necessary.
-    smallest_horizontal_margin_sum =
-        std::min(horizontal_margin_sum, smallest_horizontal_margin_sum);
-    smallest_vertical_margin_sum =
-        std::min(vertical_margin_sum, smallest_vertical_margin_sum);
-  }
-
-  // Split along the axis perpendicular to the axis with the overall smallest
-  // margin sum. Meaning the axis sort resulting in two boxes with the smallest
-  // combined margin will become the axis along which the sorted rectangles are
-  // distributed to the two Nodes.
-  bool is_vertical_split =
-      smallest_vertical_margin_sum < smallest_horizontal_margin_sum;
-  return is_vertical_split;
-}
-
-RTree::Node* RTree::Node::DivideChildren(
-    const std::vector<Rect>& low_bounds,
-    const std::vector<Rect>& high_bounds,
-    const std::vector<Node*>& sorted_children,
-    size_t split_index) {
-  Node* sibling = new Node(level_);
-  sibling->parent_ = parent_;
-  rect_ = low_bounds[split_index - 1];
-  sibling->rect_ = high_bounds[split_index];
-  // Our own children_ vector is unsorted, so we wipe it out and divide the
-  // sorted bounds rects between ourselves and our sibling.
-  children_.weak_clear();
-  children_.insert(children_.end(),
-                   sorted_children.begin(),
-                   sorted_children.begin() + split_index);
-  sibling->children_.insert(sibling->children_.end(),
-                            sorted_children.begin() + split_index,
-                            sorted_children.end());
-
-  // Fix up sibling parentage or it's gonna be an awkward Thanksgiving.
-  for (size_t i = 0; i < sibling->children_.size(); ++i) {
-    sibling->children_[i]->parent_ = sibling;
-  }
-
-  return sibling;
-}
-
-void RTree::Node::SetRect(const Rect& rect) {
-  // Record nodes only, please.
-  DCHECK(key_);
-  rect_ = rect;
-}
-
-// Returns all contained record_node values for this node and all children.
-void RTree::Node::GetAllValues(base::hash_set<intptr_t>* matches_out) const {
-  if (key_) {
-    DCHECK_EQ(level_, -1);
-    matches_out->insert(key_);
-  } else {
-    for (size_t i = 0; i < children_.size(); ++i) {
-      Node* node = children_[i];
-      // Sanity-check our children.
-      DCHECK_EQ(node->parent_, this);
-      DCHECK_EQ(level_ - 1, node->level_);
-      DCHECK(rect_.Contains(node->rect_));
-      node->GetAllValues(matches_out);
-    }
-  }
-}
-
-// static
-bool RTree::Node::CompareVertical(Node* a, Node* b) {
-  // Sort nodes by top coordinate first.
-  if (a->rect_.y() < b->rect_.y()) {
-    return true;
-  } else if (a->rect_.y() == b->rect_.y()) {
-    // If top coordinate is equal, sort by lowest bottom coordinate.
-    return a->rect_.height() < b->rect_.height();
-  }
-  return false;
-}
-
-// static
-bool RTree::Node::CompareHorizontal(Node* a, Node* b) {
-  // Sort nodes by left coordinate first.
-  if (a->rect_.x() < b->rect_.x()) {
-    return true;
-  } else if (a->rect_.x() == b->rect_.x()) {
-    // If left coordinate is equal, sort by lowest right coordinate.
-    return a->rect_.width() < b->rect_.width();
-  }
-  return false;
-}
-
-// Sort these two nodes by the distance of the center of their rects from the
-// center of their parent's rect. We don't bother with square roots because we
-// are only comparing the two values for sorting purposes.
-// static
-bool RTree::Node::CompareCenterDistanceFromParent(Node* a, Node* b) {
-  // This comparison assumes the nodes have the same parent.
-  DCHECK(a->parent_ == b->parent_);
-  // This comparison requires that each node have a parent.
-  DCHECK(a->parent_);
-  // Sanity-check level_ of these nodes is equal.
-  DCHECK_EQ(a->level_, b->level_);
-  // Also the parent of the nodes should have level one higher.
-  DCHECK_EQ(a->level_, a->parent_->level_ - 1);
-
-  // Find the parent.
-  Node* p = a->parent();
-
-  Vector2d p_center = CenterOfRect(p->rect_);
-  Vector2d a_center = CenterOfRect(a->rect_);
-  Vector2d b_center = CenterOfRect(b->rect_);
-
-  return (a_center - p_center).LengthSquared() <
-         (b_center - p_center).LengthSquared();
-}
-
-size_t RTree::Node::ChooseSplitIndex(size_t min_children,
-                                     size_t max_children,
-                                     const std::vector<Rect>& low_bounds,
-                                     const std::vector<Rect>& high_bounds) {
-  int smallest_overlap_area = std::numeric_limits<int>::max();
-  int smallest_combined_area = std::numeric_limits<int>::max();
-  size_t optimal_split_index = 0;
-  for (size_t p = min_children; p < max_children - min_children; ++p) {
-    Rect overlap_bounds = low_bounds[p];
-    overlap_bounds.Union(high_bounds[p]);
-    int overlap_area = overlap_bounds.size().GetArea();
-    if (overlap_area < smallest_overlap_area) {
-      smallest_overlap_area = overlap_area;
-      smallest_combined_area =
-          low_bounds[p].size().GetArea() + high_bounds[p].size().GetArea();
-      optimal_split_index = p;
-    } else if (overlap_area == smallest_overlap_area) {
-      // Break ties with smallest combined area of the two bounding boxes.
-      int combined_area =
-          low_bounds[p].size().GetArea() + high_bounds[p].size().GetArea();
-      if (combined_area < smallest_combined_area) {
-        smallest_combined_area = combined_area;
-        optimal_split_index = p;
-      }
-    }
-  }
-
-  // optimal_split_index currently points at the last element in the first set,
-  // so advance it by 1 to point at the first element in the second set.
-  return optimal_split_index + 1;
-}
-
-void RTree::Node::RecomputeBoundsNoParents() {
-  // Clear our rectangle, then reset it to union of our children.
-  rect_.SetRect(0, 0, 0, 0);
-  for (size_t i = 0; i < children_.size(); ++i) {
-    rect_.Union(children_[i]->rect_);
-  }
-}
-
-RTree::RTree(size_t min_children, size_t max_children)
-    : root_(new Node(0)),
-      min_children_(min_children),
-      max_children_(max_children) {
-  // R-Trees require min_children >= 2
-  DCHECK_GE(min_children_, 2U);
-  // R-Trees also require min_children <= max_children / 2
-  DCHECK_LE(min_children_, max_children_ / 2U);
-  root_.reset(new Node(0));
-}
-
-RTree::~RTree() {
-  Clear();
-}
-
-void RTree::Insert(const Rect& rect, intptr_t key) {
-  // Non-NULL keys, please.
-  DCHECK(key);
-
-  Node* record_node = NULL;
-  // Check if this key is already present in the tree.
-  base::hash_map<intptr_t, Node*>::iterator it = record_map_.find(key);
-  if (it != record_map_.end()) {
-    // We will re-use this node structure, regardless of re-insert or return.
-    record_node = it->second;
-    // If the new rect and the current rect are identical we can skip rest of
-    // Insert() as nothing has changed.
-    if (record_node->rect() == rect)
-      return;
-
-    // Remove the node from the tree in its current position.
-    RemoveNode(record_node);
-
-    // If we are replacing this key with an empty rectangle we just remove the
-    // old node from the list and return, thus preventing insertion of empty
-    // rectangles into our spatial database.
-    if (rect.IsEmpty()) {
-      record_map_.erase(it);
-      delete record_node;
-      return;
-    }
-
-    // Reset the rectangle to the new value.
-    record_node->SetRect(rect);
-  } else {
-    if (rect.IsEmpty())
-      return;
-    // Build a new record Node for insertion in to tree.
-    record_node = new Node(rect, key);
-    // Add this new node to our map, for easy retrieval later.
-    record_map_.insert(std::make_pair(key, record_node));
-  }
-
-  // Call internal Insert with this new node and allowing all re-inserts.
-  int starting_level = -1;
-  InsertNode(record_node, &starting_level);
-}
-
-void RTree::Remove(intptr_t key) {
-  // Search the map for the leaf parent that has the provided record.
-  base::hash_map<intptr_t, Node*>::iterator it = record_map_.find(key);
-  // If not in the map it's not in the tree, we're done.
-  if (it == record_map_.end())
-    return;
-
-  Node* node = it->second;
-  // Remove this node from the map.
-  record_map_.erase(it);
-  // Now remove it from the RTree.
-  RemoveNode(node);
-  delete node;
-
-  // Lastly check the root. If it has only one non-leaf child, delete it and
-  // replace it with its child.
-  if (root_->count() == 1 && root_->level() > 0) {
-    root_ = root_->RemoveAndReturnLastChild();
-  }
-}
-
-void RTree::Query(const Rect& query_rect,
-                  base::hash_set<intptr_t>* matches_out) const {
-  root_->Query(query_rect, matches_out);
-}
-
-void RTree::Clear() {
-  record_map_.clear();
-  root_.reset(new Node(0));
-}
-
-void RTree::InsertNode(Node* node, int* highest_reinsert_level) {
-  // Find the most appropriate parent to insert node into.
-  Node* parent = root_->ChooseSubtree(node);
-  DCHECK(parent);
-  // Verify ChooseSubtree returned a Node at the correct level.
-  DCHECK_EQ(parent->level(), node->level() + 1);
-  Node* insert_node = node;
-  Node* insert_parent = parent;
-  Node* needs_bounds_recomputed = insert_parent->parent();
-  ScopedVector<Node> reinserts;
-  // Attempt to insert the Node, if this overflows the Node we must handle it.
-  while (insert_parent &&
-         insert_parent->AddChild(insert_node) > max_children_) {
-    // If we have yet to re-insert nodes at this level during this data insert,
-    // and we're not at the root, R*-Tree calls for re-insertion of some of the
-    // nodes, resulting in a better balance on the tree.
-    if (insert_parent->parent() &&
-        insert_parent->level() > *highest_reinsert_level) {
-      insert_parent->RemoveNodesForReinsert(max_children_ / 3, &reinserts);
-      // Adjust highest_reinsert_level to this level.
-      *highest_reinsert_level = insert_parent->level();
-      // We didn't create any new nodes so we have nothing new to insert.
-      insert_node = NULL;
-      // RemoveNodesForReinsert() does not recompute bounds, so mark it.
-      needs_bounds_recomputed = insert_parent;
-      break;
-    }
-
-    // Split() will create a sibling to insert_parent both of which will have
-    // valid bounds, but this invalidates their parent's bounds.
-    insert_node = insert_parent->Split(min_children_, max_children_);
-    insert_parent = insert_parent->parent();
-    needs_bounds_recomputed = insert_parent;
-  }
-
-  // If we have a Node to insert, and we hit the root of the current tree,
-  // we create a new root which is the parent of the current root and the
-  // insert_node
-  if (!insert_parent && insert_node) {
-    Node* old_root = root_.release();
-    root_.reset(new Node(old_root->level() + 1));
-    root_->AddChild(old_root);
-    root_->AddChild(insert_node);
-  }
-
-  // Recompute bounds along insertion path.
-  if (needs_bounds_recomputed) {
-    needs_bounds_recomputed->RecomputeBounds();
-  }
-
-  // Complete re-inserts, if any.
-  for (size_t i = 0; i < reinserts.size(); ++i) {
-    InsertNode(reinserts[i], highest_reinsert_level);
-  }
-
-  // Clear out reinserts without deleting any of the children, as they have been
-  // re-inserted into the tree.
-  reinserts.weak_clear();
-}
-
-void RTree::RemoveNode(Node* node) {
-  // We need to remove this node from its parent.
-  Node* parent = node->parent();
-  // Record nodes are never allowed as the root, so we should always have a
-  // parent.
-  DCHECK(parent);
-  // Should always be a leaf that had the record.
-  DCHECK_EQ(parent->level(), 0);
-  ScopedVector<Node> orphans;
-  Node* child = node;
-
-  // Traverse up the tree, removing the child from each parent and deleting
-  // parent nodes, until we either encounter the root of the tree or a parent
-  // that still has sufficient children.
-  while (parent) {
-    size_t children_remaining = parent->RemoveChild(child, &orphans);
-    if (child != node)
-      delete child;
-
-    if (children_remaining >= min_children_)
-      break;
-
-    child = parent;
-    parent = parent->parent();
-  }
-
-  // If we stopped deleting nodes up the tree before encountering the root,
-  // we'll need to fix up the bounds from the first parent we didn't delete
-  // up to the root.
-  if (parent) {
-    parent->RecomputeBounds();
-  } else {
-    root_->RecomputeBounds();
-  }
-
-  // Now re-insert each of the orphaned nodes back into the tree.
-  for (size_t i = 0; i < orphans.size(); ++i) {
-    int starting_level = -1;
-    InsertNode(orphans[i], &starting_level);
-  }
-
-  // Clear out the orphans list without deleting any of the children, as they
-  // have been re-inserted into the tree.
-  orphans.weak_clear();
-}
-
-}  // namespace gfx
diff --git a/ui/gfx/geometry/r_tree.h b/ui/gfx/geometry/r_tree.h
index 7eb6991..53fd5c9 100644
--- a/ui/gfx/geometry/r_tree.h
+++ b/ui/gfx/geometry/r_tree.h
@@ -2,22 +2,7 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#ifndef UI_GFX_GEOMETRY_R_TREE_H_
-#define UI_GFX_GEOMETRY_R_TREE_H_
-
-#include <vector>
-
-#include "base/containers/hash_tables.h"
-#include "base/gtest_prod_util.h"
-#include "base/macros.h"
-#include "base/memory/scoped_ptr.h"
-#include "base/memory/scoped_vector.h"
-#include "ui/gfx/geometry/rect.h"
-#include "ui/gfx/gfx_export.h"
-
-namespace gfx {
-
-// Defines a heirarchical bounding rectangle data structure for Rect objects,
+// Defines a hierarchical bounding rectangle data structure for Rect objects,
 // associated with a generic unique key K for efficient spatial queries. The
 // R*-tree algorithm is used to build the trees. Based on the papers:
 //
@@ -27,270 +12,171 @@ namespace gfx {
 // N Beckmann, H-P Kriegel, R Schneider, B Seeger 'The R*-tree: an efficient and
 // robust access method for points and rectangles', Proc ACM SIGMOD Int Conf on
 // Management of Data, 322-331, 1990
-class GFX_EXPORT RTree {
+
+#ifndef UI_GFX_GEOMETRY_R_TREE_H_
+#define UI_GFX_GEOMETRY_R_TREE_H_
+
+#include "r_tree_base.h"
+
+namespace gfx {
+
+template <typename Key>
+class RTree : public RTreeBase {
  public:
+  typedef base::hash_set<Key> Matches;
+
+  // RTrees organize pairs of keys and rectangles in a hierarchical bounding
+  // box structure. This allows for queries of the tree within logarithmic time.
+  // |min_children| and |max_children| allows for adjustment of the average size
+  // of the nodes within RTree, which adjusts the base of the logarithm in the
+  // algorithm runtime. Some parts of insertion and deletion are polynomial
+  // in the size of the individual node, so the trade-off with larger nodes is
+  // potentially faster queries but slower insertions and deletions. Generally
+  // it is worth considering how much overlap between rectangles of different
+  // keys will occur in the tree, and trying to set |max_children| as a
+  // reasonable upper bound to the number of overlapping rectangles expected.
+  // Then |min_children| can bet set to a quantity slightly less than half of
+  // that.
   RTree(size_t min_children, size_t max_children);
   ~RTree();
 
   // Insert a new rect into the tree, associated with provided key. Note that if
-  // rect is empty, this rect will not actually be inserted. Duplicate keys
+  // |rect| is empty, the |key| will not actually be inserted. Duplicate keys
   // overwrite old entries.
-  void Insert(const Rect& rect, intptr_t key);
+  void Insert(const Rect& rect, Key key);
 
-  // If present, remove the supplied key from the tree.
-  void Remove(intptr_t key);
+  // If present, remove the supplied |key| from the tree.
+  void Remove(Key key);
 
-  // Fills a supplied list matches_out with all keys having bounding rects
-  // intersecting query_rect.
-  void Query(const Rect& query_rect,
-             base::hash_set<intptr_t>* matches_out) const;
+  // Fills |matches_out| with all keys having bounding rects intersecting
+  // |query_rect|.
+  void AppendIntersectingRecords(const Rect& query_rect,
+                                 Matches* matches_out) const;
 
-  // Removes all objects from the tree.
   void Clear();
 
  private:
-  // Private data structure class for storing internal nodes or leaves with keys
-  // of R-Trees. Note that "leaf" nodes can still have children, the children
-  // will all be Nodes with non-NULL record pointers.
-  class GFX_EXPORT Node {
-   public:
-    // Level counts from -1 for "record" Nodes, that is Nodes that wrap key
-    // values, to 0 for leaf Nodes, that is Nodes that only have record
-    // children, up to the root Node, which has level equal to the height of the
-    // tree.
-    explicit Node(int level);
-
-    // Builds a new record Node.
-    Node(const Rect& rect, intptr_t key);
-
-    virtual ~Node();
-
-    // Deletes all children and any attached record.
-    void Clear();
-
-    // Recursive call to build a list of rects that intersect the query_rect.
-    void Query(const Rect& query_rect,
-               base::hash_set<intptr_t>* matches_out) const;
-
-    // Recompute our bounds by taking the union of all children rects. Will then
-    // call RecomputeBounds() on our parent for recursive bounds recalculation
-    // up to the root.
-    void RecomputeBounds();
-
-    // Removes number_to_remove nodes from this Node, and appends them to the
-    // supplied list. Does not repair bounds upon completion.
-    void RemoveNodesForReinsert(size_t number_to_remove,
-                                ScopedVector<Node>* nodes);
-
-    // Given a pointer to a child node within this Node, remove it from our
-    // list. If that child had any children, append them to the supplied orphan
-    // list. Returns the new count of this node after removal. Does not
-    // recompute bounds, as this node itself may be removed if it now has too
-    // few children.
-    size_t RemoveChild(Node* child_node, ScopedVector<Node>* orphans);
-
-    // Does what it says on the tin. Returns NULL if no children. Does not
-    // recompute bounds.
-    scoped_ptr<Node> RemoveAndReturnLastChild();
-
-    // Given a node, returns the best fit node for insertion of that node at
-    // the nodes level().
-    Node* ChooseSubtree(Node* node);
-
-    // Adds the provided node to this Node. Returns the new count of records
-    // stored in the Node. Will recompute the bounds of this node after
-    // addition.
-    size_t AddChild(Node* node);
-
-    // Returns a sibling to this Node with at least min_children and no greater
-    // than max_children of this Node's children assigned to it, and having the
-    // same parent. Bounds will be valid on both Nodes after this call.
-    Node* Split(size_t min_children, size_t max_children);
-
-    // For record nodes only, to support re-insert, allows setting the rect.
-    void SetRect(const Rect& rect);
-
-    // Returns a pointer to the parent of this Node, or NULL if no parent.
-    Node* parent() const { return parent_; }
-
-    // 0 level() would mean that this Node is a leaf. 1 would mean that this
-    // Node has children that are leaves. Calling level() on root_ returns the
-    // height of the tree - 1. A level of -1 means that this is a Record node.
-    int level() const { return level_; }
-
-    const Rect& rect() const { return rect_; }
-
-    size_t count() const { return children_.size(); }
+  friend class RTreeTest;
+  friend class RTreeNodeTest;
 
-    intptr_t key() const { return key_; }
+  class Record : public RecordBase {
+   public:
+    Record(const Rect& rect, const Key& key);
+    virtual ~Record();
+    const Key& key() const { return key_; }
 
    private:
-    // Returns all records stored in this node and its children.
-    void GetAllValues(base::hash_set<intptr_t>* matches_out) const;
-
-    // Used for sorting Nodes along vertical and horizontal axes
-    static bool CompareVertical(Node* a, Node* b);
-
-    static bool CompareHorizontal(Node* a, Node* b);
-
-    static bool CompareCenterDistanceFromParent(Node* a, Node* b);
-
-    // Returns the increase in overlap value, as defined in Beckmann et al as
-    // the sum of the areas of the intersection of each |children_| rectangle
-    // (excepting the candidate child) with the argument rectangle. The
-    // expanded_rect argument is computed as the union of the candidate child
-    // rect and the argument rect, and is included here to avoid recomputation.
-    // Here the candidate child is indicated by index in |children_|, and
-    // expanded_rect is the alread-computed union of candidate's rect and
-    // rect.
-    int OverlapIncreaseToAdd(const Rect& rect,
-                             size_t candidate,
-                             const Rect& expanded_rect);
-
-    // Bounds recomputation without calling parents to do the same.
-    void RecomputeBoundsNoParents();
-
-    // Split() helper methods.
-    //
-    // Given two vectors of Nodes sorted by vertical or horizontal bounds, this
-    // function populates two vectors of Rectangles in which the ith element is
-    // the Union of all bounding rectangles [0,i] in the associated sorted array
-    // of Nodes.
-    static void BuildLowBounds(const std::vector<Node*>& vertical_sort,
-                               const std::vector<Node*>& horizontal_sort,
-                               std::vector<Rect>* vertical_bounds,
-                               std::vector<Rect>* horizontal_bounds);
-
-    // Given two vectors of Nodes sorted by vertical or horizontal bounds, this
-    // function populates two vectors of Rectangles in which the ith element is
-    // the Union of all bounding rectangles [i, count()) in the associated
-    // sorted array of Nodes.
-    static void BuildHighBounds(const std::vector<Node*>& vertical_sort,
-                                const std::vector<Node*>& horizontal_sort,
-                                std::vector<Rect>* vertical_bounds,
-                                std::vector<Rect>* horizontal_bounds);
-
-    // Returns true if this is a vertical split, false if a horizontal one.
-    // Based on ChooseSplitAxis algorithm in Beckmann et al. Chooses the axis
-    // with the lowest sum of margin values of bounding boxes.
-    static bool ChooseSplitAxis(const std::vector<Rect>& low_vertical_bounds,
-                                const std::vector<Rect>& high_vertical_bounds,
-                                const std::vector<Rect>& low_horizontal_bounds,
-                                const std::vector<Rect>& high_horizontal_bounds,
-                                size_t min_children,
-                                size_t max_children);
-
-    // Used by SplitNode to calculate optimal index of split, after determining
-    // along which axis to sort and split the children rectangles. Returns the
-    // index to the first element in the split children as sorted by the bounds
-    // vectors.
-    static size_t ChooseSplitIndex(size_t min_children,
-                                   size_t max_children,
-                                   const std::vector<Rect>& low_bounds,
-                                   const std::vector<Rect>& high_bounds);
-
-    // Takes our children_ and divides them into a new node, starting at index
-    // split_index in sorted_children.
-    Node* DivideChildren(const std::vector<Rect>& low_bounds,
-                         const std::vector<Rect>& high_bounds,
-                         const std::vector<Node*>& sorted_children,
-                         size_t split_index);
-
-    // Returns a pointer to the child node that will result in the least overlap
-    // increase with the addition of node_rect, as defined in the Beckmann et al
-    // paper, or NULL if there's a tie found. Requires a precomputed vector of
-    // expanded rectangles where the ith rectangle in the vector is the union of
-    // |children_|[i] and node_rect.
-    Node* LeastOverlapIncrease(const Rect& node_rect,
-                               const std::vector<Rect>& expanded_rects);
-
-    // Returns a pointer to the child node that will result in the least area
-    // enlargement if the argument node rectangle were to be added to that
-    // nodes' bounding box. Requires a precomputed vector of expanded rectangles
-    // where the ith rectangle in the vector is the union of |children_|[i] and
-    // node_rect.
-    Node* LeastAreaEnlargement(const Rect& node_rect,
-                               const std::vector<Rect>& expanded_rects);
-
-    // This Node's bounding rectangle.
-    Rect rect_;
-
-    // The height of the node in the tree, counting from -1 at the record node
-    // to 0 at the leaf up to the root node which has level equal to the height
-    // of the tree.
-    int level_;
-
-    // Pointers to all of our children Nodes.
-    ScopedVector<Node> children_;
-
-    // A weak pointer to our parent Node in the RTree. The root node will have a
-    // NULL value for |parent_|.
-    Node* parent_;
-
-    // If this is a record Node, then |key_| will be non-NULL and will contain
-    // the key data. Otherwise, NULL.
-    intptr_t key_;
-
-    friend class RTreeTest;
-    FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeBuildHighBounds);
-    FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeBuildLowBounds);
-    FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeChooseSplitAxisAndIndex);
-    FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeChooseSubtree);
-    FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareCenterDistanceFromParent);
-    FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareHorizontal);
-    FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareVertical);
-    FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeDivideChildren);
-    FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeLeastAreaEnlargement);
-    FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeLeastOverlapIncrease);
-    FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeOverlapIncreaseToAdd);
-    FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveAndReturnLastChild);
-    FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveChildNoOrphans);
-    FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveChildOrphans);
-    FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveNodesForReinsert);
-    FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeSplit);
-
-    DISALLOW_COPY_AND_ASSIGN(Node);
-  };
-
-  // Supports re-insertion of Nodes based on the strategies outlined in
-  // Beckmann et al.
-  void InsertNode(Node* node, int* highset_reinsert_level);
-
-  // Supports removal of nodes for tree without deletion.
-  void RemoveNode(Node* node);
+    Key key_;
 
-  // A pointer to the root node in the RTree.
-  scoped_ptr<Node> root_;
-
-  // The parameters used to define the shape of the RTree.
-  size_t min_children_;
-  size_t max_children_;
+    DISALLOW_COPY_AND_ASSIGN(Record);
+  };
 
   // A map of supplied keys to their Node representation within the RTree, for
   // efficient retrieval of keys without requiring a bounding rect.
-  base::hash_map<intptr_t, Node*> record_map_;
-
-  friend class RTreeTest;
-  FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeBuildHighBounds);
-  FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeBuildLowBounds);
-  FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeChooseSplitAxisAndIndex);
-  FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeChooseSubtree);
-  FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareCenterDistanceFromParent);
-  FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareHorizontal);
-  FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeCompareVertical);
-  FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeDivideChildren);
-  FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeLeastAreaEnlargement);
-  FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeLeastOverlapIncrease);
-  FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeOverlapIncreaseToAdd);
-  FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveAndReturnLastChild);
-  FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveChildNoOrphans);
-  FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveChildOrphans);
-  FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeRemoveNodesForReinsert);
-  FRIEND_TEST_ALL_PREFIXES(RTreeTest, NodeSplit);
+  typedef base::hash_map<Key, Record*> RecordMap;
+  RecordMap record_map_;
 
   DISALLOW_COPY_AND_ASSIGN(RTree);
 };
 
+template <typename Key>
+RTree<Key>::RTree(size_t min_children, size_t max_children)
+    : RTreeBase(min_children, max_children) {
+}
+
+template <typename Key>
+RTree<Key>::~RTree() {
+}
+
+template <typename Key>
+void RTree<Key>::Insert(const Rect& rect, Key key) {
+  scoped_ptr<NodeBase> record;
+  // Check if this key is already present in the tree.
+  typename RecordMap::iterator it(record_map_.find(key));
+
+  if (it != record_map_.end()) {
+    // We will re-use this node structure, regardless of re-insert or return.
+    Record* existing_record = it->second;
+    // If the new rect and the current rect are identical we can skip the rest
+    // of Insert() as nothing has changed.
+    if (existing_record->rect() == rect)
+      return;
+
+    // Remove the node from the tree in its current position.
+    record = RemoveNode(existing_record);
+
+    PruneRootIfNecessary();
+
+    // If we are replacing this key with an empty rectangle we just remove the
+    // old node from the list and return, thus preventing insertion of empty
+    // rectangles into our spatial database.
+    if (rect.IsEmpty()) {
+      record_map_.erase(it);
+      return;
+    }
+
+    // Reset the rectangle to the new value.
+    record->set_rect(rect);
+  } else {
+    if (rect.IsEmpty())
+      return;
+
+    record.reset(new Record(rect, key));
+    record_map_.insert(std::make_pair(key, static_cast<Record*>(record.get())));
+  }
+
+  int highest_reinsert_level = -1;
+  InsertNode(record.Pass(), &highest_reinsert_level);
+}
+
+template <typename Key>
+void RTree<Key>::Clear() {
+  record_map_.clear();
+  ResetRoot();
+}
+
+template <typename Key>
+void RTree<Key>::Remove(Key key) {
+  // Search the map for the leaf parent that has the provided record.
+  typename RecordMap::iterator it = record_map_.find(key);
+  if (it == record_map_.end())
+    return;
+
+  Record* record = it->second;
+  record_map_.erase(it);
+  RemoveNode(record);
+
+  // Lastly check the root. If it has only one non-leaf child, delete it and
+  // replace it with its child.
+  PruneRootIfNecessary();
+}
+
+template <typename Key>
+void RTree<Key>::AppendIntersectingRecords(
+      const Rect& query_rect, Matches* matches_out) const {
+  RTreeBase::Records matching_records;
+  root()->AppendIntersectingRecords(query_rect, &matching_records);
+  for (RTreeBase::Records::const_iterator it = matching_records.begin();
+       it != matching_records.end();
+       ++it) {
+    const Record* record = static_cast<const Record*>(*it);
+    matches_out->insert(record->key());
+  }
+}
+
+
+// RTree::Record --------------------------------------------------------------
+
+template <typename Key>
+RTree<Key>::Record::Record(const Rect& rect, const Key& key)
+    : RecordBase(rect),
+      key_(key) {
+}
+
+template <typename Key>
+RTree<Key>::Record::~Record() {
+}
+
 }  // namespace gfx
 
 #endif  // UI_GFX_GEOMETRY_R_TREE_H_
diff --git a/ui/gfx/geometry/r_tree_base.cc b/ui/gfx/geometry/r_tree_base.cc
new file mode 100644
index 0000000..e93e1d5
--- /dev/null
+++ b/ui/gfx/geometry/r_tree_base.cc
@@ -0,0 +1,658 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "ui/gfx/geometry/r_tree_base.h"
+
+#include <algorithm>
+
+#include "base/logging.h"
+
+
+// Helpers --------------------------------------------------------------------
+
+namespace {
+
+// Returns a Vector2d to allow us to do arithmetic on the result such as
+// computing distances between centers.
+gfx::Vector2d CenterOfRect(const gfx::Rect& rect) {
+  return rect.OffsetFromOrigin() +
+      gfx::Vector2d(rect.width() / 2, rect.height() / 2);
+}
+
+}
+
+namespace gfx {
+
+
+// RTreeBase::NodeBase --------------------------------------------------------
+
+RTreeBase::NodeBase::~NodeBase() {
+}
+
+void RTreeBase::NodeBase::RecomputeBoundsUpToRoot() {
+  RecomputeLocalBounds();
+  if (parent_)
+    parent_->RecomputeBoundsUpToRoot();
+}
+
+RTreeBase::NodeBase::NodeBase(const Rect& rect, NodeBase* parent)
+    : rect_(rect),
+      parent_(parent) {
+}
+
+void RTreeBase::NodeBase::RecomputeLocalBounds() {
+}
+
+// RTreeBase::RecordBase ------------------------------------------------------
+
+RTreeBase::RecordBase::RecordBase(const Rect& rect) : NodeBase(rect, NULL) {
+}
+
+RTreeBase::RecordBase::~RecordBase() {
+}
+
+void RTreeBase::RecordBase::AppendIntersectingRecords(
+    const Rect& query_rect, Records* matches_out) const {
+  if (rect().Intersects(query_rect))
+    matches_out->push_back(this);
+}
+
+void RTreeBase::RecordBase::AppendAllRecords(Records* matches_out) const {
+  matches_out->push_back(this);
+}
+
+scoped_ptr<RTreeBase::NodeBase>
+RTreeBase::RecordBase::RemoveAndReturnLastChild() {
+  return scoped_ptr<NodeBase>();
+}
+
+int RTreeBase::RecordBase::Level() const {
+  return -1;
+}
+
+
+// RTreeBase::Node ------------------------------------------------------------
+
+RTreeBase::Node::Node() : NodeBase(Rect(), NULL), level_(0) {
+}
+
+RTreeBase::Node::~Node() {
+}
+
+scoped_ptr<RTreeBase::Node> RTreeBase::Node::ConstructParent() {
+  DCHECK(!parent());
+  scoped_ptr<Node> new_parent(new Node(level_ + 1));
+  new_parent->AddChild(scoped_ptr<NodeBase>(this));
+  return new_parent.Pass();
+}
+
+void RTreeBase::Node::AppendIntersectingRecords(
+    const Rect& query_rect, Records* matches_out) const {
+  // Check own bounding box for intersection, can cull all children if no
+  // intersection.
+  if (!rect().Intersects(query_rect))
+    return;
+
+  // Conversely if we are completely contained within the query rect we can
+  // confidently skip all bounds checks for ourselves and all our children.
+  if (query_rect.Contains(rect())) {
+    AppendAllRecords(matches_out);
+    return;
+  }
+
+  // We intersect the query rect but we are not are not contained within it.
+  // We must query each of our children in turn.
+  for (Nodes::const_iterator i = children_.begin(); i != children_.end(); ++i)
+    (*i)->AppendIntersectingRecords(query_rect, matches_out);
+}
+
+void RTreeBase::Node::AppendAllRecords(Records* matches_out) const {
+  for (Nodes::const_iterator i = children_.begin(); i != children_.end(); ++i)
+    (*i)->AppendAllRecords(matches_out);
+}
+
+void RTreeBase::Node::RemoveNodesForReinsert(size_t number_to_remove,
+                                             Nodes* nodes) {
+  DCHECK_LE(number_to_remove, children_.size());
+
+  std::partial_sort(children_.begin(),
+                    children_.begin() + number_to_remove,
+                    children_.end(),
+                    &RTreeBase::Node::CompareCenterDistanceFromParent);
+
+  // Move the lowest-distance nodes to the returned vector.
+  nodes->insert(
+      nodes->end(), children_.begin(), children_.begin() + number_to_remove);
+  children_.weak_erase(children_.begin(), children_.begin() + number_to_remove);
+}
+
+scoped_ptr<RTreeBase::NodeBase> RTreeBase::Node::RemoveChild(
+    NodeBase* child_node, Nodes* orphans) {
+  DCHECK_EQ(this, child_node->parent());
+
+  scoped_ptr<NodeBase> orphan(child_node->RemoveAndReturnLastChild());
+  while (orphan) {
+    orphans->push_back(orphan.release());
+    orphan = child_node->RemoveAndReturnLastChild();
+  }
+
+  Nodes::iterator i = std::find(children_.begin(), children_.end(), child_node);
+  DCHECK(i != children_.end());
+  children_.weak_erase(i);
+
+  return scoped_ptr<NodeBase>(child_node);
+}
+
+scoped_ptr<RTreeBase::NodeBase> RTreeBase::Node::RemoveAndReturnLastChild() {
+  if (children_.empty())
+    return scoped_ptr<NodeBase>();
+
+  scoped_ptr<NodeBase> last_child(children_.back());
+  children_.weak_erase(children_.end() - 1);
+  last_child->set_parent(NULL);
+  return last_child.Pass();
+}
+
+RTreeBase::Node* RTreeBase::Node::ChooseSubtree(NodeBase* node) {
+  DCHECK(node);
+  // Should never be called on a node at equal or lower level in the tree than
+  // the node to insert.
+  DCHECK_GT(level_, node->Level());
+
+  // If we are a parent of nodes on the provided node level, we are done.
+  if (level_ == node->Level() + 1)
+    return this;
+
+  // Precompute a vector of expanded rects, used by both LeastOverlapIncrease
+  // and LeastAreaEnlargement.
+  Rects expanded_rects;
+  expanded_rects.reserve(children_.size());
+  for (Nodes::iterator i = children_.begin(); i != children_.end(); ++i)
+    expanded_rects.push_back(UnionRects(node->rect(), (*i)->rect()));
+
+  Node* best_candidate = NULL;
+  // For parents of leaf nodes, we pick the node that will cause the least
+  // increase in overlap by the addition of this new node. This may detect a
+  // tie, in which case it will return NULL.
+  if (level_ == 1)
+    best_candidate = LeastOverlapIncrease(node->rect(), expanded_rects);
+
+  // For non-parents of leaf nodes, or for parents of leaf nodes with ties in
+  // overlap increase, we choose the subtree with least area enlargement caused
+  // by the addition of the new node.
+  if (!best_candidate)
+    best_candidate = LeastAreaEnlargement(node->rect(), expanded_rects);
+
+  DCHECK(best_candidate);
+  return best_candidate->ChooseSubtree(node);
+}
+
+size_t RTreeBase::Node::AddChild(scoped_ptr<NodeBase> node) {
+  DCHECK(node);
+  // Sanity-check that the level of the child being added is one less than ours.
+  DCHECK_EQ(level_ - 1, node->Level());
+  node->set_parent(this);
+  set_rect(UnionRects(rect(), node->rect()));
+  children_.push_back(node.release());
+  return children_.size();
+}
+
+scoped_ptr<RTreeBase::NodeBase> RTreeBase::Node::Split(size_t min_children,
+                                                       size_t max_children) {
+  // We should have too many children to begin with.
+  DCHECK_EQ(max_children + 1, children_.size());
+
+  // Determine if we should split along the horizontal or vertical axis.
+  std::vector<NodeBase*> vertical_sort(children_.get());
+  std::vector<NodeBase*> horizontal_sort(children_.get());
+  std::sort(vertical_sort.begin(),
+            vertical_sort.end(),
+            &RTreeBase::Node::CompareVertical);
+  std::sort(horizontal_sort.begin(),
+            horizontal_sort.end(),
+            &RTreeBase::Node::CompareHorizontal);
+
+  Rects low_vertical_bounds;
+  Rects low_horizontal_bounds;
+  BuildLowBounds(vertical_sort,
+                 horizontal_sort,
+                 &low_vertical_bounds,
+                 &low_horizontal_bounds);
+
+  Rects high_vertical_bounds;
+  Rects high_horizontal_bounds;
+  BuildHighBounds(vertical_sort,
+                  horizontal_sort,
+                  &high_vertical_bounds,
+                  &high_horizontal_bounds);
+
+  // Choose |end_index| such that both Nodes after the split will have
+  // min_children <= children_.size() <= max_children.
+  size_t end_index = std::min(max_children, children_.size() - min_children);
+  bool is_vertical_split =
+      SmallestMarginSum(min_children,
+                        end_index,
+                        low_horizontal_bounds,
+                        high_horizontal_bounds) <
+      SmallestMarginSum(min_children,
+                        end_index,
+                        low_vertical_bounds,
+                        high_vertical_bounds);
+
+  // Choose split index along chosen axis and perform the split.
+  const Rects& low_bounds(
+      is_vertical_split ? low_vertical_bounds : low_horizontal_bounds);
+  const Rects& high_bounds(
+      is_vertical_split ? high_vertical_bounds : high_horizontal_bounds);
+  size_t split_index =
+      ChooseSplitIndex(min_children, end_index, low_bounds, high_bounds);
+
+  const std::vector<NodeBase*>& sort(
+      is_vertical_split ? vertical_sort : horizontal_sort);
+  return DivideChildren(low_bounds, high_bounds, sort, split_index);
+}
+
+int RTreeBase::Node::Level() const {
+  return level_;
+}
+
+RTreeBase::Node::Node(int level) : NodeBase(Rect(), NULL), level_(level) {
+}
+
+// static
+bool RTreeBase::Node::CompareVertical(const NodeBase* a, const NodeBase* b) {
+  const Rect& a_rect = a->rect();
+  const Rect& b_rect = b->rect();
+  return (a_rect.y() < b_rect.y()) ||
+         ((a_rect.y() == b_rect.y()) && (a_rect.height() < b_rect.height()));
+}
+
+// static
+bool RTreeBase::Node::CompareHorizontal(const NodeBase* a, const NodeBase* b) {
+  const Rect& a_rect = a->rect();
+  const Rect& b_rect = b->rect();
+  return (a_rect.x() < b_rect.x()) ||
+         ((a_rect.x() == b_rect.x()) && (a_rect.width() < b_rect.width()));
+}
+
+// static
+bool RTreeBase::Node::CompareCenterDistanceFromParent(const NodeBase* a,
+                                                      const NodeBase* b) {
+  const NodeBase* p = a->parent();
+
+  DCHECK(p);
+  DCHECK_EQ(p, b->parent());
+
+  Vector2d p_center = CenterOfRect(p->rect());
+  Vector2d a_center = CenterOfRect(a->rect());
+  Vector2d b_center = CenterOfRect(b->rect());
+
+  // We don't bother with square roots because we are only comparing the two
+  // values for sorting purposes.
+  return (a_center - p_center).LengthSquared() <
+         (b_center - p_center).LengthSquared();
+}
+
+// static
+void RTreeBase::Node::BuildLowBounds(
+    const std::vector<NodeBase*>& vertical_sort,
+    const std::vector<NodeBase*>& horizontal_sort,
+    Rects* vertical_bounds,
+    Rects* horizontal_bounds) {
+  Rect vertical_bounds_rect;
+  vertical_bounds->reserve(vertical_sort.size());
+  for (std::vector<NodeBase*>::const_iterator i = vertical_sort.begin();
+       i != vertical_sort.end();
+       ++i) {
+    vertical_bounds_rect.Union((*i)->rect());
+    vertical_bounds->push_back(vertical_bounds_rect);
+  }
+
+  Rect horizontal_bounds_rect;
+  horizontal_bounds->reserve(horizontal_sort.size());
+  for (std::vector<NodeBase*>::const_iterator i = horizontal_sort.begin();
+       i != horizontal_sort.end();
+       ++i) {
+    horizontal_bounds_rect.Union((*i)->rect());
+    horizontal_bounds->push_back(horizontal_bounds_rect);
+  }
+}
+
+// static
+void RTreeBase::Node::BuildHighBounds(
+    const std::vector<NodeBase*>& vertical_sort,
+    const std::vector<NodeBase*>& horizontal_sort,
+    Rects* vertical_bounds,
+    Rects* horizontal_bounds) {
+  Rect vertical_bounds_rect;
+  vertical_bounds->reserve(vertical_sort.size());
+  for (std::vector<NodeBase*>::const_reverse_iterator i =
+           vertical_sort.rbegin();
+       i != vertical_sort.rend();
+       ++i) {
+    vertical_bounds_rect.Union((*i)->rect());
+    vertical_bounds->push_back(vertical_bounds_rect);
+  }
+  std::reverse(vertical_bounds->begin(), vertical_bounds->end());
+
+  Rect horizontal_bounds_rect;
+  horizontal_bounds->reserve(horizontal_sort.size());
+  for (std::vector<NodeBase*>::const_reverse_iterator i =
+           horizontal_sort.rbegin();
+       i != horizontal_sort.rend();
+       ++i) {
+    horizontal_bounds_rect.Union((*i)->rect());
+    horizontal_bounds->push_back(horizontal_bounds_rect);
+  }
+  std::reverse(horizontal_bounds->begin(), horizontal_bounds->end());
+}
+
+size_t RTreeBase::Node::ChooseSplitIndex(size_t start_index,
+                                         size_t end_index,
+                                         const Rects& low_bounds,
+                                         const Rects& high_bounds) {
+  DCHECK_EQ(low_bounds.size(), high_bounds.size());
+
+  int smallest_overlap_area = UnionRects(
+      low_bounds[start_index], high_bounds[start_index]).size().GetArea();
+  int smallest_combined_area = low_bounds[start_index].size().GetArea() +
+      high_bounds[start_index].size().GetArea();
+  size_t optimal_split_index = start_index;
+  for (size_t p = start_index + 1; p < end_index; ++p) {
+    const int overlap_area =
+        UnionRects(low_bounds[p], high_bounds[p]).size().GetArea();
+    const int combined_area =
+        low_bounds[p].size().GetArea() + high_bounds[p].size().GetArea();
+    if ((overlap_area < smallest_overlap_area) ||
+        ((overlap_area == smallest_overlap_area) &&
+         (combined_area < smallest_combined_area))) {
+      smallest_overlap_area = overlap_area;
+      smallest_combined_area = combined_area;
+      optimal_split_index = p;
+    }
+  }
+
+  // optimal_split_index currently points at the last element in the first set,
+  // so advance it by 1 to point at the first element in the second set.
+  return optimal_split_index + 1;
+}
+
+// static
+int RTreeBase::Node::SmallestMarginSum(size_t start_index,
+                                       size_t end_index,
+                                       const Rects& low_bounds,
+                                       const Rects& high_bounds) {
+  DCHECK_EQ(low_bounds.size(), high_bounds.size());
+  DCHECK_LT(start_index, low_bounds.size());
+  DCHECK_LE(start_index, end_index);
+  DCHECK_LE(end_index, low_bounds.size());
+  Rects::const_iterator i(low_bounds.begin() + start_index);
+  Rects::const_iterator j(high_bounds.begin() + start_index);
+  int smallest_sum = i->width() + i->height() + j->width() + j->height();
+  for (; i != (low_bounds.begin() + end_index); ++i, ++j) {
+    smallest_sum = std::min(
+        smallest_sum, i->width() + i->height() + j->width() + j->height());
+  }
+
+  return smallest_sum;
+}
+
+void RTreeBase::Node::RecomputeLocalBounds() {
+  Rect bounds;
+  for (size_t i = 0; i < children_.size(); ++i)
+    bounds.Union(children_[i]->rect());
+
+  set_rect(bounds);
+}
+
+int RTreeBase::Node::OverlapIncreaseToAdd(const Rect& rect,
+                                          const NodeBase* candidate_node,
+                                          const Rect& expanded_rect) const {
+  DCHECK(candidate_node);
+
+  // Early-out when |rect| is contained completely within |candidate|.
+  if (candidate_node->rect().Contains(rect))
+    return 0;
+
+  int total_original_overlap = 0;
+  int total_expanded_overlap = 0;
+
+  // Now calculate overlap with all other rects in this node.
+  for (Nodes::const_iterator it = children_.begin();
+       it != children_.end(); ++it) {
+    // Skip calculating overlap with the candidate rect.
+    if ((*it) == candidate_node)
+      continue;
+    NodeBase* overlap_node = (*it);
+    total_original_overlap += IntersectRects(
+        candidate_node->rect(), overlap_node->rect()).size().GetArea();
+    Rect expanded_overlap_rect = expanded_rect;
+    expanded_overlap_rect.Intersect(overlap_node->rect());
+    total_expanded_overlap += expanded_overlap_rect.size().GetArea();
+  }
+
+  return total_expanded_overlap - total_original_overlap;
+}
+
+scoped_ptr<RTreeBase::NodeBase> RTreeBase::Node::DivideChildren(
+    const Rects& low_bounds,
+    const Rects& high_bounds,
+    const std::vector<NodeBase*>& sorted_children,
+    size_t split_index) {
+  DCHECK_EQ(low_bounds.size(), high_bounds.size());
+  DCHECK_EQ(low_bounds.size(), sorted_children.size());
+  DCHECK_LT(split_index, low_bounds.size());
+  DCHECK_GT(split_index, 0U);
+
+  scoped_ptr<Node> sibling(new Node(level_));
+  sibling->set_parent(parent());
+  set_rect(low_bounds[split_index - 1]);
+  sibling->set_rect(high_bounds[split_index]);
+
+  // Our own children_ vector is unsorted, so we wipe it out and divide the
+  // sorted bounds rects between ourselves and our sibling.
+  children_.weak_clear();
+  children_.insert(children_.end(),
+                   sorted_children.begin(),
+                   sorted_children.begin() + split_index);
+  sibling->children_.insert(sibling->children_.end(),
+                            sorted_children.begin() + split_index,
+                            sorted_children.end());
+
+  for (size_t i = 0; i < sibling->children_.size(); ++i)
+    sibling->children_[i]->set_parent(sibling.get());
+
+  return sibling.PassAs<NodeBase>();
+}
+
+RTreeBase::Node* RTreeBase::Node::LeastOverlapIncrease(
+    const Rect& node_rect,
+    const Rects& expanded_rects) {
+  NodeBase* best_node = children_.front();
+  int least_overlap_increase =
+      OverlapIncreaseToAdd(node_rect, children_[0], expanded_rects[0]);
+  for (size_t i = 1; i < children_.size(); ++i) {
+    int overlap_increase =
+        OverlapIncreaseToAdd(node_rect, children_[i], expanded_rects[i]);
+    if (overlap_increase < least_overlap_increase) {
+      least_overlap_increase = overlap_increase;
+      best_node = children_[i];
+    } else if (overlap_increase == least_overlap_increase) {
+      // If we are tied at zero there is no possible better overlap increase,
+      // so we can report a tie early.
+      if (overlap_increase == 0)
+        return NULL;
+
+      best_node = NULL;
+    }
+  }
+
+  // Ensure that our children are always Nodes and not Records.
+  DCHECK_GE(level_, 1);
+  return static_cast<Node*>(best_node);
+}
+
+RTreeBase::Node* RTreeBase::Node::LeastAreaEnlargement(
+    const Rect& node_rect,
+    const Rects& expanded_rects) {
+  DCHECK(!children_.empty());
+  DCHECK_EQ(children_.size(), expanded_rects.size());
+
+  NodeBase* best_node = children_.front();
+  int least_area_enlargement =
+      expanded_rects[0].size().GetArea() - best_node->rect().size().GetArea();
+  for (size_t i = 1; i < children_.size(); ++i) {
+    NodeBase* candidate_node = children_[i];
+    int area_change = expanded_rects[i].size().GetArea() -
+                      candidate_node->rect().size().GetArea();
+    DCHECK_GE(area_change, 0);
+    if (area_change < least_area_enlargement) {
+      best_node = candidate_node;
+      least_area_enlargement = area_change;
+    } else if (area_change == least_area_enlargement &&
+        candidate_node->rect().size().GetArea() <
+            best_node->rect().size().GetArea()) {
+      // Ties are broken by choosing the entry with the least area.
+      best_node = candidate_node;
+    }
+  }
+
+  // Ensure that our children are always Nodes and not Records.
+  DCHECK_GE(level_, 1);
+  return static_cast<Node*>(best_node);
+}
+
+
+// RTreeBase ------------------------------------------------------------------
+
+RTreeBase::RTreeBase(size_t min_children, size_t max_children)
+    : root_(new Node()),
+      min_children_(min_children),
+      max_children_(max_children) {
+  DCHECK_GE(min_children_, 2U);
+  DCHECK_LE(min_children_, max_children_ / 2U);
+}
+
+RTreeBase::~RTreeBase() {
+}
+
+void RTreeBase::InsertNode(
+    scoped_ptr<NodeBase> node, int* highest_reinsert_level) {
+  // Find the most appropriate parent to insert node into.
+  Node* parent = root_->ChooseSubtree(node.get());
+  DCHECK(parent);
+  // Verify ChooseSubtree returned a Node at the correct level.
+  DCHECK_EQ(parent->Level(), node->Level() + 1);
+  Node* insert_parent = static_cast<Node*>(parent);
+  NodeBase* needs_bounds_recomputed = insert_parent->parent();
+  Nodes reinserts;
+  // Attempt to insert the Node, if this overflows the Node we must handle it.
+  while (insert_parent &&
+         insert_parent->AddChild(node.Pass()) > max_children_) {
+    // If we have yet to re-insert nodes at this level during this data insert,
+    // and we're not at the root, R*-Tree calls for re-insertion of some of the
+    // nodes, resulting in a better balance on the tree.
+    if (insert_parent->parent() &&
+        insert_parent->Level() > *highest_reinsert_level) {
+      insert_parent->RemoveNodesForReinsert(max_children_ / 3, &reinserts);
+      // Adjust highest_reinsert_level to this level.
+      *highest_reinsert_level = insert_parent->Level();
+      // RemoveNodesForReinsert() does not recompute bounds, so mark it.
+      needs_bounds_recomputed = insert_parent;
+      break;
+    }
+
+    // Split() will create a sibling to insert_parent both of which will have
+    // valid bounds, but this invalidates their parent's bounds.
+    node = insert_parent->Split(min_children_, max_children_);
+    insert_parent = static_cast<Node*>(insert_parent->parent());
+    needs_bounds_recomputed = insert_parent;
+  }
+
+  // If we have a Node to insert, and we hit the root of the current tree,
+  // we create a new root which is the parent of the current root and the
+  // insert_node. Note that we must release() the |root_| since
+  // ConstructParent() will take ownership of it.
+  if (!insert_parent && node) {
+    root_ = root_.release()->ConstructParent();
+    root_->AddChild(node.Pass());
+  }
+
+  // Recompute bounds along insertion path.
+  if (needs_bounds_recomputed)
+    needs_bounds_recomputed->RecomputeBoundsUpToRoot();
+
+  // Complete re-inserts, if any. The algorithm only allows for one invocation
+  // of RemoveNodesForReinsert() per level of the tree in an overall call to
+  // Insert().
+  while (!reinserts.empty()) {
+    Nodes::iterator last_element = reinserts.end() - 1;
+    NodeBase* temp_ptr(*last_element);
+    reinserts.weak_erase(last_element);
+    InsertNode(make_scoped_ptr(temp_ptr), highest_reinsert_level);
+  }
+}
+
+scoped_ptr<RTreeBase::NodeBase> RTreeBase::RemoveNode(NodeBase* node) {
+  // We need to remove this node from its parent.
+  Node* parent = static_cast<Node*>(node->parent());
+  // Record nodes are never allowed as the root, so we should always have a
+  // parent.
+  DCHECK(parent);
+  // Should always be a leaf that had the record.
+  DCHECK_EQ(0, parent->Level());
+
+  Nodes orphans;
+  scoped_ptr<NodeBase> removed_node(parent->RemoveChild(node, &orphans));
+
+  // It's possible that by removing |node| from |parent| we have made |parent|
+  // have less than the minimum number of children, in which case we will need
+  // to remove and delete |parent| while reinserting any other children that it
+  // had. We traverse up the tree doing this until we remove a child from a
+  // parent that still has greater than or equal to the minimum number of Nodes.
+  while (parent->count() < min_children_) {
+    NodeBase* child = parent;
+    parent = static_cast<Node*>(parent->parent());
+
+    // If we've hit the root, stop.
+    if (!parent)
+      break;
+
+    parent->RemoveChild(child, &orphans);
+  }
+
+  // If we stopped deleting nodes up the tree before encountering the root,
+  // we'll need to fix up the bounds from the first parent we didn't delete
+  // up to the root.
+  if (parent)
+    parent->RecomputeBoundsUpToRoot();
+  else
+    root_->RecomputeBoundsUpToRoot();
+
+  while (!orphans.empty()) {
+    Nodes::iterator last_element = orphans.end() - 1;
+    NodeBase* temp_ptr(*last_element);
+    orphans.weak_erase(last_element);
+    int starting_level = -1;
+    InsertNode(make_scoped_ptr(temp_ptr), &starting_level);
+  }
+
+  return removed_node.Pass();
+}
+
+void RTreeBase::PruneRootIfNecessary() {
+  if (root()->count() == 1 && root()->Level() > 0) {
+    // Awkward reset(cast(release)) pattern here because there's no better way
+    // to downcast the scoped_ptr from RemoveAndReturnLastChild() from NodeBase
+    // to Node.
+    root_.reset(
+        static_cast<Node*>(root_->RemoveAndReturnLastChild().release()));
+  }
+}
+
+void RTreeBase::ResetRoot() {
+  root_.reset(new Node());
+}
+
+}  // namespace gfx
diff --git a/ui/gfx/geometry/r_tree_base.h b/ui/gfx/geometry/r_tree_base.h
new file mode 100644
index 0000000..21dc86b
--- /dev/null
+++ b/ui/gfx/geometry/r_tree_base.h
@@ -0,0 +1,309 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// Provides an implementation the parts of the RTree data structure that don't
+// require knowledge of the generic key type. Don't use these objects directly,
+// rather specialize the RTree<> object in r_tree.h. This file defines the
+// internal objects of an RTree, namely Nodes (internal nodes of the tree) and
+// Records, which hold (key, rectangle) pairs.
+
+#ifndef UI_GFX_GEOMETRY_R_TREE_BASE_H_
+#define UI_GFX_GEOMETRY_R_TREE_BASE_H_
+
+#include <list>
+#include <vector>
+
+#include "base/containers/hash_tables.h"
+#include "base/macros.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/memory/scoped_vector.h"
+#include "ui/gfx/geometry/rect.h"
+#include "ui/gfx/gfx_export.h"
+
+namespace gfx {
+
+class GFX_EXPORT RTreeBase {
+ protected:
+  class NodeBase;
+  class RecordBase;
+
+  typedef std::vector<const RecordBase*> Records;
+  typedef ScopedVector<NodeBase> Nodes;
+
+  RTreeBase(size_t min_children, size_t max_children);
+  ~RTreeBase();
+
+  // Protected data structure class for storing internal Nodes or leaves with
+  // Records.
+  class GFX_EXPORT NodeBase {
+   public:
+    virtual ~NodeBase();
+
+    // Appends to |records_out| the set of Records in this subtree with rects
+    // that intersect |query_rect|.  Avoids clearing |records_out| so that it
+    // can be called recursively.
+    virtual void AppendIntersectingRecords(const Rect& query_rect,
+                                           Records* records_out) const = 0;
+
+    // Returns all records stored in the subtree rooted at this node. Appends to
+    // |matches_out| without clearing.
+    virtual void AppendAllRecords(Records* records_out) const = 0;
+
+    // Returns NULL if no children. Does not recompute bounds.
+    virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() = 0;
+
+    // Returns -1 for Records, or the height of this subtree for Nodes.  The
+    // height of a leaf Node (a Node containing only Records) is 0, a leaf's
+    // parent is 1, etc. Note that in an R*-Tree, all branches from the root
+    // Node will be the same height.
+    virtual int Level() const = 0;
+
+    // Recomputes our bounds by taking the union of all child rects, then calls
+    // recursively on our parent so that ultimately all nodes up to the root
+    // recompute their bounds.
+    void RecomputeBoundsUpToRoot();
+
+    NodeBase* parent() { return parent_; }
+    const NodeBase* parent() const { return parent_; }
+    void set_parent(NodeBase* parent) { parent_ = parent; }
+    const Rect& rect() const { return rect_; }
+    void set_rect(const Rect& rect) { rect_ = rect; }
+
+   protected:
+    NodeBase(const Rect& rect, NodeBase* parent);
+
+    // Bounds recomputation without calling parents to do the same.
+    virtual void RecomputeLocalBounds();
+
+   private:
+    friend class RTreeTest;
+    friend class RTreeNodeTest;
+
+    // This Node's bounding rectangle.
+    Rect rect_;
+
+    // A weak pointer to our parent Node in the RTree. The root node will have a
+    // NULL value for |parent_|.
+    NodeBase* parent_;
+
+    DISALLOW_COPY_AND_ASSIGN(NodeBase);
+  };
+
+  class GFX_EXPORT RecordBase : public NodeBase {
+   public:
+    explicit RecordBase(const Rect& rect);
+    virtual ~RecordBase();
+
+    virtual void AppendIntersectingRecords(const Rect& query_rect,
+                                           Records* records_out) const OVERRIDE;
+    virtual void AppendAllRecords(Records* records_out) const OVERRIDE;
+    virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() OVERRIDE;
+    virtual int Level() const OVERRIDE;
+
+   private:
+    friend class RTreeTest;
+    friend class RTreeNodeTest;
+
+    DISALLOW_COPY_AND_ASSIGN(RecordBase);
+  };
+
+  class GFX_EXPORT Node : public NodeBase {
+   public:
+    // Constructs an empty Node with |level_| of 0.
+    Node();
+    virtual ~Node();
+
+    virtual void AppendIntersectingRecords(const Rect& query_rect,
+                                           Records* records_out) const OVERRIDE;
+    virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() OVERRIDE;
+    virtual int Level() const OVERRIDE;
+    virtual void AppendAllRecords(Records* matches_out) const OVERRIDE;
+
+    // Constructs a new Node that is the parent of this Node and already has
+    // this Node as its sole child. Valid to call only on root Nodes, meaning
+    // Nodes with |parent_| NULL. Note that ownership of this Node is
+    // transferred to the parent returned by this function.
+    scoped_ptr<Node> ConstructParent();
+
+    // Removes |number_to_remove| children from this Node, and appends them to
+    // the supplied list. Does not repair bounds upon completion. Nodes are
+    // selected in the manner suggested in the Beckmann et al. paper, which
+    // suggests that the children should be sorted by the distance from the
+    // center of their bounding rectangle to their parent's bounding rectangle,
+    // and then the n closest children should be removed for re-insertion. This
+    // removal occurs at most once on each level of the tree when overflowing
+    // nodes that have exceeded the maximum number of children during an Insert.
+    void RemoveNodesForReinsert(size_t number_to_remove, Nodes* nodes);
+
+    // Given a pointer to a child node within this Node, removes it from our
+    // list. If that child had any children, appends them to the supplied orphan
+    // list. Returns the removed child. Does not recompute bounds, as the caller
+    // might subsequently remove this node as well, meaning the recomputation
+    // would be wasted work.
+    scoped_ptr<NodeBase> RemoveChild(NodeBase* child_node, Nodes* orphans);
+
+    // Returns the best parent for insertion of the provided |node| as a child.
+    Node* ChooseSubtree(NodeBase* node);
+
+    // Adds |node| as a child of this Node, and recomputes the bounds of this
+    // node after the addition of the child. Returns the new count of children
+    // stored in this Node. This node becomes the owner of |node|.
+    size_t AddChild(scoped_ptr<NodeBase> node);
+
+    // Returns a sibling to this Node with at least min_children and no greater
+    // than max_children of this Node's children assigned to it, and having the
+    // same parent. Bounds will be valid on both Nodes after this call.
+    scoped_ptr<NodeBase> Split(size_t min_children, size_t max_children);
+
+    size_t count() const { return children_.size(); }
+    const NodeBase* child(size_t i) const { return children_[i]; }
+    NodeBase* child(size_t i) { return children_[i]; }
+
+   private:
+    typedef std::vector<Rect> Rects;
+
+    explicit Node(int level);
+
+    // Given two arrays of bounds rectangles as computed by BuildLowBounds()
+    // and BuildHighBounds(), returns the index of the element in those arrays
+    // along which a split of the arrays would result in a minimum amount of
+    // overlap (area of intersection) in the two groups.
+    static size_t ChooseSplitIndex(size_t start_index,
+                                   size_t end_index,
+                                   const Rects& low_bounds,
+                                   const Rects& high_bounds);
+
+    // R*-Tree attempts to keep groups of rectangles that are roughly square
+    // in shape. It does this by comparing the "margins" of different bounding
+    // boxes, where margin is defined as the sum of the length of all four sides
+    // of a rectangle. For two rectangles of equal area, the one with the
+    // smallest margin will be the rectangle whose width and height differ the
+    // least. When splitting we decide to split along an axis chosen from the
+    // rectangles either sorted vertically or horizontally by finding the axis
+    // that would result in the smallest sum of margins between the two bounding
+    // boxes of the resulting split. Returns the smallest sum computed given the
+    // sorted bounding boxes and a range to look within.
+    static int SmallestMarginSum(size_t start_index,
+                                 size_t end_index,
+                                 const Rects& low_bounds,
+                                 const Rects& high_bounds);
+
+    // Sorts nodes primarily by increasing y coordinates, and secondarily by
+    // increasing height.
+    static bool CompareVertical(const NodeBase* a, const NodeBase* b);
+
+    // Sorts nodes primarily by increasing x coordinates, and secondarily by
+    // increasing width.
+    static bool CompareHorizontal(const NodeBase* a, const NodeBase* b);
+
+    // Sorts nodes by the distance of the center of their rectangles to the
+    // center of their parent's rectangles.
+    static bool CompareCenterDistanceFromParent(
+        const NodeBase* a, const NodeBase* b);
+
+    // Given two vectors of Nodes sorted by vertical or horizontal bounds,
+    // populates two vectors of Rectangles in which the ith element is the union
+    // of all bounding rectangles [0,i] in the associated sorted array of Nodes.
+    static void BuildLowBounds(const std::vector<NodeBase*>& vertical_sort,
+                               const std::vector<NodeBase*>& horizontal_sort,
+                               Rects* vertical_bounds,
+                               Rects* horizontal_bounds);
+
+    // Given two vectors of Nodes sorted by vertical or horizontal bounds,
+    // populates two vectors of Rectangles in which the ith element is the
+    // union of all bounding rectangles [i, count()) in the associated sorted
+    // array of Nodes.
+    static void BuildHighBounds(const std::vector<NodeBase*>& vertical_sort,
+                                const std::vector<NodeBase*>& horizontal_sort,
+                                Rects* vertical_bounds,
+                                Rects* horizontal_bounds);
+
+    virtual void RecomputeLocalBounds() OVERRIDE;
+
+    // Returns the increase in overlap value, as defined in Beckmann et al. as
+    // the sum of the areas of the intersection of all child rectangles
+    // (excepting the candidate child) with the argument rectangle. Here the
+    // |candidate_node| is one of our |children_|, and |expanded_rect| is the
+    // already-computed union of the candidate's rect and |rect|.
+    int OverlapIncreaseToAdd(const Rect& rect,
+                             const NodeBase* candidate_node,
+                             const Rect& expanded_rect) const;
+
+    // Returns a new node containing children [split_index, count()) within
+    // |sorted_children|.  Children before |split_index| remain with |this|.
+    scoped_ptr<NodeBase> DivideChildren(
+        const Rects& low_bounds,
+        const Rects& high_bounds,
+        const std::vector<NodeBase*>& sorted_children,
+        size_t split_index);
+
+    // Returns a pointer to the child node that will result in the least overlap
+    // increase with the addition of node_rect, or NULL if there's a tie found.
+    // Requires a precomputed vector of expanded rectangles where the ith
+    // rectangle in the vector is the union of |children_|[i] and node_rect.
+    // Overlap is defined in Beckmann et al. as the sum of the areas of
+    // intersection of all child rectangles with the |node_rect| argument
+    // rectangle.  This heuristic attempts to choose the node for which adding
+    // the new rectangle to their bounding box will result in the least overlap
+    // with the other rectangles, thus trying to preserve the usefulness of the
+    // bounding rectangle by keeping it from covering too much redundant area.
+    Node* LeastOverlapIncrease(const Rect& node_rect,
+                               const Rects& expanded_rects);
+
+    // Returns a pointer to the child node that will result in the least area
+    // enlargement if the argument node rectangle were to be added to that
+    // node's bounding box. Requires a precomputed vector of expanded rectangles
+    // where the ith rectangle in the vector is the union of children_[i] and
+    // |node_rect|.
+    Node* LeastAreaEnlargement(const Rect& node_rect,
+                               const Rects& expanded_rects);
+
+    const int level_;
+
+    Nodes children_;
+
+    friend class RTreeTest;
+    friend class RTreeNodeTest;
+
+    DISALLOW_COPY_AND_ASSIGN(Node);
+  };
+
+  // Inserts |node| into the tree. The |highest_reinsert_level| supports
+  // re-insertion as described by Beckmann et al. As Node overflows progagate
+  // up the tree the algorithm performs a reinsertion of the overflow Nodes
+  // (instead of a split) at most once per level of the tree. A starting value
+  // of -1 for |highest_reinsert_level| means that reinserts are permitted for
+  // every level of the tree. This should always be set to -1 except by
+  // recursive calls from within InsertNode().
+  void InsertNode(scoped_ptr<NodeBase> node, int* highest_reinsert_level);
+
+  // Removes |node| from the tree without deleting it.
+  scoped_ptr<NodeBase> RemoveNode(NodeBase* node);
+
+  // If |root_| has only one child, deletes the |root_| Node and replaces it
+  // with its only descendant child. Otherwise does nothing.
+  void PruneRootIfNecessary();
+
+  // Deletes the entire current tree and replaces it with an empty Node.
+  void ResetRoot();
+
+  const Node* root() const { return root_.get(); }
+
+ private:
+  friend class RTreeTest;
+  friend class RTreeNodeTest;
+
+  // A pointer to the root node in the RTree.
+  scoped_ptr<Node> root_;
+
+  // The parameters used to define the shape of the RTree.
+  const size_t min_children_;
+  const size_t max_children_;
+
+  DISALLOW_COPY_AND_ASSIGN(RTreeBase);
+};
+
+}  // namespace gfx
+
+#endif  // UI_GFX_GEOMETRY_R_TREE_BASE_H_
diff --git a/ui/gfx/geometry/r_tree_unittest.cc b/ui/gfx/geometry/r_tree_unittest.cc
index a98c57e..ba45405 100644
--- a/ui/gfx/geometry/r_tree_unittest.cc
+++ b/ui/gfx/geometry/r_tree_unittest.cc
@@ -4,459 +4,344 @@
 
 #include "testing/gtest/include/gtest/gtest.h"
 #include "ui/gfx/geometry/r_tree.h"
+#include "ui/gfx/geometry/r_tree_base.h"
 #include "ui/gfx/geometry/rect.h"
 
 namespace gfx {
 
 class RTreeTest : public ::testing::Test {
  protected:
-  // Given a pointer to an RTree, traverse it and verify its internal structure
-  // is consistent with the RTree semantics.
-  void ValidateRTree(RTree* rt) {
+  typedef RTree<int> RT;
+
+  // Given a pointer to an RTree, traverse it and verify that its internal
+  // structure is consistent with RTree semantics.
+  void ValidateRTree(RTreeBase* rt) {
     // If RTree is empty it should have an empty rectangle.
-    if (!rt->root_->count()) {
-      EXPECT_TRUE(rt->root_->rect().IsEmpty());
-      EXPECT_EQ(rt->root_->level(), 0);
+    if (!rt->root()->count()) {
+      EXPECT_TRUE(rt->root()->rect().IsEmpty());
+      EXPECT_EQ(0, rt->root()->Level());
       return;
     }
     // Root is allowed to have fewer than min_children_ but never more than
     // max_children_.
-    EXPECT_LE(rt->root_->count(), rt->max_children_);
+    EXPECT_LE(rt->root()->count(), rt->max_children_);
     // The root should never be a record node.
-    EXPECT_GT(rt->root_->level(), -1);
-    EXPECT_FALSE(rt->root_->key());
+    EXPECT_GT(rt->root()->Level(), -1);
     // The root should never have a parent pointer.
-    EXPECT_FALSE(rt->root_->parent());
+    EXPECT_TRUE(rt->root()->parent() == NULL);
     // Bounds must be consistent on the root.
-    CheckBoundsConsistent(rt->root_.get());
-    // We traverse root's children ourselves, so we can avoid asserts about
-    // root's potential inconsistencies.
-    for (size_t i = 0; i < rt->root_->children_.size(); ++i) {
+    CheckBoundsConsistent(rt->root());
+    for (size_t i = 0; i < rt->root()->count(); ++i) {
       ValidateNode(
-          rt->root_->children_[i], rt->min_children_, rt->max_children_);
+          rt->root()->child(i), rt->min_children_, rt->max_children_);
     }
   }
 
   // Recursive descent method used by ValidateRTree to check each node within
   // the RTree for consistency with RTree semantics.
-  void ValidateNode(RTree::Node* node,
+  void ValidateNode(const RTreeBase::NodeBase* node_base,
                     size_t min_children,
                     size_t max_children) {
-    // Record nodes have different requirements, handle up front.
-    if (node->level() == -1) {
-      // Record nodes may have no children.
-      EXPECT_EQ(node->count(), 0U);
-      // They must have an associated non-NULL key.
-      EXPECT_TRUE(node->key());
-      // They must always have a parent.
-      EXPECT_TRUE(node->parent());
-      return;
-    }
-    // Non-record node, normal expectations apply.
-    EXPECT_GE(node->count(), min_children);
-    EXPECT_LE(node->count(), max_children);
-    EXPECT_EQ(node->key(), 0);
-    CheckBoundsConsistent(node);
-    for (size_t i = 0; i < node->children_.size(); ++i) {
-      ValidateNode(node->children_[i], min_children, max_children);
+    if (node_base->Level() >= 0) {
+      const RTreeBase::Node* node =
+          static_cast<const RTreeBase::Node*>(node_base);
+      EXPECT_GE(node->count(), min_children);
+      EXPECT_LE(node->count(), max_children);
+      CheckBoundsConsistent(node);
+      for (size_t i = 0; i < node->count(); ++i)
+        ValidateNode(node->child(i), min_children, max_children);
     }
   }
 
   // Check bounds are consistent with children bounds, and other checks
   // convenient to do while enumerating the children of node.
-  void CheckBoundsConsistent(RTree::Node* node) {
-    EXPECT_FALSE(node->rect_.IsEmpty());
+  void CheckBoundsConsistent(const RTreeBase::Node* node) {
+    EXPECT_FALSE(node->rect().IsEmpty());
     Rect check_bounds;
-    for (size_t i = 0; i < node->children_.size(); ++i) {
-      RTree::Node* child_node = node->children_[i];
+    for (size_t i = 0; i < node->count(); ++i) {
+      const RTreeBase::NodeBase* child_node = node->child(i);
       check_bounds.Union(child_node->rect());
-      EXPECT_EQ(node->level() - 1, child_node->level());
+      EXPECT_EQ(node->Level() - 1, child_node->Level());
       EXPECT_EQ(node, child_node->parent());
     }
-    EXPECT_EQ(node->rect_, check_bounds);
+    EXPECT_EQ(check_bounds, node->rect());
   }
 
   // Adds count squares stacked around the point (0,0) with key equal to width.
-  void AddStackedSquares(RTree* rt, int count) {
+  void AddStackedSquares(RT* rt, int count) {
     for (int i = 1; i <= count; ++i) {
       rt->Insert(Rect(0, 0, i, i), i);
-      ValidateRTree(rt);
+      ValidateRTree(static_cast<RTreeBase*>(rt));
     }
   }
 
-  // Given an unordered list of matching keys, verify that it contains all
+  // Given an unordered list of matching keys, verifies that it contains all
   // values [1..length] for the length of that list.
-  void VerifyAllKeys(const base::hash_set<intptr_t>& keys) {
-    // Verify that the keys are in values [1,count].
-    for (size_t i = 1; i <= keys.size(); ++i) {
-      EXPECT_EQ(keys.count(i), 1U);
-    }
+  void VerifyAllKeys(const RT::Matches& keys) {
+    for (size_t i = 1; i <= keys.size(); ++i)
+      EXPECT_EQ(1U, keys.count(i));
   }
 
   // Given a node and a rectangle, builds an expanded rectangle list where the
-  // ith element of the rectangle is union of the recangle of the ith child of
+  // ith element of the vector is the union of the rectangle of the ith child of
   // the node and the argument rectangle.
-  void BuildExpandedRects(RTree::Node* node,
+  void BuildExpandedRects(RTreeBase::Node* node,
                           const Rect& rect,
                           std::vector<Rect>* expanded_rects) {
     expanded_rects->clear();
-    expanded_rects->reserve(node->children_.size());
-    for (size_t i = 0; i < node->children_.size(); ++i) {
+    expanded_rects->reserve(node->count());
+    for (size_t i = 0; i < node->count(); ++i) {
       Rect expanded_rect(rect);
-      expanded_rect.Union(node->children_[i]->rect_);
+      expanded_rect.Union(node->child(i)->rect());
       expanded_rects->push_back(expanded_rect);
     }
   }
 };
 
-// An empty RTree should never return Query results, and RTrees should be empty
-// upon construction.
-TEST_F(RTreeTest, QueryEmptyTree) {
-  RTree rt(2, 10);
-  ValidateRTree(&rt);
-  base::hash_set<intptr_t> results;
-  Rect test_rect(25, 25);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 0U);
-  ValidateRTree(&rt);
-}
-
-// Clear should empty the tree, meaning that all queries should not return
-// results after.
-TEST_F(RTreeTest, ClearEmptiesTreeOfSingleNode) {
-  RTree rt(2, 5);
-  rt.Insert(Rect(0, 0, 100, 100), 1);
-  rt.Clear();
-  base::hash_set<intptr_t> results;
-  Rect test_rect(1, 1);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 0U);
-  ValidateRTree(&rt);
-}
-
-// Even with a complex internal structure, clear should empty the tree, meaning
-// that all queries should not return results after.
-TEST_F(RTreeTest, ClearEmptiesTreeOfManyNodes) {
-  RTree rt(2, 5);
-  AddStackedSquares(&rt, 100);
-  rt.Clear();
-  base::hash_set<intptr_t> results;
-  Rect test_rect(1, 1);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 0U);
-  ValidateRTree(&rt);
-}
-
-// Duplicate inserts should overwrite previous inserts.
-TEST_F(RTreeTest, DuplicateInsertsOverwrite) {
-  RTree rt(2, 5);
-  // Add 100 stacked squares, but always with duplicate key of 1.
-  for (int i = 1; i <= 100; ++i) {
-    rt.Insert(Rect(0, 0, i, i), 1);
-    ValidateRTree(&rt);
+class RTreeNodeTest : public RTreeTest {
+ protected:
+  typedef RTreeBase::NodeBase RTreeNodeBase;
+  typedef RT::Record RTreeRecord;
+  typedef RTreeBase::Node RTreeNode;
+  typedef RTreeBase::Node::Rects RTreeRects;
+  typedef RTreeBase::Nodes RTreeNodes;
+
+  // Accessors to private members of RTree::Node.
+  const RTreeRecord* record(RTreeNode* node, size_t i) {
+    return static_cast<const RTreeRecord*>(node->child(i));
   }
-  base::hash_set<intptr_t> results;
-  Rect test_rect(1, 1);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 1U);
-  EXPECT_EQ(results.count(1), 1U);
-}
 
-// Call Remove() once on something that's been inserted repeatedly.
-TEST_F(RTreeTest, DuplicateInsertRemove) {
-  RTree rt(3, 9);
-  AddStackedSquares(&rt, 25);
-  for (int i = 1; i <= 100; ++i) {
-    rt.Insert(Rect(0, 0, i, i), 26);
-    ValidateRTree(&rt);
+  // Provides access for tests to private methods of RTree::Node.
+  scoped_ptr<RTreeNode> NewNodeAtLevel(size_t level) {
+    return make_scoped_ptr(new RTreeBase::Node(level));
   }
-  rt.Remove(26);
-  base::hash_set<intptr_t> results;
-  Rect test_rect(1, 1);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 25U);
-  VerifyAllKeys(results);
-}
 
-// Call Remove() repeatedly on something that's been inserted once.
-TEST_F(RTreeTest, InsertDuplicateRemove) {
-  RTree rt(7, 15);
-  AddStackedSquares(&rt, 101);
-  for (int i = 0; i < 100; ++i) {
-    rt.Remove(101);
-    ValidateRTree(&rt);
+  void NodeRecomputeLocalBounds(RTreeNodeBase* node) {
+    node->RecomputeLocalBounds();
   }
-  base::hash_set<intptr_t> results;
-  Rect test_rect(1, 1);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 100U);
-  VerifyAllKeys(results);
-}
-
-// Stacked rects should meet all matching queries regardless of nesting.
-TEST_F(RTreeTest, QueryStackedSquaresNestedHit) {
-  RTree rt(2, 5);
-  AddStackedSquares(&rt, 100);
-  base::hash_set<intptr_t> results;
-  Rect test_rect(1, 1);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 100U);
-  VerifyAllKeys(results);
-}
 
-// Stacked rects should meet all matching queries when contained completely by
-// the query rectangle.
-TEST_F(RTreeTest, QueryStackedSquaresContainedHit) {
-  RTree rt(2, 10);
-  AddStackedSquares(&rt, 100);
-  base::hash_set<intptr_t> results;
-  Rect test_rect(0, 0, 100, 100);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 100U);
-  VerifyAllKeys(results);
-}
+  bool NodeCompareVertical(RTreeNodeBase* a, RTreeNodeBase* b) {
+    return RTreeBase::Node::CompareVertical(a, b);
+  }
 
-// Stacked rects should miss a missing query when the query has no intersection
-// with the rects.
-TEST_F(RTreeTest, QueryStackedSquaresCompleteMiss) {
-  RTree rt(2, 7);
-  AddStackedSquares(&rt, 100);
-  base::hash_set<intptr_t> results;
-  Rect test_rect(150, 150, 100, 100);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 0U);
-}
+  bool NodeCompareHorizontal(RTreeNodeBase* a, RTreeNodeBase* b) {
+    return RTreeBase::Node::CompareHorizontal(a, b);
+  }
 
-// Removing half the nodes after insertion should still result in a valid tree.
-TEST_F(RTreeTest, RemoveHalfStackedRects) {
-  RTree rt(2, 11);
-  AddStackedSquares(&rt, 200);
-  for (int i = 101; i <= 200; ++i) {
-    rt.Remove(i);
-    ValidateRTree(&rt);
+  bool NodeCompareCenterDistanceFromParent(
+      const RTreeNodeBase* a, const RTreeNodeBase* b) {
+    return RTreeBase::Node::CompareCenterDistanceFromParent(a, b);
   }
-  base::hash_set<intptr_t> results;
-  Rect test_rect(1, 1);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 100U);
-  VerifyAllKeys(results);
-  // Add the nodes back in.
-  for (int i = 101; i <= 200; ++i) {
-    rt.Insert(Rect(0, 0, i, i), i);
-    ValidateRTree(&rt);
+
+  int NodeOverlapIncreaseToAdd(RTreeNode* node,
+                               const Rect& rect,
+                               const RTreeNodeBase* candidate_node,
+                               const Rect& expanded_rect) {
+    return node->OverlapIncreaseToAdd(rect, candidate_node, expanded_rect);
   }
-  results.clear();
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 200U);
-  VerifyAllKeys(results);
-}
 
-TEST_F(RTreeTest, InsertDupToRoot) {
-  RTree rt(2, 5);
-  rt.Insert(Rect(0, 0, 1, 2), 1);
-  ValidateRTree(&rt);
-  rt.Insert(Rect(0, 0, 2, 1), 1);
-  ValidateRTree(&rt);
-}
+  void NodeBuildLowBounds(const std::vector<RTreeNodeBase*>& vertical_sort,
+                          const std::vector<RTreeNodeBase*>& horizontal_sort,
+                          RTreeRects* vertical_bounds,
+                          RTreeRects* horizontal_bounds) {
+    RTreeBase::Node::BuildLowBounds(
+        vertical_sort, horizontal_sort, vertical_bounds, horizontal_bounds);
+  }
 
-TEST_F(RTreeTest, InsertNegativeCoordsRect) {
-  RTree rt(5, 11);
-  for (int i = 1; i <= 100; ++i) {
-    rt.Insert(Rect(-i, -i, i, i), (i * 2) - 1);
-    ValidateRTree(&rt);
-    rt.Insert(Rect(0, 0, i, i), i * 2);
-    ValidateRTree(&rt);
+  void NodeBuildHighBounds(const std::vector<RTreeNodeBase*>& vertical_sort,
+                           const std::vector<RTreeNodeBase*>& horizontal_sort,
+                           RTreeRects* vertical_bounds,
+                           RTreeRects* horizontal_bounds) {
+    RTreeBase::Node::BuildHighBounds(
+        vertical_sort, horizontal_sort, vertical_bounds, horizontal_bounds);
   }
-  base::hash_set<intptr_t> results;
-  Rect test_rect(-1, -1, 2, 2);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 200U);
-  VerifyAllKeys(results);
-}
 
-TEST_F(RTreeTest, RemoveNegativeCoordsRect) {
-  RTree rt(7, 21);
-  // Add 100 positive stacked squares.
-  AddStackedSquares(&rt, 100);
-  // Now add 100 negative stacked squares.
-  for (int i = 101; i <= 200; ++i) {
-    rt.Insert(Rect(100 - i, 100 - i, i - 100, i - 100), 301 - i);
-    ValidateRTree(&rt);
+  int NodeSmallestMarginSum(size_t start_index,
+                            size_t end_index,
+                            const RTreeRects& low_bounds,
+                            const RTreeRects& high_bounds) {
+    return RTreeBase::Node::SmallestMarginSum(
+        start_index, end_index, low_bounds, high_bounds);
   }
-  // Now remove half of the negative squares.
-  for (int i = 101; i <= 150; ++i) {
-    rt.Remove(301 - i);
-    ValidateRTree(&rt);
+
+  size_t NodeChooseSplitIndex(size_t min_children,
+                              size_t max_children,
+                              const RTreeRects& low_bounds,
+                              const RTreeRects& high_bounds) {
+    return RTreeBase::Node::ChooseSplitIndex(
+        min_children, max_children, low_bounds, high_bounds);
   }
-  // Queries should return 100 positive and 50 negative stacked squares.
-  base::hash_set<intptr_t> results;
-  Rect test_rect(-1, -1, 2, 2);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 150U);
-  VerifyAllKeys(results);
-}
 
-TEST_F(RTreeTest, InsertEmptyRectReplacementRemovesKey) {
-  RTree rt(10, 31);
-  AddStackedSquares(&rt, 50);
-  ValidateRTree(&rt);
+  scoped_ptr<RTreeNodeBase> NodeDivideChildren(
+      RTreeNode* node,
+      const RTreeRects& low_bounds,
+      const RTreeRects& high_bounds,
+      const std::vector<RTreeNodeBase*>& sorted_children,
+      size_t split_index) {
+    return node->DivideChildren(
+        low_bounds, high_bounds, sorted_children, split_index);
+  }
 
-  // Replace last square with empty rect.
-  rt.Insert(Rect(), 50);
-  ValidateRTree(&rt);
+  RTreeNode* NodeLeastOverlapIncrease(RTreeNode* node,
+                                      const Rect& node_rect,
+                                      const RTreeRects& expanded_rects) {
+    return node->LeastOverlapIncrease(node_rect, expanded_rects);
+  }
 
-  // Now query large area to get all rects in tree.
-  base::hash_set<intptr_t> results;
-  Rect test_rect(0, 0, 100, 100);
-  rt.Query(test_rect, &results);
+  RTreeNode* NodeLeastAreaEnlargement(RTreeNode* node,
+                                      const Rect& node_rect,
+                                      const RTreeRects& expanded_rects) {
+    return node->LeastAreaEnlargement(node_rect, expanded_rects);
+  }
+};
 
-  // Should only be 49 rects in tree.
-  EXPECT_EQ(results.size(), 49U);
-  VerifyAllKeys(results);
-}
+// RTreeNodeTest --------------------------------------------------------------
 
-TEST_F(RTreeTest, NodeRemoveNodesForReinsert) {
+TEST_F(RTreeNodeTest, RemoveNodesForReinsert) {
   // Make a leaf node for testing removal from.
-  scoped_ptr<RTree::Node> test_node(new RTree::Node(0));
+  scoped_ptr<RTreeNode> test_node(new RTreeNode);
   // Build 20 record nodes with rectangle centers going from (1,1) to (20,20)
-  for (int i = 1; i <= 20; ++i) {
-    test_node->AddChild(new RTree::Node(Rect(i - 1, i - 1, 2, 2), i));
-  }
+  for (int i = 1; i <= 20; ++i)
+    test_node->AddChild(scoped_ptr<RTreeNodeBase>(
+        new RTreeRecord(Rect(i - 1, i - 1, 2, 2), i)));
+
   // Quick verification of the node before removing children.
   ValidateNode(test_node.get(), 1U, 20U);
   // Use a scoped vector to delete all children that get removed from the Node.
-  ScopedVector<RTree::Node> removals;
+  RTreeNodes removals;
   test_node->RemoveNodesForReinsert(1, &removals);
-  // Should have gotten back 1 node pointers.
-  EXPECT_EQ(removals.size(), 1U);
+  // Should have gotten back 1 node pointer.
+  EXPECT_EQ(1U, removals.size());
   // There should be 19 left in the test_node.
-  EXPECT_EQ(test_node->count(), 19U);
+  EXPECT_EQ(19U, test_node->count());
   // If we fix up the bounds on the test_node, it should verify.
-  test_node->RecomputeBoundsNoParents();
+  NodeRecomputeLocalBounds(test_node.get());
   ValidateNode(test_node.get(), 2U, 20U);
   // The node we removed should be node 10, as it was exactly in the center.
-  EXPECT_EQ(removals[0]->key(), 10);
+  EXPECT_EQ(10, static_cast<RTreeRecord*>(removals[0])->key());
 
   // Now remove the next 2.
   removals.clear();
   test_node->RemoveNodesForReinsert(2, &removals);
-  EXPECT_EQ(removals.size(), 2U);
-  EXPECT_EQ(test_node->count(), 17U);
-  test_node->RecomputeBoundsNoParents();
+  EXPECT_EQ(2U, removals.size());
+  EXPECT_EQ(17U, test_node->count());
+  NodeRecomputeLocalBounds(test_node.get());
   ValidateNode(test_node.get(), 2U, 20U);
   // Lastly the 2 nodes we should have gotten back are keys 9 and 11, as their
   // centers were the closest to the center of the node bounding box.
   base::hash_set<intptr_t> results_hash;
-  results_hash.insert(removals[0]->key());
-  results_hash.insert(removals[1]->key());
-  EXPECT_EQ(results_hash.count(9), 1U);
-  EXPECT_EQ(results_hash.count(11), 1U);
+  results_hash.insert(static_cast<RTreeRecord*>(removals[0])->key());
+  results_hash.insert(static_cast<RTreeRecord*>(removals[1])->key());
+  EXPECT_EQ(1U, results_hash.count(9));
+  EXPECT_EQ(1U, results_hash.count(11));
 }
 
-TEST_F(RTreeTest, NodeCompareVertical) {
-  // One rect with lower y than another should always sort lower than higher y.
-  RTree::Node low(Rect(0, 1, 10, 10), 1);
-  RTree::Node middle(Rect(0, 5, 10, 10), 5);
-  EXPECT_TRUE(RTree::Node::CompareVertical(&low, &middle));
-  EXPECT_FALSE(RTree::Node::CompareVertical(&middle, &low));
+TEST_F(RTreeNodeTest, CompareVertical) {
+  // One rect with lower y than another should always sort lower.
+  RTreeRecord low(Rect(0, 1, 10, 10), 1);
+  RTreeRecord middle(Rect(0, 5, 10, 10), 5);
+  EXPECT_TRUE(NodeCompareVertical(&low, &middle));
+  EXPECT_FALSE(NodeCompareVertical(&middle, &low));
 
   // Try a non-overlapping higher-y rectangle.
-  RTree::Node high(Rect(-10, 20, 10, 1), 10);
-  EXPECT_TRUE(RTree::Node::CompareVertical(&low, &high));
-  EXPECT_FALSE(RTree::Node::CompareVertical(&high, &low));
+  RTreeRecord high(Rect(-10, 20, 10, 1), 10);
+  EXPECT_TRUE(NodeCompareVertical(&low, &high));
+  EXPECT_FALSE(NodeCompareVertical(&high, &low));
 
   // Ties are broken by lowest bottom y value.
-  RTree::Node shorter_tie(Rect(10, 1, 100, 2), 2);
-  EXPECT_TRUE(RTree::Node::CompareVertical(&shorter_tie, &low));
-  EXPECT_FALSE(RTree::Node::CompareVertical(&low, &shorter_tie));
+  RTreeRecord shorter_tie(Rect(10, 1, 100, 2), 2);
+  EXPECT_TRUE(NodeCompareVertical(&shorter_tie, &low));
+  EXPECT_FALSE(NodeCompareVertical(&low, &shorter_tie));
 }
 
-TEST_F(RTreeTest, NodeCompareHorizontal) {
+TEST_F(RTreeNodeTest, CompareHorizontal) {
   // One rect with lower x than another should always sort lower than higher x.
-  RTree::Node low(Rect(1, 0, 10, 10), 1);
-  RTree::Node middle(Rect(5, 0, 10, 10), 5);
-  EXPECT_TRUE(RTree::Node::CompareHorizontal(&low, &middle));
-  EXPECT_FALSE(RTree::Node::CompareHorizontal(&middle, &low));
+  RTreeRecord low(Rect(1, 0, 10, 10), 1);
+  RTreeRecord middle(Rect(5, 0, 10, 10), 5);
+  EXPECT_TRUE(NodeCompareHorizontal(&low, &middle));
+  EXPECT_FALSE(NodeCompareHorizontal(&middle, &low));
 
   // Try a non-overlapping higher-x rectangle.
-  RTree::Node high(Rect(20, -10, 1, 10), 10);
-  EXPECT_TRUE(RTree::Node::CompareHorizontal(&low, &high));
-  EXPECT_FALSE(RTree::Node::CompareHorizontal(&high, &low));
+  RTreeRecord high(Rect(20, -10, 1, 10), 10);
+  EXPECT_TRUE(NodeCompareHorizontal(&low, &high));
+  EXPECT_FALSE(NodeCompareHorizontal(&high, &low));
 
   // Ties are broken by lowest bottom x value.
-  RTree::Node shorter_tie(Rect(1, 10, 2, 100), 2);
-  EXPECT_TRUE(RTree::Node::CompareHorizontal(&shorter_tie, &low));
-  EXPECT_FALSE(RTree::Node::CompareHorizontal(&low, &shorter_tie));
+  RTreeRecord shorter_tie(Rect(1, 10, 2, 100), 2);
+  EXPECT_TRUE(NodeCompareHorizontal(&shorter_tie, &low));
+  EXPECT_FALSE(NodeCompareHorizontal(&low, &shorter_tie));
 }
 
-TEST_F(RTreeTest, NodeCompareCenterDistanceFromParent) {
+TEST_F(RTreeNodeTest, CompareCenterDistanceFromParent) {
   // Create a test node we can add children to, for distance comparisons.
-  scoped_ptr<RTree::Node> parent(new RTree::Node(0));
+  scoped_ptr<RTreeNode> parent(new RTreeNode);
 
   // Add three children, one each with centers at (0, 0), (10, 10), (-9, -9),
   // around which a bounding box will be centered at (0, 0)
-  RTree::Node* center_zero = new RTree::Node(Rect(-1, -1, 2, 2), 1);
-  parent->AddChild(center_zero);
+  scoped_ptr<RTreeRecord> center_zero(new RTreeRecord(Rect(-1, -1, 2, 2), 1));
+  parent->AddChild(center_zero.PassAs<RTreeNodeBase>());
 
-  RTree::Node* center_positive = new RTree::Node(Rect(9, 9, 2, 2), 2);
-  parent->AddChild(center_positive);
+  scoped_ptr<RTreeRecord> center_positive(new RTreeRecord(Rect(9, 9, 2, 2), 2));
+  parent->AddChild(center_positive.PassAs<RTreeNodeBase>());
 
-  RTree::Node* center_negative = new RTree::Node(Rect(-10, -10, 2, 2), 3);
-  parent->AddChild(center_negative);
+  scoped_ptr<RTreeRecord> center_negative(
+      new RTreeRecord(Rect(-10, -10, 2, 2), 3));
+  parent->AddChild(center_negative.PassAs<RTreeNodeBase>());
 
   ValidateNode(parent.get(), 1U, 5U);
-  EXPECT_EQ(parent->rect_, Rect(-10, -10, 21, 21));
-
-  EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_zero,
-                                                           center_positive));
-  EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_positive,
-                                                            center_zero));
-
-  EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_zero,
-                                                           center_negative));
-  EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_negative,
-                                                            center_zero));
-
-  EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_negative,
-                                                           center_positive));
-  EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_positive,
-                                                            center_negative));
+  EXPECT_EQ(Rect(-10, -10, 21, 21), parent->rect());
+
+  EXPECT_TRUE(
+      NodeCompareCenterDistanceFromParent(parent->child(0), parent->child(1)));
+  EXPECT_FALSE(
+      NodeCompareCenterDistanceFromParent(parent->child(1), parent->child(0)));
+  EXPECT_TRUE(
+      NodeCompareCenterDistanceFromParent(parent->child(0), parent->child(2)));
+  EXPECT_FALSE(
+      NodeCompareCenterDistanceFromParent(parent->child(2), parent->child(0)));
+  EXPECT_TRUE(
+      NodeCompareCenterDistanceFromParent(parent->child(2), parent->child(1)));
+  EXPECT_FALSE(
+      NodeCompareCenterDistanceFromParent(parent->child(1), parent->child(2)));
 }
 
-TEST_F(RTreeTest, NodeOverlapIncreaseToAdd) {
+TEST_F(RTreeNodeTest, OverlapIncreaseToAdd) {
   // Create a test node with three children, for overlap comparisons.
-  scoped_ptr<RTree::Node> parent(new RTree::Node(0));
+  scoped_ptr<RTreeNode> parent(new RTreeNode);
 
   // Add three children, each 4 wide and tall, at (0, 0), (3, 3), (6, 6) with
   // overlapping corners.
   Rect top(0, 0, 4, 4);
-  parent->AddChild(new RTree::Node(top, 1));
+  parent->AddChild(scoped_ptr<RTreeNodeBase>(new RTreeRecord(top, 1)));
   Rect middle(3, 3, 4, 4);
-  parent->AddChild(new RTree::Node(middle, 2));
+  parent->AddChild(scoped_ptr<RTreeNodeBase>(new RTreeRecord(middle, 2)));
   Rect bottom(6, 6, 4, 4);
-  parent->AddChild(new RTree::Node(bottom, 3));
+  parent->AddChild(scoped_ptr<RTreeNodeBase>(new RTreeRecord(bottom, 3)));
   ValidateNode(parent.get(), 1U, 5U);
 
   // Test a rect in corner.
   Rect corner(0, 0, 1, 1);
   Rect expanded = top;
   expanded.Union(corner);
-  // It should not add any overlap to add this to the first child at (0, 0);
-  EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 0, expanded), 0);
+  // It should not add any overlap to add this to the first child at (0, 0).
+  EXPECT_EQ(0, NodeOverlapIncreaseToAdd(
+      parent.get(), corner, parent->child(0), expanded));
 
   expanded = middle;
   expanded.Union(corner);
   // Overlap for middle rectangle should increase from 2 pixels at (3, 3) and
   // (6, 6) to 17 pixels, as it will now cover 4x4 rectangle top,
-  // so a change of +15
-  EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 1, expanded), 15);
+  // so a change of +15.
+  EXPECT_EQ(15, NodeOverlapIncreaseToAdd(
+      parent.get(), corner, parent->child(1), expanded));
 
   expanded = bottom;
   expanded.Union(corner);
   // Overlap for bottom rectangle should increase from 1 pixel at (6, 6) to
   // 32 pixels, as it will now cover both 4x4 rectangles top and middle,
-  // so a change of 31
-  EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 2, expanded), 31);
+  // so a change of 31.
+  EXPECT_EQ(31, NodeOverlapIncreaseToAdd(
+      parent.get(), corner, parent->child(2), expanded));
 
   // Test a rect that doesn't overlap with anything, in the far right corner.
   Rect far_corner(9, 0, 1, 1);
@@ -464,58 +349,61 @@ TEST_F(RTreeTest, NodeOverlapIncreaseToAdd) {
   expanded.Union(far_corner);
   // Overlap of top should go from 1 to 4, as it will now cover the entire first
   // row of pixels in middle.
-  EXPECT_EQ(parent->OverlapIncreaseToAdd(far_corner, 0, expanded), 3);
+  EXPECT_EQ(3, NodeOverlapIncreaseToAdd(
+      parent.get(), far_corner, parent->child(0), expanded));
 
   expanded = middle;
   expanded.Union(far_corner);
   // Overlap of middle should go from 2 to 8, as it will cover the rightmost 4
-  // pixels of top and the top 4 pixles of bottom as it expands.
-  EXPECT_EQ(parent->OverlapIncreaseToAdd(far_corner, 1, expanded), 6);
+  // pixels of top and the top 4 pixels of bottom as it expands.
+  EXPECT_EQ(6, NodeOverlapIncreaseToAdd(
+      parent.get(), far_corner, parent->child(1), expanded));
 
   expanded = bottom;
   expanded.Union(far_corner);
   // Overlap of bottom should go from 1 to 4, as it will now cover the rightmost
   // 4 pixels of middle.
-  EXPECT_EQ(parent->OverlapIncreaseToAdd(far_corner, 2, expanded), 3);
+  EXPECT_EQ(3, NodeOverlapIncreaseToAdd(
+      parent.get(), far_corner, parent->child(2), expanded));
 }
 
-TEST_F(RTreeTest, NodeBuildLowBounds) {
-  ScopedVector<RTree::Node> nodes;
-  nodes.reserve(10);
-  for (int i = 1; i <= 10; ++i) {
-    nodes.push_back(new RTree::Node(Rect(0, 0, i, i), i));
-  }
-  std::vector<Rect> vertical_bounds;
-  std::vector<Rect> horizontal_bounds;
-  RTree::Node::BuildLowBounds(
-      nodes.get(), nodes.get(), &vertical_bounds, &horizontal_bounds);
+TEST_F(RTreeNodeTest, BuildLowBounds) {
+  RTreeNodes records;
+  records.reserve(10);
+  for (int i = 1; i <= 10; ++i)
+    records.push_back(new RTreeRecord(Rect(0, 0, i, i), i));
+
+  RTreeRects vertical_bounds;
+  RTreeRects horizontal_bounds;
+  NodeBuildLowBounds(
+      records.get(), records.get(), &vertical_bounds, &horizontal_bounds);
   for (int i = 0; i < 10; ++i) {
-    EXPECT_EQ(vertical_bounds[i], Rect(0, 0, i + 1, i + 1));
-    EXPECT_EQ(horizontal_bounds[i], Rect(0, 0, i + 1, i + 1));
+    EXPECT_EQ(records[i]->rect(), vertical_bounds[i]);
+    EXPECT_EQ(records[i]->rect(), horizontal_bounds[i]);
   }
 }
 
-TEST_F(RTreeTest, NodeBuildHighBounds) {
-  ScopedVector<RTree::Node> nodes;
-  nodes.reserve(25);
-  for (int i = 0; i < 25; ++i) {
-    nodes.push_back(new RTree::Node(Rect(i, i, 25 - i, 25 - i), i));
-  }
-  std::vector<Rect> vertical_bounds;
-  std::vector<Rect> horizontal_bounds;
-  RTree::Node::BuildHighBounds(
-      nodes.get(), nodes.get(), &vertical_bounds, &horizontal_bounds);
+TEST_F(RTreeNodeTest, BuildHighBounds) {
+  RTreeNodes records;
+  records.reserve(25);
+  for (int i = 0; i < 25; ++i)
+    records.push_back(new RTreeRecord(Rect(i, i, 25 - i, 25 - i), i));
+
+  RTreeRects vertical_bounds;
+  RTreeRects horizontal_bounds;
+  NodeBuildHighBounds(
+      records.get(), records.get(), &vertical_bounds, &horizontal_bounds);
   for (int i = 0; i < 25; ++i) {
-    EXPECT_EQ(vertical_bounds[i], Rect(i, i, 25 - i, 25 - i));
-    EXPECT_EQ(horizontal_bounds[i], Rect(i, i, 25 - i, 25 - i));
+    EXPECT_EQ(records[i]->rect(), vertical_bounds[i]);
+    EXPECT_EQ(records[i]->rect(), horizontal_bounds[i]);
   }
 }
 
-TEST_F(RTreeTest, NodeChooseSplitAxisAndIndex) {
-  std::vector<Rect> low_vertical_bounds;
-  std::vector<Rect> high_vertical_bounds;
-  std::vector<Rect> low_horizontal_bounds;
-  std::vector<Rect> high_horizontal_bounds;
+TEST_F(RTreeNodeTest, ChooseSplitAxisAndIndexVertical) {
+  RTreeRects low_vertical_bounds;
+  RTreeRects high_vertical_bounds;
+  RTreeRects low_horizontal_bounds;
+  RTreeRects high_horizontal_bounds;
   // In this test scenario we describe a mirrored, stacked configuration of
   // horizontal, 1 pixel high rectangles labeled a-f like this:
   //
@@ -538,9 +426,8 @@ TEST_F(RTreeTest, NodeChooseSplitAxisAndIndex) {
   // Low bounds of horizontal sort start with bounds of box a and then jump to
   // cover everything, as box f is second in horizontal sort.
   low_horizontal_bounds.push_back(Rect(0, 0, 5, 1));
-  for (int i = 0; i < 5; ++i) {
+  for (int i = 0; i < 5; ++i)
     low_horizontal_bounds.push_back(Rect(0, 0, 5, 6));
-  }
 
   // High horizontal bounds are hand-calculated.
   high_horizontal_bounds.push_back(Rect(0, 0, 5, 6));
@@ -550,18 +437,24 @@ TEST_F(RTreeTest, NodeChooseSplitAxisAndIndex) {
   high_horizontal_bounds.push_back(Rect(2, 2, 1, 2));
   high_horizontal_bounds.push_back(Rect(2, 3, 1, 1));
 
-  // This should split vertically, right down the middle.
-  EXPECT_TRUE(RTree::Node::ChooseSplitAxis(low_vertical_bounds,
-                                           high_vertical_bounds,
-                                           low_horizontal_bounds,
-                                           high_horizontal_bounds,
-                                           2,
-                                           5));
-  EXPECT_EQ(3U,
-            RTree::Node::ChooseSplitIndex(
-                2, 5, low_vertical_bounds, high_vertical_bounds));
+  int smallest_vertical_margin =
+      NodeSmallestMarginSum(2, 3, low_vertical_bounds, high_vertical_bounds);
+  int smallest_horizontal_margin = NodeSmallestMarginSum(
+      2, 3, low_horizontal_bounds, high_horizontal_bounds);
+  EXPECT_LT(smallest_vertical_margin, smallest_horizontal_margin);
+
+  EXPECT_EQ(
+      3U,
+      NodeChooseSplitIndex(2, 5, low_vertical_bounds, high_vertical_bounds));
+}
 
-  // We rotate the shape to test horizontal split axis detection:
+TEST_F(RTreeNodeTest, ChooseSplitAxisAndIndexHorizontal) {
+  RTreeRects low_vertical_bounds;
+  RTreeRects high_vertical_bounds;
+  RTreeRects low_horizontal_bounds;
+  RTreeRects high_horizontal_bounds;
+  // We rotate the shape from ChooseSplitAxisAndIndexVertical to test
+  // horizontal split axis detection:
   //
   //         +--------+
   //         | a    f |
@@ -574,18 +467,11 @@ TEST_F(RTreeTest, NodeChooseSplitAxisAndIndex) {
   // h sort: | 012345 |
   //         +--------+
   //
-  // Clear out old bounds first.
-  low_vertical_bounds.clear();
-  high_vertical_bounds.clear();
-  low_horizontal_bounds.clear();
-  high_horizontal_bounds.clear();
-
   // Low bounds of vertical sort start with bounds of box a and then jump to
   // cover everything, as box f is second in vertical sort.
   low_vertical_bounds.push_back(Rect(0, 0, 1, 5));
-  for (int i = 0; i < 5; ++i) {
+  for (int i = 0; i < 5; ++i)
     low_vertical_bounds.push_back(Rect(0, 0, 6, 5));
-  }
 
   // High vertical bounds are hand-calculated.
   high_vertical_bounds.push_back(Rect(0, 0, 6, 5));
@@ -603,162 +489,178 @@ TEST_F(RTreeTest, NodeChooseSplitAxisAndIndex) {
     high_horizontal_bounds.push_back(Rect(i, 0, 6 - i, 5));
   }
 
-  // This should split horizontally, right down the middle.
-  EXPECT_FALSE(RTree::Node::ChooseSplitAxis(low_vertical_bounds,
-                                            high_vertical_bounds,
-                                            low_horizontal_bounds,
-                                            high_horizontal_bounds,
-                                            2,
-                                            5));
+  int smallest_vertical_margin =
+      NodeSmallestMarginSum(2, 3, low_vertical_bounds, high_vertical_bounds);
+  int smallest_horizontal_margin = NodeSmallestMarginSum(
+      2, 3, low_horizontal_bounds, high_horizontal_bounds);
+
+  EXPECT_GT(smallest_vertical_margin, smallest_horizontal_margin);
+
   EXPECT_EQ(3U,
-            RTree::Node::ChooseSplitIndex(
+            NodeChooseSplitIndex(
                 2, 5, low_horizontal_bounds, high_horizontal_bounds));
 }
 
-TEST_F(RTreeTest, NodeDivideChildren) {
+TEST_F(RTreeNodeTest, DivideChildren) {
   // Create a test node to split.
-  scoped_ptr<RTree::Node> test_node(new RTree::Node(0));
-  std::vector<RTree::Node*> sorted_children;
-  std::vector<Rect> low_bounds;
-  std::vector<Rect> high_bounds;
+  scoped_ptr<RTreeNode> test_node(new RTreeNode);
+  std::vector<RTreeNodeBase*> sorted_children;
+  RTreeRects low_bounds;
+  RTreeRects high_bounds;
   // Insert 10 record nodes, also inserting them into our children array.
   for (int i = 1; i <= 10; ++i) {
-    RTree::Node* node = new RTree::Node(Rect(0, 0, i, i), i);
-    test_node->AddChild(node);
-    sorted_children.push_back(node);
+    scoped_ptr<RTreeRecord> record(new RTreeRecord(Rect(0, 0, i, i), i));
+    sorted_children.push_back(record.get());
+    test_node->AddChild(record.PassAs<RTreeNodeBase>());
     low_bounds.push_back(Rect(0, 0, i, i));
     high_bounds.push_back(Rect(0, 0, 10, 10));
   }
   // Split the children in half.
-  scoped_ptr<RTree::Node> split_node(
-      test_node->DivideChildren(low_bounds, high_bounds, sorted_children, 5));
+  scoped_ptr<RTreeNodeBase> split_node_base(NodeDivideChildren(
+      test_node.get(), low_bounds, high_bounds, sorted_children, 5));
+  RTreeNode* split_node = static_cast<RTreeNode*>(split_node_base.get());
   // Both nodes should be valid.
   ValidateNode(test_node.get(), 1U, 10U);
-  ValidateNode(split_node.get(), 1U, 10U);
+  ValidateNode(split_node, 1U, 10U);
   // Both nodes should have five children.
-  EXPECT_EQ(test_node->children_.size(), 5U);
-  EXPECT_EQ(split_node->children_.size(), 5U);
+  EXPECT_EQ(5U, test_node->count());
+  EXPECT_EQ(5U, split_node->count());
   // Test node should have children 1-5, split node should have children 6-10.
   for (int i = 0; i < 5; ++i) {
-    EXPECT_EQ(test_node->children_[i]->key(), i + 1);
-    EXPECT_EQ(split_node->children_[i]->key(), i + 6);
+    EXPECT_EQ(i + 1, record(test_node.get(), i)->key());
+    EXPECT_EQ(i + 6, record(split_node, i)->key());
   }
 }
 
-TEST_F(RTreeTest, NodeRemoveChildNoOrphans) {
-  scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
-  scoped_ptr<RTree::Node> child_one(new RTree::Node(Rect(0, 0, 1, 1), 1));
-  scoped_ptr<RTree::Node> child_two(new RTree::Node(Rect(0, 0, 2, 2), 2));
-  scoped_ptr<RTree::Node> child_three(new RTree::Node(Rect(0, 0, 3, 3), 3));
-  test_parent->AddChild(child_one.get());
-  test_parent->AddChild(child_two.get());
-  test_parent->AddChild(child_three.get());
+TEST_F(RTreeNodeTest, RemoveChildNoOrphans) {
+  scoped_ptr<RTreeNode> test_parent(new RTreeNode);
+  test_parent->AddChild(
+      scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 1, 1), 1)));
+  test_parent->AddChild(
+      scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 2, 2), 2)));
+  test_parent->AddChild(
+    scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 3, 3), 3)));
   ValidateNode(test_parent.get(), 1U, 5U);
+
+  RTreeNodes orphans;
+
   // Remove the middle node.
-  ScopedVector<RTree::Node> orphans;
-  EXPECT_EQ(test_parent->RemoveChild(child_two.get(), &orphans), 2U);
-  EXPECT_EQ(orphans.size(), 0U);
-  EXPECT_EQ(test_parent->count(), 2U);
-  test_parent->RecomputeBoundsNoParents();
+  scoped_ptr<RTreeNodeBase> middle_child(
+      test_parent->RemoveChild(test_parent->child(1), &orphans));
+  EXPECT_EQ(0U, orphans.size());
+  EXPECT_EQ(2U, test_parent->count());
+  NodeRecomputeLocalBounds(test_parent.get());
   ValidateNode(test_parent.get(), 1U, 5U);
+
   // Remove the end node.
-  EXPECT_EQ(test_parent->RemoveChild(child_three.get(), &orphans), 1U);
-  EXPECT_EQ(orphans.size(), 0U);
-  EXPECT_EQ(test_parent->count(), 1U);
-  test_parent->RecomputeBoundsNoParents();
+  scoped_ptr<RTreeNodeBase> end_child(
+      test_parent->RemoveChild(test_parent->child(1), &orphans));
+  EXPECT_EQ(0U, orphans.size());
+  EXPECT_EQ(1U, test_parent->count());
+  NodeRecomputeLocalBounds(test_parent.get());
   ValidateNode(test_parent.get(), 1U, 5U);
+
   // Remove the first node.
-  EXPECT_EQ(test_parent->RemoveChild(child_one.get(), &orphans), 0U);
-  EXPECT_EQ(orphans.size(), 0U);
-  EXPECT_EQ(test_parent->count(), 0U);
+  scoped_ptr<RTreeNodeBase> first_child(
+      test_parent->RemoveChild(test_parent->child(0), &orphans));
+  EXPECT_EQ(0U, orphans.size());
+  EXPECT_EQ(0U, test_parent->count());
 }
 
-TEST_F(RTreeTest, NodeRemoveChildOrphans) {
-  // Build flattened binary tree of Nodes 4 deep, from the record nodes up.
-  ScopedVector<RTree::Node> nodes;
-  nodes.resize(15);
-  // Indicies 7 through 15 are record nodes.
-  for (int i = 7; i < 15; ++i) {
-    nodes[i] = new RTree::Node(Rect(0, 0, i, i), i);
-  }
-  // Nodes 3 through 6 are level 0 (leaves) and get 2 record nodes each.
-  for (int i = 3; i < 7; ++i) {
-    nodes[i] = new RTree::Node(0);
-    nodes[i]->AddChild(nodes[(i * 2) + 1]);
-    nodes[i]->AddChild(nodes[(i * 2) + 2]);
-  }
-  // Nodes 1 and 2 are level 1 and get 2 leaves each.
-  for (int i = 1; i < 3; ++i) {
-    nodes[i] = new RTree::Node(1);
-    nodes[i]->AddChild(nodes[(i * 2) + 1]);
-    nodes[i]->AddChild(nodes[(i * 2) + 2]);
-  }
-  // Node 0 is level 2 and gets 2 childen.
-  nodes[0] = new RTree::Node(2);
-  nodes[0]->AddChild(nodes[1]);
-  nodes[0]->AddChild(nodes[2]);
-  // This should now be a valid node structure.
-  ValidateNode(nodes[0], 2U, 2U);
-
-  // Now remove the level 0 nodes, so we get the record nodes as orphans.
-  ScopedVector<RTree::Node> orphans;
-  EXPECT_EQ(nodes[1]->RemoveChild(nodes[3], &orphans), 1U);
-  EXPECT_EQ(nodes[1]->RemoveChild(nodes[4], &orphans), 0U);
-  EXPECT_EQ(nodes[2]->RemoveChild(nodes[5], &orphans), 1U);
-  EXPECT_EQ(nodes[2]->RemoveChild(nodes[6], &orphans), 0U);
-
-  // Orphans should be nodes 7 through 15 in order.
-  EXPECT_EQ(orphans.size(), 8U);
-  for (int i = 0; i < 8; ++i) {
-    EXPECT_EQ(orphans[i], nodes[i + 7]);
-  }
-
-  // Now we remove nodes 1 and 2 from the root, expecting no further orphans.
-  // This prevents a crash due to double-delete on test exit, as no node should
-  // own any other node right now.
-  EXPECT_EQ(nodes[0]->RemoveChild(nodes[1], &orphans), 1U);
-  EXPECT_EQ(orphans.size(), 8U);
-  EXPECT_EQ(nodes[0]->RemoveChild(nodes[2], &orphans), 0U);
-  EXPECT_EQ(orphans.size(), 8U);
-
-  // Prevent double-delete of nodes by both nodes and orphans.
-  orphans.weak_clear();
+TEST_F(RTreeNodeTest, RemoveChildOrphans) {
+  // Build binary tree of Nodes of height 4, keeping weak pointers to the
+  // Levels 0 and 1 Nodes and the Records so we can test removal of them below.
+  std::vector<RTreeNode*> level_1_children;
+  std::vector<RTreeNode*> level_0_children;
+  std::vector<RTreeRecord*> records;
+  int id = 1;
+  scoped_ptr<RTreeNode> root(NewNodeAtLevel(2));
+  for (int i = 0; i < 2; ++i) {
+    scoped_ptr<RTreeNode> level_1_child(NewNodeAtLevel(1));
+    for (int j = 0; j < 2; ++j) {
+      scoped_ptr<RTreeNode> level_0_child(new RTreeNode);
+      for (int k = 0; k < 2; ++k) {
+        scoped_ptr<RTreeRecord> record(
+            new RTreeRecord(Rect(0, 0, id, id), id));
+        ++id;
+        records.push_back(record.get());
+        level_0_child->AddChild(record.PassAs<RTreeNodeBase>());
+      }
+      level_0_children.push_back(level_0_child.get());
+      level_1_child->AddChild(level_0_child.PassAs<RTreeNodeBase>());
+    }
+    level_1_children.push_back(level_1_child.get());
+    root->AddChild(level_1_child.PassAs<RTreeNodeBase>());
+  }
+
+  // This should now be a valid tree structure.
+  ValidateNode(root.get(), 2U, 2U);
+  EXPECT_EQ(2U, level_1_children.size());
+  EXPECT_EQ(4U, level_0_children.size());
+  EXPECT_EQ(8U, records.size());
+
+  // Now remove all of the level 0 nodes so we get the record nodes as orphans.
+  RTreeNodes orphans;
+  for (size_t i = 0; i < level_0_children.size(); ++i)
+    level_1_children[i / 2]->RemoveChild(level_0_children[i], &orphans);
+
+  // Orphans should be all 8 records but no order guarantee.
+  EXPECT_EQ(8U, orphans.size());
+  for (std::vector<RTreeRecord*>::iterator it = records.begin();
+      it != records.end(); ++it) {
+    RTreeNodes::iterator orphan =
+        std::find(orphans.begin(), orphans.end(), *it);
+    EXPECT_NE(orphan, orphans.end());
+    orphans.erase(orphan);
+  }
+  EXPECT_EQ(0U, orphans.size());
 }
 
-TEST_F(RTreeTest, NodeRemoveAndReturnLastChild) {
-  scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
-  scoped_ptr<RTree::Node> child_one(new RTree::Node(Rect(0, 0, 1, 1), 1));
-  scoped_ptr<RTree::Node> child_two(new RTree::Node(Rect(0, 0, 2, 2), 2));
-  scoped_ptr<RTree::Node> child_three(new RTree::Node(Rect(0, 0, 3, 3), 3));
-  test_parent->AddChild(child_one.get());
-  test_parent->AddChild(child_two.get());
-  test_parent->AddChild(child_three.get());
+TEST_F(RTreeNodeTest, RemoveAndReturnLastChild) {
+  scoped_ptr<RTreeNode> test_parent(new RTreeNode);
+  test_parent->AddChild(
+      scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 1, 1), 1)));
+  test_parent->AddChild(
+      scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 2, 2), 2)));
+  test_parent->AddChild(
+      scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 3, 3), 3)));
   ValidateNode(test_parent.get(), 1U, 5U);
 
-  EXPECT_EQ(test_parent->RemoveAndReturnLastChild().release(),
-            child_three.get());
-  EXPECT_EQ(test_parent->count(), 2U);
-  test_parent->RecomputeBoundsNoParents();
+  RTreeNodeBase* child = test_parent->child(2);
+  scoped_ptr<RTreeNodeBase> last_child(test_parent->RemoveAndReturnLastChild());
+  EXPECT_EQ(child, last_child.get());
+  EXPECT_EQ(2U, test_parent->count());
+  NodeRecomputeLocalBounds(test_parent.get());
   ValidateNode(test_parent.get(), 1U, 5U);
 
-  EXPECT_EQ(test_parent->RemoveAndReturnLastChild().release(), child_two.get());
-  EXPECT_EQ(test_parent->count(), 1U);
-  test_parent->RecomputeBoundsNoParents();
+  child = test_parent->child(1);
+  scoped_ptr<RTreeNodeBase> middle_child(
+      test_parent->RemoveAndReturnLastChild());
+  EXPECT_EQ(child, middle_child.get());
+  EXPECT_EQ(1U, test_parent->count());
+  NodeRecomputeLocalBounds(test_parent.get());
   ValidateNode(test_parent.get(), 1U, 5U);
 
-  EXPECT_EQ(test_parent->RemoveAndReturnLastChild().release(), child_one.get());
-  EXPECT_EQ(test_parent->count(), 0U);
+  child = test_parent->child(0);
+  scoped_ptr<RTreeNodeBase> first_child(
+      test_parent->RemoveAndReturnLastChild());
+  EXPECT_EQ(child, first_child.get());
+  EXPECT_EQ(0U, test_parent->count());
 }
 
-TEST_F(RTreeTest, NodeLeastOverlapIncrease) {
-  scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
-  // Construct 4 nodes with 1x2 retangles spaced horizontally 1 pixel apart, or:
+TEST_F(RTreeNodeTest, LeastOverlapIncrease) {
+  scoped_ptr<RTreeNode> test_parent(NewNodeAtLevel(1));
+  // Construct 4 nodes with 1x2 rects spaced horizontally 1 pixel apart, or:
   //
   // a b c d
   // a b c d
   //
   for (int i = 0; i < 4; ++i) {
-    test_parent->AddChild(new RTree::Node(Rect(i * 2, 0, 1, 2), i + 1));
+    scoped_ptr<RTreeNode> node(new RTreeNode);
+    scoped_ptr<RTreeRecord> record(
+        new RTreeRecord(Rect(i * 2, 0, 1, 2), i + 1));
+    node->AddChild(record.PassAs<RTreeNodeBase>());
+    test_parent->AddChild(node.PassAs<RTreeNodeBase>());
   }
 
   ValidateNode(test_parent.get(), 1U, 5U);
@@ -770,11 +672,11 @@ TEST_F(RTreeTest, NodeLeastOverlapIncrease) {
   // a b c d
   //
   Rect test_rect_far(7, 0, 1, 1);
-  std::vector<Rect> expanded_rects;
+  RTreeRects expanded_rects;
   BuildExpandedRects(test_parent.get(), test_rect_far, &expanded_rects);
-  RTree::Node* result =
-      test_parent->LeastOverlapIncrease(test_rect_far, expanded_rects);
-  EXPECT_EQ(result->key(), 4);
+  RTreeNode* result = NodeLeastOverlapIncrease(
+      test_parent.get(), test_rect_far, expanded_rects);
+  EXPECT_EQ(4, record(result, 0)->key());
 
   // Test rect covering the bottom half of all children should be a 4-way tie,
   // so LeastOverlapIncrease should return NULL:
@@ -784,7 +686,8 @@ TEST_F(RTreeTest, NodeLeastOverlapIncrease) {
   //
   Rect test_rect_tie(0, 1, 7, 1);
   BuildExpandedRects(test_parent.get(), test_rect_tie, &expanded_rects);
-  result = test_parent->LeastOverlapIncrease(test_rect_tie, expanded_rects);
+  result = NodeLeastOverlapIncrease(
+      test_parent.get(), test_rect_tie, expanded_rects);
   EXPECT_TRUE(result == NULL);
 
   // Test rect completely inside c should return the third rectangle:
@@ -794,8 +697,9 @@ TEST_F(RTreeTest, NodeLeastOverlapIncrease) {
   //
   Rect test_rect_inside(4, 0, 1, 1);
   BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects);
-  result = test_parent->LeastOverlapIncrease(test_rect_inside, expanded_rects);
-  EXPECT_EQ(result->key(), 3);
+  result = NodeLeastOverlapIncrease(
+      test_parent.get(), test_rect_inside, expanded_rects);
+  EXPECT_EQ(3, record(result, 0)->key());
 
   // Add a rectangle that overlaps completely with rectangle c, to test
   // when there is a tie between two completely contained rectangles:
@@ -803,24 +707,40 @@ TEST_F(RTreeTest, NodeLeastOverlapIncrease) {
   // a b Ted
   // a b eed
   //
-  test_parent->AddChild(new RTree::Node(Rect(4, 0, 2, 2), 9));
+  scoped_ptr<RTreeNode> record_parent(new RTreeNode);
+  record_parent->AddChild(
+      scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(4, 0, 2, 2), 9)));
+  test_parent->AddChild(record_parent.PassAs<RTreeNodeBase>());
   BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects);
-  result = test_parent->LeastOverlapIncrease(test_rect_inside, expanded_rects);
+  result = NodeLeastOverlapIncrease(
+      test_parent.get(), test_rect_inside, expanded_rects);
   EXPECT_TRUE(result == NULL);
 }
 
-TEST_F(RTreeTest, NodeLeastAreaEnlargement) {
-  scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
+TEST_F(RTreeNodeTest, LeastAreaEnlargement) {
+  scoped_ptr<RTreeNode> test_parent(NewNodeAtLevel(1));
   // Construct 4 nodes in a cross-hairs style configuration:
   //
   //  a
   // b c
   //  d
   //
-  test_parent->AddChild(new RTree::Node(Rect(1, 0, 1, 1), 1));
-  test_parent->AddChild(new RTree::Node(Rect(0, 1, 1, 1), 2));
-  test_parent->AddChild(new RTree::Node(Rect(2, 1, 1, 1), 3));
-  test_parent->AddChild(new RTree::Node(Rect(1, 2, 1, 1), 4));
+  scoped_ptr<RTreeNode> node(new RTreeNode);
+  node->AddChild(
+      scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(1, 0, 1, 1), 1)));
+  test_parent->AddChild(node.PassAs<RTreeNodeBase>());
+  node.reset(new RTreeNode);
+  node->AddChild(
+      scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 1, 1, 1), 2)));
+  test_parent->AddChild(node.PassAs<RTreeNodeBase>());
+  node.reset(new RTreeNode);
+  node->AddChild(
+      scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(2, 1, 1, 1), 3)));
+  test_parent->AddChild(node.PassAs<RTreeNodeBase>());
+  node.reset(new RTreeNode);
+  node->AddChild(
+      scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(1, 2, 1, 1), 4)));
+  test_parent->AddChild(node.PassAs<RTreeNodeBase>());
 
   ValidateNode(test_parent.get(), 1U, 5U);
 
@@ -832,11 +752,11 @@ TEST_F(RTreeTest, NodeLeastAreaEnlargement) {
   //  T
   //
   Rect test_rect_below(1, 3, 1, 1);
-  std::vector<Rect> expanded_rects;
+  RTreeRects expanded_rects;
   BuildExpandedRects(test_parent.get(), test_rect_below, &expanded_rects);
-  RTree::Node* result =
-      test_parent->LeastAreaEnlargement(test_rect_below, expanded_rects);
-  EXPECT_EQ(result->key(), 4);
+  RTreeNode* result = NodeLeastAreaEnlargement(
+      test_parent.get(), test_rect_below, expanded_rects);
+  EXPECT_EQ(4, record(result, 0)->key());
 
   // Test rect completely inside b should require minimum area to add to Node b:
   //
@@ -846,8 +766,9 @@ TEST_F(RTreeTest, NodeLeastAreaEnlargement) {
   //
   Rect test_rect_inside(0, 1, 1, 1);
   BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects);
-  result = test_parent->LeastAreaEnlargement(test_rect_inside, expanded_rects);
-  EXPECT_EQ(result->key(), 2);
+  result = NodeLeastAreaEnlargement(
+      test_parent.get(), test_rect_inside, expanded_rects);
+  EXPECT_EQ(2, record(result, 0)->key());
 
   // Add e at (0, 1) to overlap b and c, to test tie-breaking:
   //
@@ -855,7 +776,10 @@ TEST_F(RTreeTest, NodeLeastAreaEnlargement) {
   // eee
   //  d
   //
-  test_parent->AddChild(new RTree::Node(Rect(0, 1, 3, 1), 7));
+  node.reset(new RTreeNode);
+  node->AddChild(
+      scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 1, 3, 1), 7)));
+  test_parent->AddChild(node.PassAs<RTreeNodeBase>());
 
   ValidateNode(test_parent.get(), 1U, 5U);
 
@@ -869,9 +793,233 @@ TEST_F(RTreeTest, NodeLeastAreaEnlargement) {
   //
   Rect test_rect_tie_breaker(3, 1, 1, 1);
   BuildExpandedRects(test_parent.get(), test_rect_tie_breaker, &expanded_rects);
-  result =
-      test_parent->LeastAreaEnlargement(test_rect_tie_breaker, expanded_rects);
-  EXPECT_EQ(result->key(), 3);
+  result = NodeLeastAreaEnlargement(
+      test_parent.get(), test_rect_tie_breaker, expanded_rects);
+  EXPECT_EQ(3, record(result, 0)->key());
+}
+
+// RTreeTest ------------------------------------------------------------------
+
+// An empty RTree should never return AppendIntersectingRecords results, and
+// RTrees should be empty upon construction.
+TEST_F(RTreeTest, AppendIntersectingRecordsOnEmptyTree) {
+  RT rt(2, 10);
+  ValidateRTree(&rt);
+  RT::Matches results;
+  Rect test_rect(25, 25);
+  rt.AppendIntersectingRecords(test_rect, &results);
+  EXPECT_EQ(0U, results.size());
+  ValidateRTree(&rt);
+}
+
+// Clear should empty the tree, meaning that all queries should not return
+// results after.
+TEST_F(RTreeTest, ClearEmptiesTreeOfSingleNode) {
+  RT rt(2, 5);
+  rt.Insert(Rect(0, 0, 100, 100), 1);
+  rt.Clear();
+  RT::Matches results;
+  Rect test_rect(1, 1);
+  rt.AppendIntersectingRecords(test_rect, &results);
+  EXPECT_EQ(0U, results.size());
+  ValidateRTree(&rt);
+}
+
+// Even with a complex internal structure, clear should empty the tree, meaning
+// that all queries should not return results after.
+TEST_F(RTreeTest, ClearEmptiesTreeOfManyNodes) {
+  RT rt(2, 5);
+  AddStackedSquares(&rt, 100);
+  rt.Clear();
+  RT::Matches results;
+  Rect test_rect(1, 1);
+  rt.AppendIntersectingRecords(test_rect, &results);
+  EXPECT_EQ(0U, results.size());
+  ValidateRTree(&rt);
+}
+
+// Duplicate inserts should overwrite previous inserts.
+TEST_F(RTreeTest, DuplicateInsertsOverwrite) {
+  RT rt(2, 5);
+  // Add 100 stacked squares, but always with duplicate key of 0.
+  for (int i = 1; i <= 100; ++i) {
+    rt.Insert(Rect(0, 0, i, i), 0);
+    ValidateRTree(&rt);
+  }
+  RT::Matches results;
+  Rect test_rect(1, 1);
+  rt.AppendIntersectingRecords(test_rect, &results);
+  EXPECT_EQ(1U, results.size());
+  EXPECT_EQ(1U, results.count(0));
+}
+
+// Call Remove() once on something that's been inserted repeatedly.
+TEST_F(RTreeTest, DuplicateInsertRemove) {
+  RT rt(3, 9);
+  AddStackedSquares(&rt, 25);
+  for (int i = 1; i <= 100; ++i) {
+    rt.Insert(Rect(0, 0, i, i), 26);
+    ValidateRTree(&rt);
+  }
+  rt.Remove(26);
+  RT::Matches results;
+  Rect test_rect(1, 1);
+  rt.AppendIntersectingRecords(test_rect, &results);
+  EXPECT_EQ(25U, results.size());
+  VerifyAllKeys(results);
+}
+
+// Call Remove() repeatedly on something that's been inserted once.
+TEST_F(RTreeTest, InsertDuplicateRemove) {
+  RT rt(7, 15);
+  AddStackedSquares(&rt, 101);
+  for (int i = 0; i < 100; ++i) {
+    rt.Remove(101);
+    ValidateRTree(&rt);
+  }
+  RT::Matches results;
+  Rect test_rect(1, 1);
+  rt.AppendIntersectingRecords(test_rect, &results);
+  EXPECT_EQ(100U, results.size());
+  VerifyAllKeys(results);
+}
+
+// Stacked rects should meet all matching queries regardless of nesting.
+TEST_F(RTreeTest, AppendIntersectingRecordsStackedSquaresNestedHit) {
+  RT rt(2, 5);
+  AddStackedSquares(&rt, 100);
+  RT::Matches results;
+  Rect test_rect(1, 1);
+  rt.AppendIntersectingRecords(test_rect, &results);
+  EXPECT_EQ(100U, results.size());
+  VerifyAllKeys(results);
+}
+
+// Stacked rects should meet all matching queries when contained completely by
+// the query rectangle.
+TEST_F(RTreeTest, AppendIntersectingRecordsStackedSquaresContainedHit) {
+  RT rt(2, 10);
+  AddStackedSquares(&rt, 100);
+  RT::Matches results;
+  Rect test_rect(0, 0, 100, 100);
+  rt.AppendIntersectingRecords(test_rect, &results);
+  EXPECT_EQ(100U, results.size());
+  VerifyAllKeys(results);
+}
+
+// Stacked rects should miss a missing query when the query has no intersection
+// with the rects.
+TEST_F(RTreeTest, AppendIntersectingRecordsStackedSquaresCompleteMiss) {
+  RT rt(2, 7);
+  AddStackedSquares(&rt, 100);
+  RT::Matches results;
+  Rect test_rect(150, 150, 100, 100);
+  rt.AppendIntersectingRecords(test_rect, &results);
+  EXPECT_EQ(0U, results.size());
+}
+
+// Removing half the nodes after insertion should still result in a valid tree.
+TEST_F(RTreeTest, RemoveHalfStackedRects) {
+  RT rt(2, 11);
+  AddStackedSquares(&rt, 200);
+  for (int i = 101; i <= 200; ++i) {
+    rt.Remove(i);
+    ValidateRTree(&rt);
+  }
+  RT::Matches results;
+  Rect test_rect(1, 1);
+  rt.AppendIntersectingRecords(test_rect, &results);
+  EXPECT_EQ(100U, results.size());
+  VerifyAllKeys(results);
+
+  // Add the nodes back in.
+  for (int i = 101; i <= 200; ++i) {
+    rt.Insert(Rect(0, 0, i, i), i);
+    ValidateRTree(&rt);
+  }
+  results.clear();
+  rt.AppendIntersectingRecords(test_rect, &results);
+  EXPECT_EQ(200U, results.size());
+  VerifyAllKeys(results);
+}
+
+TEST_F(RTreeTest, InsertDupToRoot) {
+  RT rt(2, 5);
+  rt.Insert(Rect(0, 0, 1, 2), 1);
+  ValidateRTree(&rt);
+  rt.Insert(Rect(0, 0, 2, 1), 1);
+  ValidateRTree(&rt);
+}
+
+TEST_F(RTreeTest, InsertNegativeCoordsRect) {
+  RT rt(5, 11);
+  for (int i = 1; i <= 100; ++i) {
+    rt.Insert(Rect(-i, -i, i, i), (i * 2) - 1);
+    ValidateRTree(&rt);
+    rt.Insert(Rect(0, 0, i, i), i * 2);
+    ValidateRTree(&rt);
+  }
+  RT::Matches results;
+  Rect test_rect(-1, -1, 2, 2);
+  rt.AppendIntersectingRecords(test_rect, &results);
+  EXPECT_EQ(200U, results.size());
+  VerifyAllKeys(results);
+}
+
+TEST_F(RTreeTest, RemoveNegativeCoordsRect) {
+  RT rt(7, 21);
+
+  // Add 100 positive stacked squares.
+  AddStackedSquares(&rt, 100);
+
+  // Now add 100 negative stacked squares.
+  for (int i = 101; i <= 200; ++i) {
+    rt.Insert(Rect(100 - i, 100 - i, i - 100, i - 100), 301 - i);
+    ValidateRTree(&rt);
+  }
+
+  // Now remove half of the negative squares.
+  for (int i = 101; i <= 150; ++i) {
+    rt.Remove(301 - i);
+    ValidateRTree(&rt);
+  }
+
+  // Queries should return 100 positive and 50 negative stacked squares.
+  RT::Matches results;
+  Rect test_rect(-1, -1, 2, 2);
+  rt.AppendIntersectingRecords(test_rect, &results);
+  EXPECT_EQ(150U, results.size());
+  VerifyAllKeys(results);
+}
+
+TEST_F(RTreeTest, InsertEmptyRectReplacementRemovesKey) {
+  RT rt(10, 31);
+  AddStackedSquares(&rt, 50);
+  ValidateRTree(&rt);
+
+  // Replace last square with empty rect.
+  rt.Insert(Rect(), 50);
+  ValidateRTree(&rt);
+
+  // Now query large area to get all rects in tree.
+  RT::Matches results;
+  Rect test_rect(0, 0, 100, 100);
+  rt.AppendIntersectingRecords(test_rect, &results);
+
+  // Should only be 49 rects in tree.
+  EXPECT_EQ(49U, results.size());
+  VerifyAllKeys(results);
+}
+
+TEST_F(RTreeTest, InsertReplacementMaintainsTree) {
+  RT rt(2, 5);
+  AddStackedSquares(&rt, 100);
+  ValidateRTree(&rt);
+
+  for (int i = 1; i <= 100; ++i) {
+    rt.Insert(Rect(0, 0, 0, 0), i);
+    ValidateRTree(&rt);
+  }
 }
 
 }  // namespace gfx
diff --git a/ui/gfx/gfx.gyp b/ui/gfx/gfx.gyp
index f2caa65..3077ac9 100644
--- a/ui/gfx/gfx.gyp
+++ b/ui/gfx/gfx.gyp
@@ -47,8 +47,9 @@
         'geometry/rect_conversions.h',
         'geometry/rect_f.cc',
         'geometry/rect_f.h',
-        'geometry/r_tree.cc',
         'geometry/r_tree.h',
+        'geometry/r_tree_base.cc',
+        'geometry/r_tree_base.h',
         'geometry/safe_integer_conversions.h',
         'geometry/size.cc',
         'geometry/size.h',
diff --git a/ui/views/view.cc b/ui/views/view.cc
index 6cb29e9..c8ebd0a 100644
--- a/ui/views/view.cc
+++ b/ui/views/view.cc
@@ -782,7 +782,7 @@ void View::Paint(gfx::Canvas* canvas, const CullSet& cull_set) {
     // propagation to our children.
     if (IsPaintRoot()) {
       if (!bounds_tree_)
-        bounds_tree_.reset(new gfx::RTree(2, 5));
+        bounds_tree_.reset(new BoundsTree(2, 5));
 
       // Recompute our bounds tree as needed.
       UpdateRootBounds(bounds_tree_.get(), gfx::Vector2d());
@@ -798,7 +798,8 @@ void View::Paint(gfx::Canvas* canvas, const CullSet& cull_set) {
       // our canvas bounds.
       scoped_ptr<base::hash_set<intptr_t> > damaged_views(
           new base::hash_set<intptr_t>());
-      bounds_tree_->Query(canvas_bounds, damaged_views.get());
+      bounds_tree_->AppendIntersectingRecords(
+          canvas_bounds, damaged_views.get());
       // Construct a CullSet to wrap the damaged views set, it will delete it
       // for us on scope exit.
       CullSet paint_root_cull_set(damaged_views.Pass());
@@ -1867,7 +1868,7 @@ void View::DoRemoveChildView(View* view,
 
     // Remove the bounds of this child and any of its descendants from our
     // paint root bounds tree.
-    gfx::RTree* bounds_tree = GetBoundsTreeFromPaintRoot();
+    BoundsTree* bounds_tree = GetBoundsTreeFromPaintRoot();
     if (bounds_tree)
       view->RemoveRootBounds(bounds_tree);
 
@@ -2078,7 +2079,7 @@ void View::SetRootBoundsDirty(bool origin_changed) {
   }
 }
 
-void View::UpdateRootBounds(gfx::RTree* tree, const gfx::Vector2d& offset) {
+void View::UpdateRootBounds(BoundsTree* tree, const gfx::Vector2d& offset) {
   // No need to recompute bounds if we haven't flagged ours as dirty.
   TRACE_EVENT1("views", "View::UpdateRootBounds", "class", GetClassName());
 
@@ -2103,7 +2104,7 @@ void View::UpdateRootBounds(gfx::RTree* tree, const gfx::Vector2d& offset) {
   }
 }
 
-void View::RemoveRootBounds(gfx::RTree* tree) {
+void View::RemoveRootBounds(BoundsTree* tree) {
   tree->Remove(reinterpret_cast<intptr_t>(this));
 
   root_bounds_dirty_ = true;
@@ -2114,8 +2115,8 @@ void View::RemoveRootBounds(gfx::RTree* tree) {
   }
 }
 
-gfx::RTree* View::GetBoundsTreeFromPaintRoot() {
-  gfx::RTree* bounds_tree = bounds_tree_.get();
+View::BoundsTree* View::GetBoundsTreeFromPaintRoot() {
+  BoundsTree* bounds_tree = bounds_tree_.get();
   View* paint_root = this;
   while (!bounds_tree && !paint_root->IsPaintRoot()) {
     // Assumption is that if IsPaintRoot() is false then parent_ is valid.
diff --git a/ui/views/view.h b/ui/views/view.h
index 8ddf734..93cbd48 100644
--- a/ui/views/view.h
+++ b/ui/views/view.h
@@ -1248,6 +1248,8 @@ class VIEWS_EXPORT View : public ui::LayerDelegate,
   friend class FocusManager;
   friend class Widget;
 
+  typedef gfx::RTree<intptr_t> BoundsTree;
+
   // Painting  -----------------------------------------------------------------
 
   enum SchedulePaintType {
@@ -1340,17 +1342,17 @@ class VIEWS_EXPORT View : public ui::LayerDelegate,
 
   // If needed, updates the bounds rectangle in paint root coordinate space
   // in the supplied RTree. Recurses to children for recomputation as well.
-  void UpdateRootBounds(gfx::RTree* bounds_tree, const gfx::Vector2d& offset);
+  void UpdateRootBounds(BoundsTree* bounds_tree, const gfx::Vector2d& offset);
 
   // Remove self and all children from the supplied bounds tree. This is used,
   // for example, when a view gets a layer and therefore becomes paint root. It
   // needs to remove all references to itself and its children from any previous
   // paint root that may have been tracking it.
-  void RemoveRootBounds(gfx::RTree* bounds_tree);
+  void RemoveRootBounds(BoundsTree* bounds_tree);
 
   // Traverse up the View hierarchy to the first ancestor that is a paint root
   // and return a pointer to its |bounds_tree_| or NULL if no tree is found.
-  gfx::RTree* GetBoundsTreeFromPaintRoot();
+  BoundsTree* GetBoundsTreeFromPaintRoot();
 
   // Transformations -----------------------------------------------------------
 
@@ -1531,7 +1533,7 @@ class VIEWS_EXPORT View : public ui::LayerDelegate,
   // If this View IsPaintRoot() then this will be a pointer to a spatial data
   // structure where we will keep the bounding boxes of all our children, for
   // efficient paint damage rectangle intersection.
-  scoped_ptr<gfx::RTree> bounds_tree_;
+  scoped_ptr<BoundsTree> bounds_tree_;
 
   // Transformations -----------------------------------------------------------