ในวิทยาการคอมพิวเตอร์ต้นไม้ค้นหาแบบไบนารี ( BST ) หรือที่เรียกว่าต้นไม้ไบนารีแบบเรียงลำดับเป็นโครงสร้างข้อมูลต้นไม้ไบนารีแบบมีรากโดยที่คีย์ของแต่ละโหนดภายในจะมีค่ามากกว่าคีย์ทั้งหมดในซับทรีด้านซ้ายของโหนดนั้น และมีค่าน้อยกว่าคีย์ทั้งหมดในซับทรีด้านขวาความซับซ้อนของเวลาในการดำเนินการบนต้นไม้ค้นหาแบบไบนารีเป็นแบบเชิงเส้นเมื่อเทียบกับความสูงของต้นไม้

ต้นไม้ค้นหาแบบไบนารี (Binary Search Tree: BST) ช่วยให้การค้นหาแบบไบนารีทำได้อย่างรวดเร็ว ทั้งการค้นหา การเพิ่ม และการลบรายการข้อมูล เนื่องจากโหนดใน BST ถูกจัดเรียงไว้เพื่อให้การเปรียบเทียบแต่ละครั้งข้ามไปประมาณครึ่งหนึ่งของต้นไม้ที่เหลืออยู่ ประสิทธิภาพการค้นหาจึงเป็นสัดส่วนกับลอการิทึมไบนารี BST ถูกคิดค้นขึ้นในทศวรรษ 1960 เพื่อแก้ปัญหาการจัดเก็บข้อมูลที่มีป้ายกำกับอย่างมีประสิทธิภาพ และได้รับการยกย่องให้เป็นผลงานของConway Berners-LeeและDavid Wheeler

ประสิทธิภาพของต้นไม้ค้นหาแบบไบนารีขึ้นอยู่กับลำดับการแทรกโหนดลงในต้นไม้ เนื่องจาก1การแทรกแบบสุ่มอาจนำไปสู่ความเสื่อมถอยได้ สามารถสร้างต้นไม้ค้นหาแบบไบนารีได้หลายรูปแบบโดยรับประกันประสิทธิภาพในกรณีที่เลวร้ายที่สุด การดำเนินการพื้นฐานประกอบด้วย: การค้นหา การท่องไป การแทรก และการลบ ต้นไม้ค้นหาแบบไบนารีที่รับประกันความซับซ้อนในกรณีที่เลวร้ายที่สุดจะมีประสิทธิภาพดีกว่าอาร์เรย์ที่ไม่เรียงลำดับ ซึ่งจะต้องใช้เวลาค้นหาเชิงเส้น

การวิเคราะห์ความซับซ้อนของ BST แสดงให้เห็นว่าโดยเฉลี่ยแล้วการแทรก การลบ และการค้นหาใช้เวลาn โหนด ในกรณีที่เลวร้ายที่สุด ความซับซ้อนจะลดลงเหลือเท่ากับรายการเชื่อมโยงเดี่ยว: เพื่อแก้ไขปัญหาการเพิ่มขึ้นอย่างไม่มีที่สิ้นสุดของความสูงของต้นไม้ด้วยการแทรกและการลบแบบไม่จำกัด จึง มีการนำ BST รูปแบบ ปรับสมดุลตัวเองมาใช้เพื่อจำกัดความซับซ้อนของการค้นหาที่เลวร้ายที่สุดให้เท่ากับลอการิทึมไบนารีต้นไม้ AVLเป็นต้นไม้ค้นหาไบนารีแบบปรับสมดุลตัวเองต้นแรก คิดค้นขึ้นในปี 1962 โดยGeorgy Adelson-VelskyและEvgenii Landis ^{[ 1 ] [ 2 ] [ 3 ]}${\displaystyle \Theta (\log n)}$${\displaystyle n}$${\displaystyle O(n)}$

ต้นไม้ค้นหาแบบไบนารีสามารถนำไปใช้ในการสร้างชนิดข้อมูลนามธรรมเช่นเซตแบบไดนามิกตารางค้นหาและคิวลำดับความสำคัญและยังใช้ในอัลกอริธึมการเรียงลำดับเช่น การเรียงลำดับ แบบ ต้นไม้ได้อีกด้วย

