How to create and use SplayTree in Julia

Overview

SplayTree is a self-balancing binary search tree. It has an additional property with the recently accessed elements to quickly access it.

The time complexity for the insert, search, and delete is O(log n)O(log\space n).

Note: nn is the number of nodes in the SplayTree.

Example

Below is a sample code for using a SplayTree in Julia:

using DataStructures
# create a new spaly tree 
splayTree = SplayTree();
push!(splayTree, 1)
push!(splayTree, 5)
push!(splayTree, 2)
push!(splayTree, 4)
push!(splayTree, 10)
for k in 1:length(splayTree)
    println("tree[$(k)] :", splayTree[k] )
end
#check if the spalytree contains a key
println("Check if spalytree has key 4 :", haskey(splayTree, 4))
# deleting 4 from the splayTree
delete!(splayTree, 4)
println("After deleting 4, The spalyTree is")
# print the elements of splayTree
for k in 1:length(splayTree)
    println("tree[$(k)] :", splayTree[k] )
end

Explanation

  • Line 4: We create a SplayTree object with the name splayTree.
  • Lines 6–10: We use the push! method to insert five elements into the splayTree.
  • Line 12–14: We print the elements of the splayTree.
  • Line 18: We use the haskey method to check if the splayTree contains key 4.
  • Line 21: We use the delete method to delete the key 4 from the splayTree .

Note: The complete reference to the SplayTree can be found on the official Julia page here.

New on Educative
Learn to Code
Learn any Language as a beginner
Develop a human edge in an AI powered world and learn to code with AI from our beginner friendly catalog
🏆 Leaderboard
Daily Coding Challenge
Solve a new coding challenge every day and climb the leaderboard

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)