<p>A chain is not considered an AVL tree, as after the second insert (a chain of length 3), the root's left son has height 1 while son on the right has height -1 (which is the <a href="http://en.wikipedia.org/wiki/Tree_height#Terminology" rel="nofollow">definition</a> of the height of an empty tree).</p>

CC BY-SA 3.0
2014-03-31T12:21:21.307Z
The definition in question is not definition of avl tree and what you mentioned is *conventionally* accepted and is actually for implementation purpose. (There is no right son at all, except you define it).
Saeed
CC BY-SA 3.0
2014-03-31T12:28:32.777Z
@Saeed, It's definition dependent. You can (and perhaps should) say every node has two sons, each of which may be an empty tree, and the height of the empty tree is defined as -1..
R B
CC BY-SA 3.0
2014-03-31T12:31:23.817Z
If you have this definition, then is not same as definition in the question (very clearly quoted, if is incomplete then tell to OP), also in any case you should provide source of your definition. He talks about X you conclude on Y, is this logical?
Saeed
CC BY-SA 3.0
2014-03-31T12:35:34.327Z
From the same Wikipedia page the OP have linked to:
"In an AVL tree, the heights of the two child subtrees of any node differ by at most one;".
This implies any node has has two child subtrees.
R B
CC BY-SA 3.0
2014-03-31T12:39:21.203Z
Also when I thought about your definition seems illogical to me. If every node should have two sons, then we have infinite complete binary tree, may be you mean every non empty node (then empty node definition is somehow strange, if it's empty node why it should have a parent node, that means it's just for implementation).
Saeed
CC BY-SA 3.0
2014-03-31T12:41:33.060Z
@R B, Read my comment to OP, that is property of avl tree, not definition. e.g A bipartite graph has at least one vertex, then this is definition of bipartite graph? Finally suppose you are correct but my question remains, is this the definition that OP said in the question?
Saeed
CC BY-SA 3.0
2014-03-31T12:48:19.747Z
Well, this is the source he claim to have quoted , then yes, this is the definition he was referring to.
R B
CC BY-SA 3.0
2014-03-31T12:56:27.850Z
@R B, you are absolutely correct in first part, this is what he claims, but you are absolutely wrong in the second part, this is not the definition he was referring, the definition very clearly still exists in question. Finally AVL tree is just balanced binary search tree, nothing less or more (According to what you both linked in your comments). Then that is (definition in Q) just property of AVL. If still you dont accept this, I think one of us is doing false analogy so is better to not discuss anymore on this.
Saeed
CC BY-SA 3.0
2014-03-31T12:58:09.520Z
This is his definition: *"A binary search tree (BST) is called an AVL-tree if for every internal node v of T the heights of the children of v can differ by at most 1"*
Saeed
CC BY-SA 3.0
2014-03-31T12:59:39.030Z
Actually if he replace with "A balanced binary search tree (BBST) is called an AVL-tree if for every internal node v of T the heights of the children of v can differ by at most 1" then we can say is according to wiki. But then obviously his counter example is wrong.
Saeed
CC BY-SA 3.0
2014-03-31T12:07:34.370Z
2014-03-31T12:07:34.370Z
R B
<blockquote>
  <p>AVL-tree T: can T be a chain (linear BST) according to the definition ?</p>
</blockquote>

<p>The definition of an AVL-tree is as follows:</p>

<p>A binary search tree (BST) is called an AVL-tree if for every internal node $v$ of $T$ the heights of the children of $v$ can differ by at most $1$.</p>

<p><img src="https://i.sstatic.net/ln76G.png" alt="enter image description here"></p>

<p>But according to this definition the above BST is an AVL-tree ? Well, the height of every children differ by at most $1$ ?</p>

<p>But at the same time the height of an AVL-tree storing $n$ keys is $O(\log n)$ ? Thus an AVL-tree cannot be a chain ?</p>