อัลกอริทึมต้นไม้ค้นหาแบบไบนารีถูกค้นพบโดยอิสระโดยนักวิจัยหลายคน รวมถึง PF Windley, Andrew Donald Booth , Andrew ColinและThomas N. Hibbard [ ^{4 ] [ 5 ] อั}ลกอริทึมนี้ได้รับการยกย่องให้เป็นผลงานของConway Berners-LeeและDavid Wheelerซึ่งใช้มันในการจัดเก็บข้อมูลที่มีป้ายกำกับในเทปแม่เหล็กในปี 1960 ^{[ 6 ]}หนึ่งในอัลกอริทึมต้นไม้ค้นหาแบบไบนารีที่เก่าแก่และได้รับความนิยมมากที่สุดคืออัลกอริทึมของ Hibbard ^{[ 4 ]}

ความซับซ้อนของเวลาของต้นไม้ค้นหาแบบไบนารีจะเพิ่มขึ้นอย่างไม่มีขีดจำกัดตามความสูงของต้นไม้ หากโหนดถูกแทรกในลำดับที่ไม่แน่นอน ดังนั้นจึง มีการนำ ต้นไม้ค้นหาแบบไบนารีที่ปรับสมดุลตัวเองมาใช้เพื่อจำกัดความสูงของต้นไม้^{[ 7 ]} มีการนำต้นไม้ค้นหาแบบไบนารี ที่ปรับสมดุลความสูงต่างๆ มา ใช้เพื่อจำกัดความสูงของต้นไม้ เช่นต้นไม้ AVL , Treapsและต้นไม้แดง-ดำ^{[ 8 ]}${\displaystyle O(\log n)}$

ต้นไม้ค้นหาแบบไบนารีเป็นต้นไม้ไบนารีแบบมีรากซึ่งโหนดต่างๆ ถูกจัดเรียงตามลำดับทั้งหมดที่เข้มงวดโดยที่โหนดที่มีคีย์มากกว่าโหนดA ใดๆ จะถูกเก็บไว้ในซับทรี ด้านขวา ของโหนดA นั้น และโหนดที่มีคีย์เท่ากับหรือน้อยกว่าAจะถูกเก็บไว้ในซับทรีด้านซ้ายของA ซึ่งเป็นไปตามคุณสมบัติการค้นหาแบบไบนารี^{[ 9 ] : 298 [ 10 ] : 287}

ต้นไม้ค้นหาแบบไบนารีมีประสิทธิภาพในการเรียงลำดับและอัลกอริทึมการค้นหา เช่นกัน อย่างไรก็ตาม ความซับซ้อนของการค้นหาของ BST ขึ้นอยู่กับลำดับการแทรกและการลบโหนด เนื่องจากในกรณีที่เลวร้ายที่สุด การดำเนินการต่อเนื่องในต้นไม้ค้นหาแบบไบนารีอาจนำไปสู่ความเสื่อมและก่อตัวเป็น โครงสร้างคล้าย รายการเชื่อมโยงเดี่ยว (หรือ "ต้นไม้ที่ไม่สมดุล") ดังนั้นจึงมีความซับซ้อนในกรณีที่เลวร้ายที่สุดเช่นเดียวกับรายการเชื่อมโยง [ ^{11 ] [ 9 ] : 299-302}

ต้นไม้ค้นหาแบบไบนารี (Binary search tree) ยังเป็นโครงสร้างข้อมูลพื้นฐานที่ใช้ในการสร้างโครงสร้างข้อมูลนามธรรมเช่น เซตมัลติเซตและอาร์เรย์แบบเชื่อมโยง (associative arrays ) อีกด้วย

การค้นหาคีย์เฉพาะในโครงสร้างข้อมูลแบบต้นไม้ค้นหาไบนารี สามารถเขียนโปรแกรมได้ทั้งแบบเรียกซ้ำหรือแบบวนซ้ำ

