| Computing desk | ||
|---|---|---|
| < December 15 | << Nov | December | Jan >> | Current desk > |
| Welcome to the Wikipedia Computing Reference Desk Archives |
|---|
| The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
December 16 Information
Hi, I'm trying to implement an avl tree. I have a height field in each node which represents the max distance to null. When I delete a node, I replace it with its successor. But I have a problem determining what the height of of the new node will be (in place of the deleted node). How can I determine its height? Thanks Exx8 ( talk) 23:24, 16 December 2019 (UTC)
- Well, when you do the deletion, you can track any tree rotations involved to see how they affect the height of the new node. But, storing the height in each node doesn't sound like it can work. For example, doing just a few deletions can change the heights of all the nodes. I think you if you need the height of a node, you should just compute it by searching downwards. Since AVL trees are always (nearly) balanced, that will be an O(log n) operation which is basically what you expect when doing stuff with trees. 173.228.123.190 ( talk) 12:13, 21 December 2019 (UTC)
- @ Exx8: Did you see the AVL tree article? The tree is implemented with a three-valued balance factor in each node, which just shows which of the two subtrees is higher. The full information about the subtree height is not necessary for AVL tree to keep its balance. -- CiaPan ( talk) 18:24, 26 December 2019 (UTC)
| Computing desk | ||
|---|---|---|
| < December 15 | << Nov | December | Jan >> | Current desk > |
| Welcome to the Wikipedia Computing Reference Desk Archives |
|---|
| The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
December 16 Information
Hi, I'm trying to implement an avl tree. I have a height field in each node which represents the max distance to null. When I delete a node, I replace it with its successor. But I have a problem determining what the height of of the new node will be (in place of the deleted node). How can I determine its height? Thanks Exx8 ( talk) 23:24, 16 December 2019 (UTC)
- Well, when you do the deletion, you can track any tree rotations involved to see how they affect the height of the new node. But, storing the height in each node doesn't sound like it can work. For example, doing just a few deletions can change the heights of all the nodes. I think you if you need the height of a node, you should just compute it by searching downwards. Since AVL trees are always (nearly) balanced, that will be an O(log n) operation which is basically what you expect when doing stuff with trees. 173.228.123.190 ( talk) 12:13, 21 December 2019 (UTC)
- @ Exx8: Did you see the AVL tree article? The tree is implemented with a three-valued balance factor in each node, which just shows which of the two subtrees is higher. The full information about the subtree height is not necessary for AVL tree to keep its balance. -- CiaPan ( talk) 18:24, 26 December 2019 (UTC)