Re: [問題] DS-AVL樹的問題

看板CSSE (電腦科學及軟體工程)作者Killercat (殺人貓™)時間16年前 (2008/06/13 08:37)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/2 (看更多)

※ 引述《Solars (學士後醫(內科?))》之銘言： : 各位前輩、版友好，小弟最近在寫avl樹的作業，可是小弟的程式一直有個地方有問題 : ，老闆交代的是產生一堆亂數(例如5000個)，範圍在1~1000內，所以會有很多數值一樣的 : 亂數，我的AVL程式最後會計算這棵樹的高度，但是我的程式中只有判斷亂數值是否大於 : 或小於父節點的值，沒有判斷亂數值一樣時該做什麼的動作；所以如果產生100000個亂數 : ，由於一堆亂數值都會產生相同的，導致高度永遠會在一個值以內(因為範圍在1~1000)， : 翻開坊間的書，AVL或BST的插入範例，也都沒有看到相同數值時的處理方法，所以我該怎 : 麼去處理相同的值呢?還是這題目本身有問題?AVL能插入相同數值的節點嗎? : 麻煩各位大大賜教了，小弟想了非常久............ : 先謝謝各位大大了，感恩!! 普通來講，AVL算BST的一種額外條件，所以BST該有的條件AVL一樣有 BST本身並不能處理同key(就是你說的同數) 同樣的AVL也不行。所以我們在做BST的時候要注意鍵值(key index)的唯一性這邊所謂的key index就是你說的亂數, 在BST裡面是必須唯一的本題無解，除非你去改AVL的結構(不過這樣就不叫AVL了) 當然也不是沒有非常trick的處理法啦 (比方說碰到同值就+0.00001, 然後第二個就+0.00002) 不過普通來講AVL並不是拿來處理這種事情的 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.217.108.106 ※ 編輯: Killercat 來自: 61.217.108.106 (06/13 08:39)