การค้นหาเริ่มต้นด้วยการตรวจสอบโหนดรากหากต้นไม้เป็นค่าว่างคีย์ที่กำลังค้นหาจะไม่มีอยู่ในต้นไม้ มิฉะนั้น หากคีย์เท่ากับคีย์ของราก การค้นหาจะสำเร็จและจะส่งคืนโหนดนั้น หากคีย์น้อยกว่าคีย์ของราก การค้นหาจะดำเนินการต่อโดยการตรวจสอบซับทรีด้านซ้าย ในทำนองเดียวกัน หากคีย์มากกว่าคีย์ของราก การค้นหาจะดำเนินการต่อโดยการตรวจสอบซับทรีด้านขวา กระบวนการนี้จะทำซ้ำจนกว่าจะพบคีย์หรือซับทรีที่เหลือเป็นค่าว่างหากไม่พบคีย์ที่ค้นหาหลังจากถึงซับทรีแล้ว คีย์นั้นจะไม่มีอยู่ในต้นไม้^{[ 10 ] : 290–291} ${\displaystyle {\text{nil}}}$${\displaystyle {\text{nil}}}$

รหัสเทียมต่อไปนี้ใช้ขั้นตอนการค้นหา BST ผ่านการเรียกซ้ำ [ ^{10 ] : 290}

Recursive-Tree-Search(x, key) ถ้า x = NIL หรือ key = x.key แล้วให้คืนค่า x ถ้า key < x.key แล้วให้คืนค่า Recursive-Tree-Search(x.left, key) มิฉะนั้นให้คืนค่า Recursive-Tree-Search(x.right, key) end if

กระบวนการเรียกซ้ำจะดำเนินต่อไปจนกว่าจะพบค่า a หรือค่าที่กำลังค้นหา ${\displaystyle {\text{nil}}}$${\displaystyle {\text{key}}}$

เวอร์ชันเรียกซ้ำของการค้นหาสามารถ "คลี่" ออกเป็นลูป whileได้ บนเครื่องส่วนใหญ่ พบว่าเวอร์ชันแบบวนซ้ำมีประสิทธิภาพมากกว่า^{[ 10 ] : 291}

Iterative-Tree-Search(x, key) while x ≠ NIL and key ≠ x.key do if key < x.key then x := x.ซ้าย อื่น x := x.ขวา จบถ้าทำซ้ำส่งคืน x 

เนื่องจากการค้นหาอาจดำเนินไปจนถึงโหนดใบ บาง โหนด ความซับซ้อนของเวลาในการดำเนินการของการค้นหา BST คือโดยที่คือความสูงของต้นไม้อย่างไรก็ตาม กรณีที่เลวร้ายที่สุดสำหรับการค้นหา BST คือโดยที่คือจำนวนโหนดทั้งหมดใน BST เนื่องจาก BST ที่ไม่สมดุลอาจเสื่อมสภาพเป็นรายการเชื่อมโยง อย่างไรก็ตาม หาก BST มีความสมดุลด้านความสูงความสูงจะเป็น[ ^{10 ] : 290} ${\displaystyle O(h)}$${\displaystyle h}$${\displaystyle O(n)}$${\displaystyle n}$${\displaystyle O(\log n)}$

สำหรับการดำเนินการบางอย่าง เมื่อกำหนดโหนดการค้นหาผู้สืบทอดหรือผู้มาก่อนของโหนดนั้นมีความสำคัญ สมมติว่าคีย์ทั้งหมดของ BST แตกต่างกัน ผู้สืบทอดของโหนดใน BST คือโหนดที่มีคีย์ที่เล็กที่สุดที่มากกว่าคีย์ของโหนดนั้น ในทางกลับกัน ผู้มาก่อนของโหนดใน BST คือโหนดที่มีคีย์ที่ใหญ่ที่สุดที่เล็กกว่าคีย์ของโหนดนั้น รหัสเทียมต่อไปนี้จะค้นหาผู้สืบทอดและผู้มาก่อนของโหนดใน BST ^{[ 12 ] [ 13 ] [ 10 ] : 292–293} ${\displaystyle {\text{x}}}$${\displaystyle {\text{x}}}$${\displaystyle {\text{x}}}$${\displaystyle {\text{x}}}$${\displaystyle {\text{x}}}$${\displaystyle {\text{x}}}$${\displaystyle {\text{x}}}$

BST-Successor(x) ถ้า x.right ≠ NIL ให้ส่งคืน BST-Minimum(x.right) end if y := x.parent ในขณะที่ y ≠ NIL และ x = y.right ให้ ทำ x := y y := y.parent ทำซ้ำส่งคืน y 

