如何扩充AVL树? [英] How to augment an AVL tree?

问题描述

我想扩充一个avl树，以便为每个节点添加额外的属性，例如它包含的节点数(即在其子树中).

I want to augment an avl tree to add extra properties to each node such as number of nodes it contains (i.e. in its subtree).

从此处的此avl Java实现代码 http://www.blackbam.在/blackbams-blog/2012/05/04/avl-tree-implementation-in-java/我想向其中添加某些代码，以便每个节点都包含一个size元素.

From this avl java implementation code here http://www.blackbam.at/blackbams-blog/2012/05/04/avl-tree-implementation-in-java/ I want to add certain code to it, so that each node will contain a size element.

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

In the AvlNode class, I changed it to:

/** 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方法.是这样吗?

But now for the AvlTree class, where do I actually add the code to update the size value of the node, during the insert and delete operations. I think it's the rotateleft and rotateright methods. Is this right?

推荐答案

这完全取决于您要对增强进行的操作.通常，当扩充平衡的二叉搜索树时，您需要在逻辑中插入额外的代码

This completely depends on what you're trying to do with the augmentation. Typically, when augmenting a balanced binary search tree, you would need to insert extra code in the logic to do

• 插入，这些插入可更改某些子树的数量/内容，
• 删除操作，可从子树中删除元素，
• 树旋转，可在不同子树之间移动节点.

CLRS的算法简介"教科书有一章介绍了增强型二进制搜索树.虽然它们着重于红色/黑色树，但对于任何基于旋转的树平衡方案，相同的常规策略也应适用.

The "Introduction to Algorithms" textbook by CLRS has a chapter on augmented binary search trees. While they focus on red/black trees, the same general policies should work for any rotation-based tree balancing scheme.

希望这会有所帮助！

这篇关于如何扩充AVL树?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！