添加到AVL樹

Question

當我將值添加到AVL樹時，我怎麼知道在哪裏插入它？我不是在談論編碼方面，而是更多的是一種圖像表現。我假設插入是在第一個可用的外部節點完成的，但我不確定，因爲我的教科書中給出的示例插入到隨機外部節點。

Answer 1

AVL樹是一個自平衡二叉搜索樹，二叉搜索樹具有以下屬性：每個節點的左子樹只包含密鑰小於節點密鑰的節點，每個節點的右子樹只包含節點鍵大於節點的密鑰。所以你必須以插入新屬性的方式插入新節點：從根節點開始，通過比較新節點密鑰和當前節點密鑰來工作，如果新節點密鑰更大，則訪問右邊孩子，否則你訪問左邊孩子下一個，當沒有孩子訪問那個地方時，你插入新的節點。