ถ้า x.left ≠ NIL ให้คืนค่าBST - Maximum(x.left)  y := x.parent ในขณะที่ y ≠ NIL และ x = y.left ให้ ทำ x := y y := y.parent ทำซ้ำส่งคืน y 

การดำเนินการต่างๆ เช่น การค้นหาโหนดใน BST ที่มีคีย์เป็นค่าสูงสุดหรือต่ำสุดนั้นมีความสำคัญอย่างยิ่งในการดำเนินการบางอย่าง เช่น การกำหนดโหนดที่ตามมาและโหนดก่อนหน้า ต่อไปนี้คือรหัสเทียมสำหรับการดำเนินการ^{[ 10 ] : 291–292}

BST-Maximum(x) ในขณะที่ x.right ≠ NIL ทำ x := x.ขวา ทำซ้ำการส่งคืน x 

BST-Minimum(x) ในขณะที่ x.left ≠ NIL ทำ x := x.ซ้าย ทำซ้ำการส่งคืน x 

การดำเนินการต่างๆ เช่น การแทรกและการลบทำให้การแสดง BST เปลี่ยนแปลงแบบไดนามิก โครงสร้างข้อมูลต้องได้รับการแก้ไขในลักษณะที่คุณสมบัติของ BST ยังคงอยู่ โหนดใหม่จะถูกแทรกเป็นโหนดใบใน BST ^{[ 10 ] : 294–295} ต่อไปนี้เป็นการใช้งานแบบวนซ้ำของการดำเนินการแทรก^{[ 10 ] : 294}

1 BST-Insert(T, z) 2 y := NIL 3 x := T.root 4 ในขณะที่ x ≠ NIL ให้ ทำ 5 y := x 6 ถ้า z.key < x.key แล้ว 7 x := x.ซ้าย 8 อย่างอื่น 9 x := x.ขวา 10 จบถ้า 11 ทำซ้ำ 12 z.parent := y 13 ถ้า y = NIL แล้ว 14 T.root := z 15 มิเช่นนั้น ถ้า z.key < y.key แล้ว 16 y.left := z 17 อย่างอื่น 18 y.right := z 19 จบถ้า

ขั้นตอนดังกล่าวจะรักษา "ตัวชี้ตาม" ไว้เป็นผู้ปกครองของหลังจากเริ่มต้นในบรรทัดที่ 2 ลูป whileตามบรรทัดที่ 4-11 จะทำให้ตัวชี้ได้รับการอัปเดต ถ้าเป็นBST จะว่างเปล่า ดังนั้นจะถูกแทรกเป็นโหนดรากของต้นไม้ค้นหาไบนารีถ้าไม่ใช่การแทรกจะดำเนินการโดยการเปรียบเทียบคีย์กับคีย์ของในบรรทัดที่ 15-19 และโหนดจะถูกแทรกตามนั้น^{[ 10 ] : 295} ${\displaystyle {\text{y}}}$${\displaystyle {\text{x}}}$${\displaystyle {\text{y}}}$${\displaystyle {\text{nil}}}$${\displaystyle {\text{z}}}$${\displaystyle {\text{T}}}$${\displaystyle {\text{nil}}}$${\displaystyle {\text{y}}}$

การลบโหนด เช่น ออกจากต้นไม้ค้นหาแบบไบนารีมีสามกรณี: ^{[ 10 ] : 295-297} ${\displaystyle {\text{Z}}}$${\displaystyle {\text{BST}}}$

