avl-tree - 添加到 AVL 树

Question

当我向 AVL 树添加一个值时，我怎么知道在哪里插入它？我不是在谈论编码方面，而是更多的图形表示。我假设插入是在第一个可用的外部节点处完成的，但我不确定，因为我的教科书中给出的示例在随机外部节点处插入。

Answer 1

AVL树是一种自平衡二叉搜索树，二叉搜索树具有以下性质：每个节点的左子树只包含键小于节点键的节点，每个节点的右子树只包含键大于节点的节点关键。因此，您必须以在插入后保持声明属性的方式插入新节点：您从根节点开始，并通过比较新节点键和当前节点键来处理叶子，如果新节点键更大，您访问右子节点，否则访问左节点下一个孩子，当在那个地方没有孩子可以访问时，您插入新节点。