2

我想扩充一个 avl 树以向每个节点添加额外的属性，例如它包含的节点数（即在其子树中）。

从这里的 avl java 实现代码 http://www.blackbam.at/blackbams-blog/2012/05/04/avl-tree-implementation-in-java/ 我想向它添加某些代码，以便每个节点将包含一个 size 元素。

在 AvlNode 类中，我将其更改为：

/** Here is the AVL-Node class for Completenesse **/
public class AvlNode {
     public AvlNode left;
     public AvlNode right;
     public AvlNode parent;
     public int key;
     public int balance;
     public int size;

     public AvlNode(int k) {
          left = right = parent = null;
          balance = 0;
          key = k;
          size = 1;
     }
     public String toString() {
         return "" + key;
     }
}

但是现在对于 AvlTree 类，在插入和删除操作期间，我实际上在哪里添加代码来更新节点的大小值。我认为这是 rotateleft 和 rotateright 方法。这是正确的吗？

4

1 回答 1

1

这完全取决于您尝试使用增强功能做什么。通常，在扩充平衡二叉搜索树时，您需要在逻辑中插入额外的代码来执行

  • 插入，改变某些子树的数量/内容，
  • 删除，从子树中删除元素，以及
  • 树旋转，将节点移动到不同的子树。

CLRS 的“算法简介”教科书有一章是关于增强二叉搜索树的。虽然他们专注于红/黑树，但相同的一般策略应该适用于任何基于旋转的树平衡方案。

希望这可以帮助！

于 2013-02-07T00:14:06.007 回答