1. ถ้าเป็นโหนดใบ จะถูกแทนที่ด้วยตามที่แสดงใน (a)${\displaystyle {\text{Z}}}$${\displaystyle {\text{NIL}}}$
2. ถ้ามีลูกเพียงคนเดียว โหนดลูกของจะถูกยกระดับโดยการแก้ไขโหนดแม่ของให้ชี้ไปยังโหนดลูก ส่งผลให้รับตำแหน่งของ ในต้นไม้ ดังแสดงใน (b) และ (c)${\displaystyle {\text{Z}}}$${\displaystyle {\text{Z}}}$${\displaystyle {\text{Z}}}$${\displaystyle {\text{Z}}}$
3. ถ้ามีทั้งลูกซ้ายและลูกขวาตัวสืบทอดลำดับของ เช่นจะแทนที่โดยทำตามสองกรณีดังนี้: ${\displaystyle {\text{Z}}}$${\displaystyle {\text{Z}}}$${\displaystyle {\text{Y}}}$${\displaystyle {\text{Z}}}$
   1. ถ้าเป็นลูกทางขวาของ ตามที่แสดงใน (d) จะทำให้ลูกทางขวาของ เคลื่อนที่และลูกทางขวาของ จะยังคงไม่เปลี่ยนแปลง${\displaystyle {\text{Y}}}$${\displaystyle {\text{Z}}}$${\displaystyle {\text{Y}}}$${\displaystyle {\text{Z}}}$${\displaystyle {\text{Y}}}$
   2. ถ้าอยู่ในซับทรีด้านขวาของ แต่ไม่ใช่ลูกด้านขวาของ ตามที่แสดงใน (e) จะถูกแทนที่ด้วยลูกด้านขวาของตัวเองก่อน จากนั้นจึงแทนที่ตำแหน่งของ ในทรี${\displaystyle {\text{Y}}}$${\displaystyle {\text{Z}}}$${\displaystyle {\text{Z}}}$${\displaystyle {\text{Y}}}$${\displaystyle {\text{Z}}}$
4. อีกทางเลือกหนึ่งคือ สามารถใช้ตัวก่อนหน้าตามลำดับได้เช่นกัน

รหัสเทียมต่อไปนี้ใช้การดำเนินการลบในต้นไม้ค้นหาแบบไบนารี^{[ 10 ] : 296-298}

1 BST-Delete(BST, z) 2 ถ้า z.left = NIL แล้ว 3 Shift-Nodes(BST, z, z.right) 4. ถ้า z.right = NIL แล้ว 5 โหนดเลื่อน (BST, z, z.left) 6 อย่างอื่น 7 y := BST-Successor(z) 8 ถ้า y.parent ≠ z แล้ว 9 โหนดเลื่อน (BST, y, y.right) 10 y.right := z.right 11 y.right.parent := y 12 จบถ้า 13 โหนดเลื่อน (BST, z, y) 14 y.left := z.left 15 y.left.parent := y 16 จบถ้า

1. โหนดการเลื่อน (BST, u, v) 2 ถ้า u.parent = NIL แล้ว 3 BST.root := v 4. else if u = u.parent.left then 5 u.parent.left := v 5 อย่างอื่น 6 u.parent.right := v 7 สิ้นสุดถ้า 8 ถ้า v ≠ NIL แล้ว 9 v.parent := u.parent 10 จบ ถ้า

ขั้นตอนดังกล่าวเกี่ยวข้องกับกรณีพิเศษ 3 กรณีที่กล่าวถึงข้างต้น บรรทัดที่ 2-3 เกี่ยวข้องกับกรณีที่ 1 บรรทัดที่ 4-5 เกี่ยวข้องกับกรณีที่ 2 และบรรทัดที่ 6-16 สำหรับกรณีที่ 3 ฟังก์ชันตัวช่วยถูกใช้ภายในอัลกอริทึมการลบเพื่อวัตถุประสงค์ในการแทนที่โหนดด้วยในต้นไม้ค้นหาแบบไบนารี[ ^{10 ] : 298} ขั้นตอนนี้จัดการการลบ (และการแทนที่) ของ จาก${\displaystyle {\text{BST-Delete}}}$${\displaystyle {\text{โหนดเลื่อน}}}$${\displaystyle {\text{u}}}$${\displaystyle {\text{v}}}$${\displaystyle {\text{BST}}}$${\displaystyle {\text{u}}}$${\displaystyle {\text{BST}}}$

BST สามารถท่องผ่านได้ด้วยอัลกอริทึมพื้นฐานสามแบบ ได้แก่การเดินต้นไม้แบบ inorder , preorderและpostorder ^{[ 10 ] : 287}