CC BY-SA 3.0
2014-03-31T11:55:05.183Z
I think you mean internal node not interval. Also where is source of this definition? This is different from known definitions like what exists in wiki (self balancing binary tree such that ...), your definition is actually property of avl tree. Finally, this does not look like a research level question.
Saeed
CC BY-SA 3.0
2014-03-31T12:00:52.060Z
Here is my source: http://en.wikipedia.org/wiki/AVL_tree
Shuzheng
CC BY-SA 3.0
2014-03-31T12:03:48.870Z
So read your source carefully, and distinguish between *property*: *"In an AVL tree, the heights of the two child subtrees of any node differ by at most one"* and the *definition* : *"AVL tree (Adelson-Velskii and Landis' tree, named after the inventors) is a self-balancing binary search tree"*.
Saeed
<graph-algorithms>
AVL-tree T: can T be a chain (linear BST) according to the definition?
Shuzheng
# AVL-tree T: can T be a chain (linear BST) according to the definition?

(Asked by: username_0 on 2014-03-31)

> AVL-tree T: can T be a chain (linear BST) according to the definition ?

The definition of an AVL-tree is as follows:

A binary search tree (BST) is called an AVL-tree if for every internal node $v$ of $T$ the heights of the children of $v$ can differ by at most $1$.

![enter image description here](https://i.sstatic.net/ln76G.png)

But according to this definition the above BST is an AVL-tree ? Well, the height of every children differ by at most $1$ ?

But at the same time the height of an AVL-tree storing $n$ keys is $O(\log n)$ ? Thus an AVL-tree cannot be a chain ?

**Tags:** graph-algorithms
> **Comments:**
> **username_1**: I think you mean internal node not interval. Also where is source of this definition? This is different from known definitions like what exists in wiki (self balancing binary tree such that ...), your definition is actually property of avl tree. Finally, this does not look like a research level question.  
> **username_0**: Here is my source: http://en.wikipedia.org/wiki/AVL_tree  
> **username_1**: So read your source carefully, and distinguish between *property*: *"In an AVL tree, the heights of the two child subtrees of any node differ by at most one"* and the *definition* : *"AVL tree (Adelson-Velskii and Landis' tree, named after the inventors) is a self-balancing binary search tree"*.  

---

## 1 answers

### Answer by username_2 on 2014-03-31. Score: 0

A chain is not considered an AVL tree, as after the second insert (a chain of length 3), the root's left son has height 1 while son on the right has height -1 (which is the [definition](http://en.wikipedia.org/wiki/Tree_height#Terminology) of the height of an empty tree).

> **Comments:**
> **username_1**: The definition in question is not definition of avl tree and what you mentioned is *conventionally* accepted and is actually for implementation purpose. (There is no right son at all, except you define it).  
> **username_2**: @Saeed, It's definition dependent. You can (and perhaps should) say every node has two sons, each of which may be an empty tree, and the height of the empty tree is defined as -1..  
> **username_1**: If you have this definition, then is not same as definition in the question (very clearly quoted, if is incomplete then tell to OP), also in any case you should provide source of your definition. He talks about X you conclude on Y, is this logical?  
> **username_2**: From the same Wikipedia page the OP have linked to: "In an AVL tree, the heights of the two child subtrees of any node differ by at most one;". This implies any node has has two child subtrees.  
> **username_1**: Also when I thought about your definition seems illogical to me. If every node should have two sons, then we have infinite complete binary tree, may be you mean every non empty node (then empty node definition is somehow strange, if it's empty node why it should have a parent node, that means it's just for implementation).  
> **username_1**: @R B, Read my comment to OP, that is property of avl tree, not definition. e.g A bipartite graph has at least one vertex, then this is definition of bipartite graph? Finally suppose you are correct but my question remains, is this the definition that OP said in the question?  
> **username_2**: Well, this is the source he claim to have quoted , then yes, this is the definition he was referring to.  
> **username_1**: @R B, you are absolutely correct in first part, this is what he claims, but you are absolutely wrong in the second part, this is not the definition he was referring, the definition very clearly still exists in question. Finally AVL tree is just balanced binary search tree, nothing less or more (According to what you both linked in your comments). Then that is (definition in Q) just property of AVL. If still you dont accept this, I think one of us is doing false analogy so is better to not discuss anymore on this.  
> **username_1**: This is his definition: *"A binary search tree (BST) is called an AVL-tree if for every internal node v of T the heights of the children of v can differ by at most 1"*  
> **username_1**: Actually if he replace with "A balanced binary search tree (BBST) is called an AVL-tree if for every internal node v of T the heights of the children of v can differ by at most 1" then we can say is according to wiki. But then obviously his counter example is wrong.  

---