• การท่องต้นไม้แบบเรียงลำดับ (Inorder tree walk ): โหนดจากซับทรีด้านซ้ายจะถูกเยี่ยมชมก่อน ตามด้วยโหนดรากและซับทรีด้านขวา การท่องแบบนี้จะเยี่ยมชมโหนดทั้งหมดตามลำดับของค่าคีย์ที่ไม่ลดลง
• ลำดับการเข้าชมแบบต้นไม้ : โหนดรากจะถูกเข้าชมก่อน ตามด้วยโหนดสาขาซ้ายและขวา
• การท่องต้นไม้แบบ Postorder : โหนดจากซับทรีด้านซ้ายจะถูกเยี่ยมชมก่อน ตามด้วยซับทรีด้านขวา และสุดท้ายคือโหนดราก

ต่อไปนี้เป็นการใช้งานการเดินต้นไม้แบบเรียกซ้ำ^{[ 10 ] : 287–289}

Inorder-Tree-Walk(x) ถ้า x ≠ NIL แล้ว Inorder-Tree-Walk(x.left) เยี่ยมชมโหนด Inorder-Tree-Walk(x.right) จบถ้า

Preorder-Tree-Walk(x) ถ้า x ≠ NIL ให้ไปที่โหนด สั่งซื้อล่วงหน้า-Tree-Walk(x.left) สั่งซื้อล่วงหน้า-Tree-Walk(x.right) จบถ้า

Postorder-Tree-Walk(x) ถ้า x ≠ NIL แล้ว Postorder-Tree-Walk(x.left) Postorder-Tree-Walk(x.right) เยี่ยมชมโหนดสุดท้ายหาก

หากไม่มีการปรับสมดุล การแทรกหรือการลบในต้นไม้ค้นหาแบบไบนารีอาจนำไปสู่การเสื่อมสภาพ ส่งผลให้ความสูงของต้นไม้ (โดยที่คือจำนวนรายการในต้นไม้) ลดลงจนประสิทธิภาพการค้นหาลดลงจนเทียบเท่ากับการค้นหาเชิงเส้น^{[ 14 ]}การรักษาสมดุลของต้นไม้ค้นหาและจำกัดความสูงไว้เป็นกุญแจสำคัญต่อประโยชน์ของต้นไม้ค้นหาแบบไบนารี ซึ่งสามารถทำได้โดยกลไก "การปรับสมดุลด้วยตนเอง" ในระหว่างการดำเนินการอัปเดตต้นไม้ที่ออกแบบมาเพื่อรักษาความสูงของต้นไม้ให้อยู่ในระดับความซับซ้อนของลอการิทึมไบนารี^{[ 7 ] [ 15 ] : 50} ${\displaystyle n}$${\displaystyle n}$${\displaystyle O(\log n)}$

ต้นไม้จะมีความสมดุลด้านความสูงหากความสูงของต้นไม้ย่อยด้านซ้ายและต้นไม้ย่อยด้านขวามีความสัมพันธ์กันด้วยปัจจัยคงที่ คุณสมบัตินี้ได้รับการแนะนำโดยต้นไม้ AVLและได้รับการพัฒนาต่อโดยต้นไม้แดง-ดำ^{[ 15 ] : 50–51} ความสูงของโหนดทั้งหมดบนเส้นทางจากรากไปยังโหนดใบที่แก้ไขแล้วจะต้องได้รับการสังเกตและอาจต้องแก้ไขในการดำเนินการแทรกและลบทุกครั้งในต้นไม้^{[ 15 ] : 52}

ในต้นไม้ที่สมดุลน้ำหนัก เกณฑ์ของต้นไม้ที่สมดุลคือจำนวนใบของต้นไม้ย่อย น้ำหนักของต้นไม้ย่อยด้านซ้ายและด้านขวาจะแตกต่างกันไม่เกิน[ ^{16 ] [ 15 ] : 61} อย่างไรก็ตาม ความแตกต่างนั้นถูกจำกัดด้วยอัตราส่วนของน้ำหนัก เนื่องจากเงื่อนไขสมดุลที่แข็งแกร่งของไม่สามารถรักษาไว้ได้ด้วยการปรับสมดุลใหม่ระหว่างการดำเนินการแทรกและลบต้นไม้ที่สมดุลน้ำหนักจะให้เงื่อนไขสมดุลทั้งตระกูล โดยที่ต้นไม้ย่อยด้านซ้ายและด้านขวาแต่ละต้นมีน้ำหนักอย่างน้อยเศษส่วนของน้ำหนักทั้งหมดของต้นไม้ย่อย^{[ 15 ] : 62} ${\displaystyle 1}$${\displaystyle \alpha }$${\displaystyle 1}$${\displaystyle O(\log n)}$${\displaystyle \alpha }$${\displaystyle \alpha }$

มีต้นไม้ค้นหาไบนารีแบบสมดุลตัวเองหลายต้น รวมถึงT-tree [ ^{17 ] treap} [ 18 ^{] red} -black ^tree [ ^{19 ] B} - tree ^{[ 20 ]} 2–3 tree ^{[ 21 ]}และSplay tree ^{[ 22 ]}

ต้นไม้ค้นหาแบบไบนารีใช้ในอัลกอริทึมการเรียงลำดับ เช่นtree sortโดยที่องค์ประกอบทั้งหมดจะถูกแทรกในครั้งเดียวและต้นไม้จะถูกสำรวจตามลำดับ^{[ 23 ]} BST ยังใช้ในquicksort อีกด้วย ^{[ 24 ]}

ต้นไม้ค้นหาแบบไบนารีใช้ในการใช้งานคิวลำดับความสำคัญโดยใช้คีย์ของโหนดเป็นลำดับความสำคัญ การเพิ่มองค์ประกอบใหม่ลงในคิวเป็นไปตามการดำเนินการแทรก BST ปกติ แต่การดำเนินการลบจะขึ้นอยู่กับประเภทของคิวลำดับความสำคัญ: ^{[ 25 ]}

• ถ้าเป็นคิวที่มีลำดับความสำคัญจากน้อยไปมาก การลบองค์ประกอบที่มีลำดับความสำคัญต่ำที่สุดจะทำได้โดยการท่องไปในคิวค้นหาแบบไบนารี (BST) จากซ้ายไปขวา
• ถ้าเป็นคิวลำดับความสำคัญจากมากไปน้อย การลบองค์ประกอบที่มีลำดับความสำคัญสูงสุดจะทำได้โดยการท่องไปในโครงสร้างค้นหาแบบไบนารี (BST) จากขวาไปซ้าย

•  บทความนี้ได้นำเนื้อหาที่เป็นสาธารณสมบัติจากPaul E. Black มาใช้ "Binary Search Tree" . Dictionary of Algorithms and Data Structures . NIST .
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). "12: Binary search trees, 15.5: Optimal binary search trees". Introduction to Algorithms (ฉบับที่ 2). MIT Press . หน้า  253–272 , 356–363 . ISBN 0-262-03293-7.
• Jarc, Duane J. (3 ธันวาคม 2005). "การท่องไปในโครงสร้างต้นไม้ไบนารี" . การแสดงภาพโครงสร้างข้อมูลแบบโต้ตอบ . มหาวิทยาลัยแมริแลนด์ . เก็บถาวรจากต้นฉบับเมื่อ 27 กุมภาพันธ์ 2014 . สืบค้นเมื่อ30 เมษายน 2006 .
• Knuth, Donald (1997). "6.2.2: การค้นหาในต้นไม้ไบนารี" ศิลปะแห่งการเขียนโปรแกรมคอมพิวเตอร์เล่ม 3: "การเรียงลำดับและการค้นหา" (ฉบับที่ 3). Addison-Wesley. หน้า  426–458 . ISBN 0-201-89685-0.
• ลอง, ฌอน. "ต้นไม้ค้นหาแบบไบนารี" ( PPT ) . การแสดงภาพโครงสร้างข้อมูลและอัลกอริทึม - แนวทางที่ใช้สไลด์ PowerPoint . SUNY Oneonta .
• Parlante, Nick (2001). "ต้นไม้ไบนารี" . ห้องสมุดการศึกษาด้านวิทยาการคอมพิวเตอร์ . มหาวิทยาลัยสแตนฟอร์ด . เก็บถาวรจากต้นฉบับเมื่อ 30 มกราคม 2022

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับโครงสร้างข้อมูลแบบต้นไม้ค้นหาไบนารี (Binary Search Tree )

• เบน แพฟฟ์: บทนำเกี่ยวกับต้นไม้ค้นหาแบบไบนารีและต้นไม้สมดุล ( PDF; 1675 kB) 2004
• การแสดงภาพต้นไม้ค้นหาแบบไบนารี